[Solved]: Finding all (weighted) cycles through a given vertex

Problem Detail: 

For a connected undirected graph $G$, given a particular vertex $v$, is there a known (efficient) algorithm to find all simple cycles in $G$ that contain $v$?

In my case, I have weights for every edge. Ideally I'd like to be able to compute, for every $v \in V(G)$, the product of the edge weights over all cycles that go through $v$. Doing this to some level of approximation would still be very helpful.

Is this a known result? Any pointers would be very helpful.

Asked By : user31016

Answered By : D.W.

Enumerating all cycles might take exponential time

There cannot be any efficient algorithm for enumerating all cycles that contain $v$. There could be exponentially many algorithms that go through $v$. Therefore, any algorithm for enumerating all cycles could potentially take exponential time.

If the graph is very small and efficiency is not important, you could enumerate all cycles that go through $v$ using depth-first search or breadth-first search starting from $v$. Or, you could use Johnson's algorithm: see Find the Simple Cycles in a Directed Graph.

You can't compute the cycle-sums you want efficiently

Now for some more bad news. You want to compute the sum over all simple cycles, of the sum of edge-weights in the cycle. Unfortunately, this cannot be done efficiently, either. This problem is #P-hard, which means there is no hope for a polynomial-time algorithm for it.

Here's a proof of #P-hardness, by reduction from the problem of counting the number of simple paths from $s$ to $t$ (which is a #P-complete problem). Let $G$ be a graph, and vertices $s$ and $t$ be specified. Add new vertices $u,v$ and edges $(t,u)$, $(u,v)$, and $(v,s)$. Label each edge with the weight 0, except that the edge $(u,v)$ will be labelled with weight 1. Now suppose you had an efficient algorithm to compute the sum over all simple cycles, of the edge-weights in that cycle, for the resulting graph. Then its output would be exactly the number of simple cycles in this graph, or equivalently, exactly the number of simple paths from $s$ to $t$ in $G$. Thus, any polynomial-time algorithm for your problem would immediately imply a polynomial-time algorithm for counting the number of simple paths from $s$ to $t$; since the latter is #P-hard, your problem must be #P-hard, too.

For more details on #P-hardness of counting simple paths, see, e.g., http://cstheory.stackexchange.com/q/20246/5038, http://stackoverflow.com/a/5570751/781723, How hard is counting the number of simple paths between two nodes in a directed graph?.

So, the bad news is: there is no efficient algorithm for your problem, and I can prove it.

Time to look for some alternative: e.g., find some way to avoid solving your problem, or hope that your graph will be extremely small (so that exponential-time algorithms are acceptable), or look for an approximation algorithm, or something. But you're not going to find an algorithm to solve your problem that is efficient on general graphs.

Other miscellaneous comments

It's important to phrase your question so you ask for what you really want. It sounds like what you really want to know is whether it's possible to compute the sum of the edge weights over all cycles that go through $v$. If that's what you really want, don't ask whether it's possible to enumerate all cycles through $v$; ask whether there's an algorithm to do what you really want. There might be a better way to do what you really want, without enumerating all cycles.

(Incidentally, if you are summing over all cycles of any length, it is important to restrict your sum to simple cycles. If you don't restrict to simple cycles, then there are infinitely many cycles and the sum is going to be either $+\infty$ or $-\infty$.)

---

For instance, it is possible to efficiently compute the sum of the cycle weights over all cycles of length $k$ (not necessarily simple) that go through $v$, where the weight of a cycle is the product of the edges in $v$. Here's how.

Here's the key idea. Let the matrix $M$ represent the adjacency matrix for the graph, i.e., $M_{i,j}$ holds the weight on the edge $(i,j)$, or $0$ if there is no such edge. Let $e_i$ denote the vector that is $1$ in its $i$th component and $0$ in all other positions. Let $x = M^k e_v$. Then $x_j$ is a sum, over all paths from $v$ to $j$ of length $k$, of the products of the weights along each such path. Thus, $x_v$ is a sum of the weights of all of the cycles of length $k$ that go through $v$. The running time is polynomial.

Unfortunately, this is not restricted to simple cycles, so it is not what you want. Also, this approach ends up multiplying the edge weights along a single cycle, rather than adding them, so it is also not what you want for that reason. Nonetheless, it shows how some problems of this form can potentially be solved in polynomial time without enumerating all cycles.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/26271