I've faced this question as an exercise in my homework and I hope for help.

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$ that have a path between them, the length of the path is greater than 2. $A$ has to contain the maximum number of vertices that satisfies what's written above.

So the point here is that if there are two vertices $v,u\in A$ and there isn't a path between them then it's still legal vertices, the condition here is that if there is a path we need its length to be at least 3.

I think the approach here is Dynamic Programming since the graph given is a tree so we don't have to check if there's a path between vertex and its children because is what the tree implements, meaning there's no need to use $BFS$ or $DFS$ or any of the known algorithms.

Note: The tree hasn't to be a binary tree, so every vertex can have multiple children and not only 2

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.

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$ that have a path between them, the length of the path is greater than 2. $A$ has to contain the maximum number of vertices that satisfies what's written above.

So the point here is that if there are two vertices $v,u\in A$ and there isn't a path between them then it's still legal vertices, the condition here is that if there is a path we need its length to be at least 3.

I think the approach here is Dynamic Programming since the graph given is a tree so we don't have to check if there's a path between vertex and its children because is what the tree implements, meaning there's no need to use $BFS$ or $DFS$ or any of the known algorithms.

Note: The tree hasn't to be a binary tree, so every vertex can have multiple children and not only 2

I've faced this question as an exercise in my homework and I hope for help.

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$ that have a path between them, the length of the path is greater than 2. $A$ has to contain the maximum number of vertices that satisfies what's written above.

So the point here is that if there are two vertices $v,u\in A$ and there isn't a path between them then it's still legal vertices, the condition here is that if there is a path we need its length to be at least 3.

I think the approach here is Dynamic Programming since the graph given is a tree so we don't have to check if there's a path between vertex and its children because is what the tree implements, meaning there's no need to use $BFS$ or $DFS$ or any of the known algorithms.

Note: The tree hasn't to be a binary tree, so every vertex can have multiple children and not only 2

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$ that have a path between them, the length of the path is greater than 2.

So the point here is that if there are two vertices $v,u\in A$ and there isn't a path between them then it's still legal vertices, the condition here is that if there is a path we need its length to be at least 3.

I think the approach here is Dynamic Programming since the graph given is a tree so we don't have to check if there's a path between vertex and its children because is what the tree implements, meaning there's no need to use $BFS$ or $DFS$ or any of the known algorithms.

Note: The tree hasn't to be a binary tree, so every vertex can have multiple children and not only 2

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$ that have a path between them, the length of the path is greater than 2. $A$ has to contain the maximum number of vertices that satisfies what's written above.

So the point here is that if there are two vertices $v,u\in A$ and there isn't a path between them then it's still legal vertices, the condition here is that if there is a path we need its length to be at least 3.

I think the approach here is Dynamic Programming since the graph given is a tree so we don't have to check if there's a path between vertex and its children because is what the tree implements, meaning there's no need to use $BFS$ or $DFS$ or any of the known algorithms.

Note: The tree hasn't to be a binary tree, so every vertex can have multiple children and not only 2