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.

Improve this question
$\endgroup$
5
  • 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
    Commented Apr 8, 2013 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
    Commented Apr 8, 2013 at 18:42
  • $\begingroup$ this seems to be very advanced, recommend migrate to cstheory $\endgroup$
    – vzn
    Commented Apr 9, 2013 at 4:10
  • $\begingroup$ If I understand right, this question might be of interest to you for a special graph. $\endgroup$
    – Juho
    Commented Apr 9, 2013 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
    Commented Apr 10, 2013 at 2:22

1 Answer 1

Reset to default
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.]

Improve this answer
$\endgroup$
1
  • $\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
    Commented Apr 10, 2013 at 7:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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