Effizientes Finden eines 5-Zyklus in einem spärlichen Graphen.

(Crossposting von MathOverflow)

Hallo,

Ich habe diesen Thread gelesen: /mathpro/16393/finding-a-cycle-of-fixed-length

Ich möchte einen 5-Zyklus in einer Grafik finden. Eigentlich , was ich wirklich will , ist ein kürzester ungeradeer Zyklus der Länge mindestens 5, aber vielleicht ist das ein wenig nebensächlich. Für meine Zwecke behandle ich und in der Komplexitätsanalyse gleich. $m$ $n$

Können wir in diesem Fall besser als eine Farbcodierung einen 5-Zyklus finden? Lassen Sie mich meine Frage konkret formulieren:

Was ist das Minimum so dass es einen -Zeitalgorithmus zum Erfassen eines Zyklus der Länge 5 gibt? Was ist der Algorithmus? Und was ist das , wenn Sie unpraktisch Methoden wie Coppersmith-Winograd schnelle Matrixmultiplikation verbieten? $\alpha$ $O(m^\alpha)$ $\alpha$

ds.algorithms graph-theory graph-algorithms sparse-matrix Andrew D. King
quelle

Crosspost von MO.

Hsien-Chih Chang 張顯張顯

Haben Ihre Graphen eine besondere Struktur, außer dass sie spärlich sind? (Wie zum Beispiel niedrige Entartung.)

Robin Kothari

Nein, Sie können das Diagramm so teuflisch gestalten, wie Sie möchten. Eigentlich ist es mir egal, ob der Graph spärlich ist: Ich betrachte einen Liniendiagramm und das zugrunde liegende Diagramm so dass (wir können annehmen, dass einfach ist). Der Grund, warum ich behandle unddas gleiche ist, dass ich kenne und ich möchte die Komplexität in Bezug auf analysieren und, aber ich kann nichts darüber sagen, wievergleicht mit.

G

$G$

H

$H$

G = L (H)

$G=L(H)$

H

$H$

| E (H) |

$|E(H)|$

| V (H) |

$|V(H)|$

| E (H) | = | V (G) |

$|E(H)|=|V(G)|$

| V (G) |

$|V(G)|$

| E (G) |

$|E(G)|$

| E (H) |

$|E(H)|$

| V (H) |

$|V(H)|$

Andrew D. King

Um klar zu sein, macht es Ihnen nichts aus, wenn der Zyklus wiederholte Eckpunkte enthält, richtig?

User834

Ich erlaube keine wiederholten Eckpunkte, aber für einen 5-Zyklus ist das egal, da ich annehme, dass der Graph einfach ist und daher keine 2-Zyklen hat.

Andrew D. King

Antworten:

Um zu Mihais Antwort hinzuzufügen:

In der Tat können 5-Zyklen (und im Allgemeinen Zyklen) in spärlichen Graphen viel schneller als gelöst werden, wenn der Trick mit hohem / niedrigem Grad verwendet wird. Sie müssen sich nur eine andere Arbeit von Alon, Yuster und Zwick ansehen: $k$ $O(mn)$

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.101.4120

Zum Beispiel kann ein 5-Zyklus in ohne Abhängigkeit von der Matrixmultiplikation gefunden werden. Siehe Satz 3.4 des oben verlinkten Papiers. $O(m^{1.67})$

Auch wenn es nicht allzu schwierig ist, die 5-Zyklus-Erkennung auf die Boolesche Matrixmultiplikation (mit konstantem Faktor-Overhead) zu reduzieren, erscheint im Farbcodierungspapier keine Verringerung in der entgegengesetzten Richtung. Eine enge Reduktion (die die Laufzeitkomplexität bewahrt) von der Booleschen Matrixmultiplikation zur 5-Zyklus-Erkennung ist nicht bekannt.

Ryan Williams
quelle

Der dichte Fall entspricht im Wesentlichen der booleschen Matrixmultiplikation durch Farbcodierung. Siehe http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.103.5167&rep=rep1&type=pdf .

$O(mn)$

Mihai
quelle

Vielen Dank! Ich werde mir die Monien-Zeitung ansehen, wenn ich Zugang dazu habe.

Andrew D. King