Let $G=(V,E)$ be a directed graph, i.e. $V$ is a finite set and $E\subseteq V\times V$.

We call a subset $J\subseteq V$ extending if for every $v\in V\setminus J$ there is a directed path from some vertex $j\in J$ to $v$.

Is there a polynomial-time algorithm to find an extending subset of minimal size?


1 Answer 1


There is a linear time algorithm.

Contract all strongly connected components, then you get a DAG. Find all the source vertex in the DAG. For each source vertex in the DAG, pick a single vertex from the strongly connected component represented by the source vertex.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.