3
$\begingroup$

Given a connected graph and two nodes s and t, there can be many different simple paths (without cycles) from s to t. Is there an efficient algorithm to find the average length of these paths?

$\endgroup$
  • 1
    $\begingroup$ Are you looking for exact algorithms or are you fine with approximations of the average length? By intuition, I would say that calculating the exact average length is NP-hard (seeing as checking if there exists a Hamiltonian path is already NP-hard), but approximating it to within $[(1-\varepsilon)L, (1+\varepsilon)L]$ (where L is the solution) might be possible efficiently. $\endgroup$ – SmeltQuake Jul 26 at 14:03
  • $\begingroup$ @SmeltQuake Anything would be interesting. Can Hamiltonian circuit/path really be reduced to this problem? You can certainly determine if there is at least one path between s and t in poly time. $\endgroup$ – Anush Jul 26 at 14:25
  • $\begingroup$ I do not know if Hamiltonian path can be reduced to this problem. This is just an intuition about why I think the exact problem is probably NP-hard: If you cannot even determine if there exists a path of length n, calculating the average over all lengths (which also sums over the paths of length n) is probably also hard. $\endgroup$ – SmeltQuake Jul 26 at 14:30
  • $\begingroup$ @SmeltQuake I understood your intuition but the reduction, if it exists, is not clear to me. Hopefully someone here will see it more clearly. $\endgroup$ – Anush Jul 26 at 14:32
3
$\begingroup$

I guess you already know that a polynomial algorithm for counting the number of simple paths between two nodes would imply P=NP, this result is due to Valiant (The complexity of enumeration and reliability problems, 1979).

Now imagine, expecting to discover a contradiction, that you could compute $\text{avg}(G, u, v)$ in polynomial time.

Let $G+l$ be the graph resulting from adding a simple path of length $l$ between $u$ and $v$ in $G$. This new path is made of $l-1$ new nodes and it does not interfere with any previous path from $u$ to $v$, provided $l \geq 2$.

Then, $\text{avg}(G+3,u,v) - \text{avg}(G+2,u,v)$ = $1/(\#\text{Paths}(G,u,v)+1)$, from which you can get $\#\text{Paths}(G,u,v)$ in polynomial time. But we know this cannot be expected to be done in polynomial time, a contradiction.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you. Do you know a reference for the result of Valiant? $\endgroup$ – Anush Jul 26 at 19:02
  • 1
    $\begingroup$ "The complexity of enumeration and reliability problems" L. Valiant 1979. There are free PDFs online, sorry I can't properly cite it, I won't have my computer with me today. $\endgroup$ – Bernardo Subercaseaux Jul 26 at 19:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.