1
$\begingroup$

Let $U$ be the set of elements and $S$ be the subset collections. There exists a tree $T$ that each node is corresponding to an element in $U$. And for every subset $s$ in $S$, $V(T) \bigcap s $ is a path of T.

And I want to find a minimum set $Z$, where $Z \subset S$, and $\forall u \in U, \exists z \in Z$ s.t $u \in z$.


This problem can also be rephrased to giving a tree with a set of paths $P$ on the tree, and I want to select a minimal set of paths subset to $P$ that covers each node on that tree at least once.

Can this be done in polynomial time?

$\endgroup$
3
  • 2
    $\begingroup$ I might rephrase the question: You have a tree with a given set of paths $P$ on that tree. You want to select a minimal set of nodes that covers each path at least once. Is that accurate? $\endgroup$
    – TickaJules
    Dec 7 '21 at 17:49
  • 1
    $\begingroup$ Thanks for your comment. I think I can rephrase this to: I have a tree with a set of paths $P$ on the tree, and I want to select a minimal set of paths subset to $P$ that cover each node on that tree at least once. $\endgroup$
    – Zhang Yu
    Dec 8 '21 at 3:48
  • $\begingroup$ What is your question? I don't see a question here. We are a question-and-answer site, so we require you to articulate a specific question about your situation. A question usually ends in "?". We expect you to state your question in the body of the post. The title should be a short summary. The body of the post needs to make sense on its own. Please edit your question to make it clearer what you are asking. Don't put clarifications in the comments -- revise the question so it contains all relevant information, and people don't need to read the comments to understand what is being asked. $\endgroup$
    – D.W.
    Dec 11 '21 at 9:58