Given a directed tree $T = (V, E)$, we need to find a set of vertices $A \subseteq V$ such that for every two vertices $v,u \in A$ either there is no path between them or the path between them is of length at least 3. Furthermore, $A$ should contain the maximum number of vertices.
The above is an exercise in my homework. "A directed tree" means a rooted tree where all edges are directed away from the root. Note that a vertex in $T$ might have more than 2 children.
We can use dynamic programming to compute such a set for the subtree rooted at each vertex of $T$. However, I found a simple greedy algorithm.
- Create an empty set $A$.
- As long as $V\neq \emptyset$, repeat the following action.
- Add all leaves to $A$.
- Remove their parents and their grandparents from $V$ (and the edges that are connected to them from $E$).
- Return $A$.
It's easy to verify that all vertices added satisfy the path separating condition.
I believe that the number of all vertices added is optimal. It is indeed true in all cases that I have tried. Is it true? Does the greedy algorithm always work? I would like to see a proof for it.