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.