How many vertices should be disconnected to make a graph acyclic?

Question

Given an undirected graph with some cycles:

we can "disconnect" the red vertex by adding a separate vertex to each of the edges adjacent to it:

In this case, disconnecting a single vertex makes the graph acyclic.

My questions:

• What is a term for the smallest number of vertices that must be "disconnected" like this, to make the graph acyclic?
• What is an algorithm for finding a smallest such set of vertices?

(I found some related concepts, but they are different:

• The circuit rank is the number of edges that have to be removed to make the graph acyclic; it always equals the number of edges minus the number of vertices plus the number of components.
• The vertex connectivity is the number of vertices that have to be removed to make the graph disconnected.)

Answer 1

A set of vertices whose removal makes the graph acyclic is called a feedback vertex set (FVS). What you seem to be doing is finding the smallest FVS, subdividing all edges incident to each vertex in the FVS, and finally deleting the vertices in the FVS.

Computing the smallest FVS is NP-hard, but it admits 2-approximation.

Answer 2

If you have a connected graph, e.g. Prim's algorithm gives you a spanning tree (no cycles).