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

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

<p>Obviously when a node is removed, the edges connecting to it are also removed.</p>

<p>Any help would be very much appreciated.
Thank you in advance!</p>

CC BY-SA 4.0
2019-08-07T23:36:42.770Z
To make it a forest instead of a tree, your problem is the [feedback vertex set problem](https://en.wikipedia.org/wiki/Feedback_vertex_set). Is this what you need, or do you specifically want the remaining induced subgraph to be a tree?
M.Monet
CC BY-SA 4.0
2019-08-08T05:47:35.937Z
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
CC BY-SA 4.0
2019-08-08T09:55:37.130Z
@M.Monet Exactly what I was looking for! Thank you so much! Please post this as an answer so that I can accept.
f10w
CC BY-SA 4.0
2019-08-08T09:59:46.947Z
@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.
f10w
<ds.algorithms><graph-theory><graph-algorithms>
Algorithm for computing the smallest subset of nodes to remove from a graph to make it a tree
f10w
# Algorithm for computing the smallest subset of nodes to remove from a graph to make it a tree

(Asked by: username_0 on 2019-08-07)

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!

**Tags:** ds.algorithms, graph-theory, graph-algorithms
> **Comments:**
> **username_1**: To make it a forest instead of a tree, your problem is the [feedback vertex set problem](https://en.wikipedia.org/wiki/Feedback_vertex_set). Is this what you need, or do you specifically want the remaining induced subgraph to be a tree?  
> **username_2**: 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  
> **username_0**: @M.Monet Exactly what I was looking for! Thank you so much! Please post this as an answer so that I can accept.  
> **username_0**: @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.  

---

## 0 answers

