# 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.

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

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:
http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_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.

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