Komplexität der k-Clique für Hypergraphen

Klassisches Problem:

Es sei eine Zahl $k$ gegeben. Das $k$ Clique-Problem ist wie folgt.

Existiert bei einem Graphen $G$ eine Teilmenge $S$ von $k$ Eckpunkten, so dass zwei beliebige Eckpunkte von $S$ benachbart sind?

Hypergraph Problem:

Es seien die Zahlen $c$ und $k$ gegeben. Das $(c,k)$ -Hyperclique-Problem ist wie folgt.

Gibt es bei einem $c$ einheitlichen Hypergraphen $H$ eine Menge $S$ von $k$ Eckpunkten, so dass jede Teilmenge von $c$ Eckpunkten aus $S$ eine Hyperkante bildet.

Fragen:

(1) Was ist der bekannteste Algorithmus zur Lösung der $(c,k)$ -Hyperclique?

(2) Wie hoch ist die zeitliche Komplexität?

(3) Gibt es einen Zusammenhang zwischen $(c,k)$ -Hyperclique und Matrixmultiplikation?

Soweit ich weiß, könnte dies ein gut untersuchtes Problem sein. Alle Referenzen, die dieses Problem untersuchen, werden sehr geschätzt.

cc.complexity-theory graph-theory matrices clique fixed-parameter-tractable Michael Wehar
quelle

Vielleicht lohnt es sich, auf das Offensichtliche hinzuweisen: Da wir den Fall

verstehen , ist das Problem NP-vollständig und nicht FPT in Bezug auf

(sondern FPT in Bezug auf

). Weiter (immer noch offensichtlich) könnten Sie das Problem als Auswahl von

Zeilen der Inzidenzmatrix umformulieren, so dass in der Submatrix dieser Zeilen Spalten die Summe .

c = 2

$c=2$

c

$c$

k

$k$

k

$k$

(\binom{k}{c})

$k\choose c$

c

$c$

Andrew D. King

Dies wird normalerweise so formuliert, dass eine unabhängige Menge in einem einheitlichen Hypergraphen gefunden wird. Siehe Yuster von 2006 Papier research.haifa.ac.il/~raphy/papers/counthyper.pdf für einige nützliche Hinweise (einschließlich der Verbindungen mit Matrix - Multiplikation).

k

$k$

c

$c$

András Salamon

@ AndrewD.King, ich verstehe nicht, was du mit "aber ist FPT in Bezug auf k" meinst, k-Clique ist W [1] -hart in Bezug auf k. Und OP: K-Clique ist bereits schwer, aber Ihre Frage ist keine Frage auf Forschungsebene, da sie mit Polynomproblemen verglichen wird.

Saeed

Danke für die Auskunft. Ich bin am meisten daran interessiert, ob es und gibt oder nicht, so dass -Hyperclique in . Wir wissen , dass für , -clique in gelöst werden können .

c > 2

$c>2$

k > 2

$k>2$

(c, k)

$(c,k)$

D T I M E (n^{k - ϵ})

$\mathrm{DTIME}(n^{k-\epsilon})$

k > 2

$k>2$

k

$k$

D T I M E (n^{k - ϵ})

$\mathrm{DTIME}(n^{k-\epsilon})$

Michael Wehar

Sie wissen also, dass es für Clique kein n ^ o (k) gibt, und mit Bezug auf die Matrixmultipulation meinen Sie nicht die Reduzierung der AP, sondern nur die Reduzierung der Laufzeit. Jetzt ist es für mich klarer, ich habe keine Ahnung davon, aber vielleicht brauchen Sie es c auch in den Exponenten aufnehmen.

Saeed

Antworten:

Es ist nicht bekannt, ob es ein , und so dass die -Hyperclique in -Zeit vorliegt . Beachten Sie, dass der Fall von trivial ist. Seit Jahren habe ich dieses Problem vielen Menschen mitgeteilt und es in cs266 in Stanford gelehrt, da es mit der Lösung von Sat verbunden ist. (Mehrere offene Problemsitzungen in Workshops haben dies wahrscheinlich aufgezeichnet.) Hier sind einige Dinge, die ich weiß: $\varepsilon > 0$ $c > 2$ $k > c$ $(c,k)$ $n^{k-\varepsilon}$ $k \leq c$ $k$

Ich habe vor einigen Jahren bewiesen, dass das Lösen von auf Knotengraphen in Zeit Hyperclique in Zeit impliziert . Habe es nicht veröffentlicht. $4-cycle$ $n$ $n^{2-\varepsilon}$ $(3,4)$ $n^{4-\varepsilon}$

UPDATE (Aug 2019) das oben genannte Ergebnis und einige Verallgemeinerungen erscheinen jetzt in der Arbeit

Andrea Lincoln, Virginia Vassilevska Williams, R. Ryan Williams: Enge Härte für kürzeste Zyklen und Wege in spärlichen Graphen . SODA 2018: 1236-1252

Wenn Sie hyperclique wie oben angegeben lösen können, kann Max-3-Sat in weniger als Zeit gelöst werden. In ähnlicher Weise würde das Lösen einer -Hyperclique einen schnelleren Sat-Algorithmus ergeben. Wenn Sie also an eine starke ETH glauben, gibt es hier eine offensichtliche Grenze. Die Reduktion ist eine natürliche Verallgemeinerung der Reduktion von Max-2-Sat auf Dreiecksfindung ( Clique) aus ICALP'04 und meiner Doktorarbeit. $(3,4)$ $2^n$ $(k,k+1)$ $k$ $(2,3)$

Sie können Hyperclique in Zeit lösen indem Sie das Papier Efficient Algorithms for Clique Problems verallgemeinern . $(c,k)$ $n^k/(\log n)^{\Omega(k)}$

Ryan Williams
quelle

Danke Ryan! Ich freue mich über Ihre Antwort und das Teilen des Papiers über das Cliquenproblem. :)

Michael Wehar

Ist 5-Takt schwieriger als 4-Zyklus?

Michael Wehar

Soweit wir wissen, ist 3-Zyklus schwieriger. Der ungerade Fall benötigt im Allgemeinen ungefähr O (n ^ {2.373}) Zeit, der gerade Fall dauert O (n ^ 2) für Zyklen fester Länge. Siehe zum Beispiel Yuster und Zwick, Finden sogar gleichmäßiger Zyklen noch schneller.

Ryan Williams

Oh wow! Das ist ziemlich interessant. OK danke. :)

Michael Wehar

Cool! Vielen Dank für die aktualisierte Referenz.

Michael Wehar