Feedback vertex set

Removing the red vertices and all edges connected to them leaves the graph with no cycles. Thus, the set of vertices is a feedback vertex set (FVS) of the graph. There is no smaller FVS, so it is a minimum FVS and the FVS number is its size, 3.

In the mathematical discipline of graph theory, a feedback vertex set (FVS) of a graph is a set of vertices whose removal leaves a graph without cycles ("removal" means deleting the vertex and all edges adjacent to it). Equivalently, each FVS contains at least one vertex of any cycle in the graph. The feedback vertex set number of a graph is the size of a smallest FVS. Whether there exists a feedback vertex set of size at most k is an NP-complete problem; it was among the first problems shown to be NP-complete. It has wide applications in operating systems, database systems, and VLSI chip design.

This page is issued from Wikipedia. The text is available under Creative Commons Attribution-Share Alike 4.0 unless otherwise noted. Additional terms may apply for the media files.