<p>There is a linear time algorithm.</p>

<p>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.</p>

CC BY-SA 3.0
2015-10-28T10:58:56.820Z
2015-10-28T10:58:56.820Z
Chao Xu
<p>Let $G=(V,E)$ be a directed graph, i.e. $V$ is a finite set and $E\subseteq V\times V$.</p>

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

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

<graph-theory><graph-algorithms>
Minimal-size extending set in a directed graph
Dominic van der Zypen
# Minimal-size extending set in a directed graph

(Asked by: username_0 on 2015-10-28)

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?

**Tags:** graph-theory, graph-algorithms


---

## 1 answers

### Answer by username_1 on 2015-10-28. Score: 7 | Accepted answer

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.


---

