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.


Your Answer

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

Browse other questions tagged or ask your own question.