# A Special Case of Set Cover Problem: Covering Nodes of Tree using Paths [closed]

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?

• 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? Dec 7 '21 at 17:49
• 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. Dec 8 '21 at 3:48