Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I've a graph whose edges are weighted by probabilities, perhaps all equal. I would like to compute the overall probability of traveling between vertices x and y in the graph after I delete each edge vw with probability 1-p(vw). In other words, I'm trying to understand the probability that a self-avoiding walk goes from v to w. I cannot simply look at powers of the weighted adjacency matrix because this includes cycles.

I've gleaned from the self-avoiding walks literature that computing this probability should be NP-complete, although maybe I've miss-understood something there. Approximation algorithms might exist however. Anyone seen one?

I could imagine some recent-path-dependent ring-like object that when used in the adjacency matrix power operation eliminates counting short cycles. If the probabilities were low enough, this might produce a reasonable approximation with sane running time, although other properties of the graph might enter into the picture too.

share|improve this question
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.