independent set of vertices in a directed graph

Question

I'm trying to prove the following statement:

Every directed graph $G$ has an independent set $S$ such that any other vertex in G can be reached with a directed path of length $\leq 2$ from a vertex in $S$.

So far, I've tried removing a vertex $v$ from the graph and considering cases where the vertex is in $S$, $A = \{ \text{the set of vertices 1 away from } S \}$ or $B = \{ \text{the set of vertices 2 away from } S \}$. But I'm not getting anywhere.

Answer 1

In the situation where $G$ is undirected, any maximal independent set $S$ has this property. If $v$ is distance at least $2$ from $S$ then $S \cup \{v\}$ is independent and larger than $S$.

In the directed situation, this motivates you to take a maximal independent set $S$ as the starting point. We then proceed by induction on the number of vertices (the base case(s) are easy). Recall that in the underlying undirected graph, all vertices are distance at most $1$ from a maximal independent set.

Given $v \in V(G) \setminus S$ either there is an edge $S \to v$ (which is good). Or all the edges point $v \to S$ (bad). Throw together these bad vertices in the set $T$. By induction, we can choose an independent set $T'$ in $T$ with the desired property (for the subgraph induced by $T$). Let $U$ be the set of $u \in S$ such that there is an edge $v \to u$ with $v \in T'$.

Now let $S' = S \setminus U \cup T'$. Then first of all, $S'$ is idependent.

Let $a, b \in S'$. If $a, b \in S$ then $a, b$ have no edges between them by independence of $S$. If $a \in S$ but $b \notin S$ (or vice versa) then there are no edges between $a$ and $b$ by definition of $T$ and $U$. Otherwise $a, b \in T'$ and again there are no edges between them by independence of $T'$.

Does $S'$ satisfy the conditions?

Let $w \in V(G)$. If $w \in S'$ we are done. Next, if $w$ is not in $S'$ and not in $T$ then there is an edge $u \to w$ with $u \in S$. If $u \in U$ then there is a path $v \to u \to w$ with $v \in T'$. Otherwise, $u \in S'$ and $u \to w$ is a path $S' \longrightarrow w$ of length $1$. Finally, if none of the above happen then $w \in T \setminus T'$ and, by definition of $T'$, there is a path $T' \longrightarrow w$ of length $\le 2$. In all cases, there is a path $S' \longrightarrow w$ of length $\le 2$.