Paste: graph theory question

Author: slava
Mode: text
Date: Mon, 3 Aug 2009 15:49:09
Plain Text |
Suppose I have a graph G = (V,E). There might be multiple edges between two vertices.

Given a set of edges X, I want to find the set of vertices W in V such that for w in W, there is a cycle that starts and ends at w with at least one edge of the cycle contained in X.

Annotation: Graph comments

Author: anonymous
Mode: text
Date: Mon, 3 Aug 2009 16:09:08
Plain Text |
it doesn't matter in a cycle if something "starts or ends" it.

If you have another idea of what starts or ends mean, then encode it. Otherwise, don't worry, you just want w to be part of a cycle of the edges in X 

Annotation: solution, maybe

Author: littledan
Mode: factor
Date: Mon, 3 Aug 2009 17:31:56
Plain Text |
1. Calculate the strongly connected components of the graph. This partitions the set of edges
2. Find the components for each member of X
3. Take their union, and get the set of vertices that any of the edges touch

You can get strongly connected components with Tarjan's algorithm:
Tarjan's algorithm seems to allow partial computation of SCCs: it's easy to just calculate the components which go through X, and not incur cost for the other components.

Annotation: Not sure

Author: Not sure
Mode: factor
Date: Mon, 3 Aug 2009 20:08:27
Plain Text |
Not sure that's right littledan but I don't have a better solution :-)

New Annotation