Können wir bei einem 4-Zyklus-freien Graphen bestimmen, ob er in quadratischer Zeit einen 3-Zyklus hat?

Das Cycle-Problem ist wie folgt: $k$

Instanz: Ein ungerichteter Graph mit Eckpunkten und bis zu Kanten. $G$ $n$ $n \choose 2$

Frage: Gibt es in ein (richtiges) Rad ? $k$ $G$

Hintergrund: Für jedes feste $k$ können wir $2k$ Zyklen in lösen $O(n^2)$ .

Raphael Yuster, Uri Zwick: Noch schneller zu geraden Rädern. SIAM J.
Discrete Math. 10 (2): 209-222 (1997)

Es ist jedoch nicht bekannt, ob wir 3-Zyklen (dh 3-Cliquen) in weniger als der Matrixmultiplikationszeit lösen können.

Meine Frage: Unter der Annahme, dass $G$ keine 4-Zyklen enthält, können wir das 3-Zyklen-Problem in lösen $O(n^2)$ ?

David schlug einen Lösungsansatz für diese Variante des 3-Zyklus-Problems in $O(n^{2.111})$ .

graph-theory graph-algorithms clique polynomial-time fixed-parameter-tractable Michael Wehar
quelle

Es scheint, dass wenn der kleinste Zyklus eines Graphen

G

$G$ eine Länge von mindestens 5 hat, er höchstens

O (n^{\frac{3}{2}})

$O(n^{\frac{3}{2}})$ Kanten hat. Link: link.springer.com/article/10.1007%2FBF01787638

Michael Wehar

Zusätzliche Informationen finden Sie in diesem Artikel

Michael Wehar

Vielleicht interessieren Sie sich auch für Eisenbrand, Friedrich und Fabrizio Grandoni. "Über die Komplexität von Clique mit festen Parametern und dominierender Menge." Theoretical Computer Science 326.1 (2004): 57 & ndash; 67. (Falls Sie es noch nicht wussten).

Juho

Antworten:

Ja, das ist bekannt. Es erscheint in einer der wichtigsten Quellenangaben zur Dreiecksfindung ...

Itai und Rodeh zeigen nämlich in SICOMP 1978, wie in -Zeit ein Zyklus in einem Graphen gefunden werden kann, der höchstens eine Kante mehr als der Mindestlängenzyklus aufweist. (Siehe die ersten drei Sätze der Zusammenfassung hier: http://www.cs.technion.ac.il/~itai/publications/Algorithms/min-circuit.pdf ) Es ist eine einfache Prozedur, die auf den Eigenschaften von width-first basiert Suche. $O(n^2)$

Wenn Ihr Graph also 4-Zyklen-frei ist und ein Dreieck vorhanden ist, muss der Algorithmus dieses ausgeben, da kein 5-Zyklen-Wert oder ein größerer Wert ausgegeben werden kann.

Ryan Williams
quelle

Es ist nicht quadratisch, aber Alon Yuster und Zwick ("Finding and counting given length cycles", Algorithmica 1997) geben einen Algorithmus zum Finden von Dreiecken in der Zeit , wobei ist der Exponent für die schnelle Matrixmultiplikation. Für 4-zyklenfreie Graphen ergibt das Einstecken von und (ansonsten gibt es einen Zyklus, unabhängig von der Existenz von Zyklen) die Zeit . $O(m^{2\omega/(\omega+1)})$ $\omega$ $\omega<2.373$ $m=O(n^{3/2})$ $4$ $3$ $O(n^{3\omega/(\omega+1)})=O(n^{2.111})$

David Eppstein
quelle

Das ist toll! Ich weiß das wirklich zu schätzen. :)

Michael Wehar

Ja, wenn ein Graph keine 4-Zyklen hat, dann hat er höchstens Kanten. Link: books.google.com/…

O (n^{\frac{3}{2}})

$O(n^{\frac{3}{2}})$

Michael Wehar

Fühlen Sie sich frei, mich zu korrigieren, wenn ich falsch liege. Es scheint, dass "The Even Circuit Theorem" von Erdos besagt, dass wenn ein Graph zyklenfrei ist, er höchstens Kanten hat. Link: sciencedirect.com/science/article/pii/S0012365X99901073

2 k

$2k$

O (n^{1 + \frac{1}{k}})

$O(n^{1+\frac{1}{k}})$

Michael Wehar

Wenn ein Graph keinen 6-Zyklus hat, hat er folglich höchstens Kanten. Daher können wir mit der von David vorgeschlagenen Methode bestimmen, ob es in einen 3-Zyklus gibt . :)

O (n^{\frac{4}{3}})

$O(n^{\frac{4}{3}})$

O (n^{1.876})

$O(n^{1.876})$

Michael Wehar

Ferner wird für jeden festen , wenn ist -Zyklus frei bestimmen können wir dann , wenn einen 3-Zyklus in subquadratic Zeit hat , weil nicht zu viele Kanten hat. Wenn jedoch ist, werden die Dinge interessant. Können wir schlagen ?

k > 2

$k > 2$

G

$G$

2 k

$2k$

G

$G$

G

$G$

k = 2

$k = 2$

O (n^{2.111})

$O(n^{2.111})$

Michael Wehar