Näherung zum Zählen der Anzahl einfacher

Mir wurde gesagt, dass es einige gute polynomielle Zeitalgorithmen gibt, um die Anzahl einfacher Pfade in einem gerichteten Graphen von einem gegebenen Startscheitelpunkt zu einem gegebenen Endscheitelpunkt t zu approximieren . Kennt jemand eine gute Referenz zu diesem Thema?$s$$t$

Hintergrund: Das Zählen der genauen Anzahl der Pfade in einem allgemeinen Diagramm ist # P-vollständig, es können jedoch Polynomzeit-Annäherungen für das Problem existieren. Ich interessiere mich besonders für zufällige Annäherungen.

Danke im Voraus.

Dieses Problem sollte NP-hart sein, indem die maximale Länge der st-Pfade verringert wird.

$k$$C_{\ell}$$\ell$$k^\ell C_{\ell}$$k$$C_{\ell_{max}}=1$