Find most vertices in a directed tree where no path of length less than 3 connects any pair

Question

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.

1. Create an empty set $A$.
2. As long as $V\neq \emptyset$, repeat the following action.
   1. Add all leaves to $A$.
   2. Remove their parents and their grandparents from $V$ (and the edges that are connected to them from $E$).
3. 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.

Answer 1

Yes, the greedy algorithm (you described) works.

Given a directed graph, call a subset of its vertices "a 3-separated set" if there isn't a path of length less than 3 between any pair of vertices among them. Call a 3-separated set a 3-separated-max set if it contains the maximum number of vertices. The problem is to find a 3-separated-max set in a directed tree.

Here is a proof of the greedy algorithm works.

Proof. It is enough to prove that there is a 3-separated-max set that contains all leaves.

Consider $S$, a 3-separated-max sets that contains the most number of leaves. It is enough to prove $S$ contains all leaves.

Suppose $S$ does not contain all leaves. Let leaf $l\not\in S$. Consider all ancestors of $l$. There are two cases.

• $S$ contains no ancestor of $l$. Then $S\sqcup\{l\}$ is a 3-separated set that has one more vertex than $S$, which is impossible.
• $S$ contains at least one ancestors of $l$. Let $\alpha$ be the ancestor in $S$ that is nearest to $l$. We can check easily that $(S\setminus\{\alpha\})\sqcup\{l\}$ is a 3-separated-max set that has one more leaf than $S$, which is impossible.

Since all cases are impossible, it cannot happen that $S$ does not contain all leaves, i.e., $S$ does contain all leaves. $\checkmark$

---

Exercise (easy). Generalize $3$ to any positive integer.