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

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.

• Can you tell us where you encountered this task, and credit the original source? We have a systematic guide on how to approach dynamic programming problems: cs.stackexchange.com/tags/dynamic-programming/info. Please follow the steps listed there and edit the question to show us your progress. Can you solve the problem for any special cases, such as for binary trees?
– D.W.
Jan 7 at 21:57
• cs.stackexchange.com/q/59964/755
– D.W.
Jan 18 at 4:05

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.