Die Komplexität des Zählens einfacher Pfade in einem gerichteten Graphen

Sei ein Digraph (nicht unbedingt eine DAG) und sei . Was ist die Komplexität der Zählen der Anzahl von einfachen Pfade in . $G$ $s,t \in V(G)$ $s-t$ $G$

Ich würde erwarten, dass das Problem # -vollständig ist, konnte aber keine genaue Referenz finden. ${\mathsf P}$

Beachten Sie auch, dass eine Reihe ähnlicher Fragen hier und anderswo richtig beantwortet wurden, aber nicht genau diese Frage - um zu betonen, ich bin nicht daran interessiert, Wege und / oder ungerichtete Graphen zu zählen (im ersten Fall steht die Variante in und in der anderen # -hard). ${\mathsf P}$ ${\mathsf P}$

ds.algorithms reference-request counting-complexity SamiD
quelle

Die # P-Vollständigkeit gilt auch für ungerichtete Graphen , und dies wurde zuvor diskutiert. Eine vielleicht interessantere Frage wäre, ob bekannt ist, dass dies hart ist.

A P X

$APX$

Antworten:

Der # P-Vollständigkeitsnachweis für das Zählen einfacher st-Pfade in ungerichteten und gerichteten Diagrammen ist zu finden in:

Leslie G. Valiant: Die Komplexität von Aufzählungs- und Zuverlässigkeitsproblemen . SIAM J. Comput. 8 (3): 410-421 (1979)

Aus dem Papier:

...
4. Einige # P-vollständige Probleme
...
14. ST-WEGE (dh SELBSTVERMEIDENDE WEGE) (gerichtet oder ungerichtet)
Eingabe: Output: Anzahl der (gerichteten) Pfade von bis , die jeden Knoten höchstens einmal besuchen. ... $G; s,t \in V$
$s$ $t$

Marzio De Biasi
quelle