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

16

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

Ich würde erwarten, dass das Problem # -vollständig ist, konnte aber keine genaue Referenz finden. 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).PPP

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. APX
RB

Antworten:

19

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. ...s tG;s,tV
st

Marzio De Biasi
quelle