1
$\begingroup$

As the title says, I'm trying to solve the question where:

Input: A directed tree $T = (V, E)$.

Output: The maximal subset $A \subseteq V$ of vertices such that there doesn't exist any two vertices $u, v \in A$ that have a directed path between of distance $2$ or less.

I thought of starting to append all of the leaves of the tree to the set $A$ and then start going upwards towards the root of the tree. However, I can't seem to solve the question.

$\endgroup$
6
  • $\begingroup$ I suggest trying dynamic programming. See cs.stackexchange.com/tags/dynamic-programming/info. Also, if we replace 2 with 1, this sounds like the problem of finding an independent set in a tree, so perhaps research methods for that and see if you can generalize that. $\endgroup$
    – D.W. ♦
    Jan 30 at 18:05
  • $\begingroup$ Thank you! After thinking about the question, I believe that it can also be done using a Greedy approach where each time you add the leaves of the tree to the set A and then delete these leaves and their parent and grandparents from T, and then keep repeating the process. $\endgroup$
    – Salty Champ
    Jan 31 at 2:01
  • $\begingroup$ @SaltyChamp, if you were able to solve this problem on your own, I think it's best for you to answer your own question as this is encouraged. This is to help others who might stumble the same or related problem on the future. See cs.stackexchange.com/help/self-answer. $\endgroup$
    – Russel
    Jan 31 at 3:11
  • $\begingroup$ I would first build a new graph B with the same vertices as A but with an edge (u, v) in B iff u and v are distance at most 2 in A. Then, look for a maximal independent set in B. Note that your question is a bit wrong: you ask for "the maximal set". In general, there are several different maximal sets (and they might not have the same number of vertices!) $\endgroup$
    – Stef
    Jan 31 at 9:42
  • $\begingroup$ Thank you all. After thinking about it, it could be solved in many different ways as you all said. The easiest way was the greedy approach. It could also be solved using dynamic programming (I'll post the answer using Dynamic Programming as well) however, it's much more complicated. $\endgroup$
    – Salty Champ
    Feb 5 at 14:52

1 Answer 1

Reset to default
2
$\begingroup$

This question can be solved in 2 different approaches. The first approach is using Dynamic Programming, and the second approach this using Greedy algorithm approach.

  • Greedy Approach:

$Algorithm$$:$

  1. Create an empty set $A$.
  2. Append all leaves $l \in T$ to $A$.
  3. Remove all the leaves $l$, their parents, and their grandparents from $T$.
  4. Repeat steps 2 and 3.

The correctness of this algorithm is classic. We can always prove that every leaf $l \in T$ is always in the set $A$.

This can be done using 'Proof by Contradiction'.

Assume that $A_{OPT}$ is the maximal set of nodes that suffice the condition of the question. Denote the cardinality of $|A_{OPT}| = c$. Assume by contradiction that there exist a leaf $l' \notin A$.

Consider the case where $l' \notin A_{OPT}$, $parent(l') \notin A_{OPT}$, and $grandParent(l') \notin A_{OPT}$. Then, we can append $l'$ to the set $A_{OPT}$ and get that $|A_{OPT}| = c + 1$, thus contradicting the assumption that $A_{OPT}$ was the maximal set of vertices that suffice the question's condition.

Consider the case where one of its grandparents is in A. Thus, we could remove its grandparent from $A_{OPT}$ and append $l'$ to $A_{OPT}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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