2
$\begingroup$

Given an undirected graph with some cycles:

enter image description here

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

enter image description here

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.)
$\endgroup$
0
4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ FVS is about directed graphs. $\endgroup$ – vonbrand May 10 at 22:33
  • $\begingroup$ @vonbrand You are wrong. FVS can be defined for either directed or undirected graphs. $\endgroup$ – Juho May 11 at 4:36
-2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ They ask about removing vertices, not edges $\endgroup$ – user114966 May 10 at 23:03

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.