I have encountered an interesting problem that I couldn't find any references to solve:

Determine the smallest subset of nodes that need to be removed from an undirected graph to make it a tree.

Obviously when a node is removed, the edges connecting to it are also removed.

Any help would be very much appreciated. Thank you in advance!

  • $\begingroup$ To make it a forest instead of a tree, your problem is the feedback vertex set problem. Is this what you need, or do you specifically want the remaining induced subgraph to be a tree? $\endgroup$ – M.Monet Aug 7 '19 at 23:36
  • 3
    $\begingroup$ To make it a tree (i.e connected and acyclic) is sometimes studied under the name Tree Deletion Set. It is NP-hard, much harder to approximate than Feedback Vertex Set, but can be shown to be FPT using the same ish techniques as for Feedback Vertex Set $\endgroup$ – daniello Aug 8 '19 at 5:47
  • $\begingroup$ @M.Monet Exactly what I was looking for! Thank you so much! Please post this as an answer so that I can accept. $\endgroup$ – Khue Aug 8 '19 at 9:55
  • $\begingroup$ @daniello Nice! In my application, a forest is sufficient, but indeed, a tree is preferred. Your comment and M.Monet's combined is a perfect answer! Thanks. $\endgroup$ – Khue Aug 8 '19 at 9:59

Your Answer

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

Browse other questions tagged or ask your own question.