# Algorithm for computing the smallest subset of nodes to remove from a graph to make it a tree

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!

• 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? – M.Monet Aug 7 '19 at 23:36
• 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 – daniello Aug 8 '19 at 5:47
• @M.Monet Exactly what I was looking for! Thank you so much! Please post this as an answer so that I can accept. – Khue Aug 8 '19 at 9:55
• @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. – Khue Aug 8 '19 at 9:59