0
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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? $\endgroup$
    – D.W.
    Jan 7 at 21:57
  • $\begingroup$ cs.stackexchange.com/q/59964/755 $\endgroup$
    – D.W.
    Jan 18 at 4:05

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.