Ermitteln der Anzahl der Zyklen der Länge in einem Diagramm

Wir haben einen Zeitalgorithmus, um zu bestimmen, ob ein Graph einen Zyklus der Länge genau . Wie können wir mit demselben oder einem anderen Algorithmus herausfinden, wie viele solcher Zyklen in vorhanden sind? G k k $f(k) n^3$$G$$k$$k$$G$

Wenn Teil der Eingabe ist, ist das Problem der Entscheidung, ob einen einfachen Zyklus der Länge enthält, NP-vollständig. Für jedes feste kann das Problem entweder in oder gelöst werden. Flum und Grohe [1] zeigten, dass die durch parametrisierten Zählzyklen und Pfade der Länge sowohl in gerichteten als auch in ungerichteten Graphen #W [1] -vollständig sind.G k k O ( V E ) O ( V & ohgr ; log V ) k $k$$G$$k$$k$$O(VE)$$O(V^\omega \log V)$$k$$k$

Für kann man die Zyklen in , wobei der Exponent der Matrixmultiplikation ist. Dies ist das Ergebnis von Alon, Yuster und Zwick [2]. Das Papier enthält auch Methoden zum Finden einfacher Zyklen der Länge genau , wobei .k O ( V ω ) ω < 2.376 k k ≥ $3 \leq k \leq 7$$k$$O(V^\omega)$$\omega < 2.376$$k$$k \geq 3$

[1] Flum, Jörg und Martin Grohe. "Die parametrisierte Komplexität von Zählproblemen." SIAM Journal on Computing 33.4 (2004): 892 & ndash; 922.

[2] Alon, Noga, Raphael Yuster und Uri Zwick. "Finden und Zählen gegebener Längenzyklen." Algorithmica 17.3 (1997): 209 & ndash; 223.

Wie Juho betonte, ist das Problem durch die Arbeit von Flum und Grohe als #W [1] -vollendet bekannt. Es gibt jedoch ein randomisiertes Approximationsschema, das in FPT-Zeit ausgeführt wird und eine Schätzung zurückgibt, die mit hoher Wahrscheinlichkeit ein Faktor von der richtigen Lösung entfernt ist. Siehe "Approximationsalgorithmen für einige parametrisierte Zählprobleme" von Arvind und Raman, ISAAC 2002.$(1+\epsilon)$

Für jedes gibt es einen ziemlich einfachen f ( k ) n ⌈ k / 2 ⌉ + 3- Zeitalgorithmus von Vassilevska Williams und Williams . Der asymptotisch schnellste exakte Algorithmus, der AFAIK bekannt ist , ist Björklund, Kaski und Kowalik .$k$$f(k)n^{\lceil k/2 \rceil+3}$