11
$\begingroup$

Given the fact that $s$-$t$ path enumeration is a #P-complete problem, could there be efficient methods that compute (or at least approximate) the average length of $s$-$t$ path without enumerating them? What if paths are allowed to revisit vertices?

Relevant results on special graphs could also be helpful.

$\endgroup$
  • 1
    $\begingroup$ If paths are allowed to revisit vertices, then a non-simple $s-t$ path implies that there is no average length, as the length will tend to infinity. $\endgroup$ – Shaull Apr 8 '13 at 18:31
  • $\begingroup$ @Shaull, you are right. I was thinking of the hitting time of a random walk from $s$ to $t$. But the average length does tend to infinity without further constraints. $\endgroup$ – liuyu Apr 8 '13 at 18:42
  • $\begingroup$ this seems to be very advanced, recommend migrate to cstheory $\endgroup$ – vzn Apr 9 '13 at 4:10
  • $\begingroup$ If I understand right, this question might be of interest to you for a special graph. $\endgroup$ – Juho Apr 9 '13 at 4:29
  • 1
    $\begingroup$ seems like this might be related to max network flow? also note for small world graphs and various other graphs with some symmetry, it will tend toward the average path length. a fairly natural algorithm might be to randomly sample shortest $s$-$t$ paths and look at the standard deviation of results. $\endgroup$ – vzn Apr 10 '13 at 2:22
3
$\begingroup$

calculating/estimating/approximating the average path length has been studied for some random graph models including the Erdos-Renyi model and the Barabasi-Albert scale free networks, and also the Strogatz small world graphs which may be suitable as approximations for your graphs. [it would be better if you could narrow down/detail some nature/characteristics of the graphs you're studying.]

$\endgroup$
  • $\begingroup$ Thanks for the comment and the references. I came up with this problem when trying to model the workload of a query processing system with probabilistic graph. The graph model does have some unique properties that lead me to believe that there might be an approximation of the average length $s$-$t$ paths. As suggested in your comment, random sampling does give an approximation. Problem is that it does not give a guaranteed upper bound of the approximation, except the length of the longest $s$-$t$ path. Worse still, computing the longest $s$-$t$ path itself is a NP-complete problem. $\endgroup$ – liuyu Apr 10 '13 at 7:27

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.