Erkennen Sie Zyklen mit ungeradem Gesamtgewicht in einem Diagramm mit {0,1}-gewichteten Kanten

Question

Gegeben sei ein kantengewichteter Digraph $G = (V, E \subseteq V^2, w \in E o \{0, 1\})$, Gibt es einen Algorithmus, der zurückgibt? TRUE wenn es in diesem Diagramm einen Zyklus gibt, dessen Gesamtgewicht ungerade ist und FALSE Ansonsten läuft das schneller als $O((|V| + |E|)(c + 1))$ (Wo $c$ ist die Anzahl der einfachen Zyklen im Diagramm, was natürlich der Fall ist $\Omega(2^{|V|})$)?

Wie aus der Frage hervorgeht, habe ich mir bereits einen Algorithmus ausgedacht, der ausgeführt werden kann $O((|V| + |E|)(c + 1))$ Zeit.Dieser Algorithmus erfordert die erste Ausführung Johnsons einfacher Zyklusaufzählungsalgorithmus, was uns alle einfachen Zyklen im Diagramm liefert.Seit even + even = even, und alle Zyklen durch Addition einfacher Zyklen erstellt werden, enthält der Graph einen Zyklus ungerader Länge genau dann, wenn er einen einfachen Zyklus ungerader Länge enthält.Daher berechnen wir einfach die Parität der einfachen Zyklen und kehren zurück TRUE wenn einer von ihnen seltsam ist, und FALSE ansonsten.

Kann jemand einen effizienteren Ansatz finden?Im Idealfall nicht einfach „Johnsons Algorithmus durch einen anderen einfachen Zyklusaufzählungsalgorithmus mit etwas besserer Asymptotik ersetzen“, da die Graphen, mit denen ich es zu tun habe, wirklich nicht so groß sind und konstante Faktoren daher durchaus dominieren können.

Answer 1

Sie können dies in lösen $O(|V| \cdot |E|)$ Zeit.

Konstruieren Sie einen Digraphen mit Eckpunkten der Form $\langle v,b angle$ Wo $v \in V$, $b \in \{0,1\}$, wie folgt:für jede Kante $v \stackrel{t}{ o} w$ Fügen Sie in Ihrem Diagramm die Kanten hinzu $\langle v,b angle o \langle w,b + t \bmod 2 angle$ für jede $b \in \{0,1\}$ zum neuen Diagramm.

Dann für jeden $v \in V$, prüfen Sie, ob es einen Pfad von gibt $\langle v,0 angle$ Zu $\langle v,1 angle$ oder von $\langle v, 1 angle$ Zu $\langle v,0 angle$ in dieser neuen Grafik.Dies kann mit zwei DFS-Suchen pro Scheitelpunkt erfolgen $v \in V$;jede DFS-Suche dauert $O(|E|)$ Zeit, also die Gesamtlaufzeit $O(|V| \cdot |E|)$ Zeit.Die Suche kann beschleunigt werden, indem der neue Graph einmal in stark verbundene Komponenten zerlegt und dann im Tag der Komponenten (dem Metagraphen) gesucht wird.

Answer 2

Konstruieren Sie die Kanten-Scheitelpunkt-Inzidenzmatrix:Zeilen entsprechen Kanten, Spalten Eckpunkten, und es gibt eine $1$ wenn die Kante auf den Scheitelpunkt trifft.Fügen Sie weitere Spalten hinzu $1$'S.Sie möchten wissen, ob es eine Teilmenge der Zeilen gibt, die zum Vektor summiert werden $0,\ldots,0,1$ (Modulo 2).Sie können dies mithilfe der Gaußschen Eliminierung in Polynomzeit herausfinden.

Was passiert hier?Betrachten wir die ursprüngliche Kanten-Scheitelpunkt-Inzidenzmatrix.Zeilen, die Zyklen entsprechen, summieren sich zu Null, da jeder Scheitelpunkt an genau zwei Kanten vorkommt.Umgekehrt ist der Grad jedes Scheitelpunkts gerade, wenn wir eine Reihe von Zeilen haben, deren Summe Null ergibt.Beginnend an einer beliebigen Kante können wir einen Spaziergang verfolgen, der sich schließlich in sich selbst schließt.Wir entfernen den entsprechenden Kreis (der nicht unbedingt die ursprüngliche Kante enthalten muss) und fahren fort.Auf diese Weise sehen wir, dass eine Menge von Zeilen, die sich zu Null summieren, einer kantendisjunkten Vereinigung von Kreisen entspricht.

Durch Hinzufügen eines zusätzlichen $1$ Spalte zur Matrix verfolgen wir die Parität des Zyklus.Ein ungerader Zyklus ergibt in der Summe den Vektor $0,\ldots,0,1$.Umgekehrt, wenn sich eine Reihe von Zeilen summiert $0,\ldots,0,1$, dann entspricht es einer Menge von Zyklen, deren Gesamtlänge ungerade ist, also ist einer der Zyklen ungerade.

Schließlich ist die Feststellung, ob sich ein Vektor im Zeilenraum der Matrix befindet, ein Standardproblem der linearen Algebra, das mithilfe der Gaußschen Eliminierung und verwandter Algorithmen gelöst werden kann.