Feedback vertex set
Encyclopedia
In the mathematical
discipline of graph theory
, a feedback vertex set of a graph
is a set of vertices whose removal leaves a graph without cycles
. In other words, each feedback vertex set contains at least one vertex of any cycle in the graph.
The feedback vertex set problem is an NP-complete
problem in computational complexity theory
. It was among the first problems shown to be NP-complete
. It has wide applications in operating system
, database system
, genome assembly, and VLSI chip design.
is as follows:
The graph
that remains after removing 
from 
is an induced forest (resp. an induced directed acyclic graph
in the case of directed graph
s). Thus, finding a minimum feedback vertex set in a graph is equivalent to finding a maximum induced forest (resp. maximum induced directed acyclic graph in the case of directed graph
s).
s is NP-complete
. The problem remains NP-complete on directed graphs with maximum in-degree and out-degree two, and on directed planar graphs with maximum in-degree and out-degree three. Karp's reduction also implies the NP-completeness of the feedback vertex set problem on undirected graphs, where the problem stays NP-hard on graphs of maximum degree
four.
Note that the problem of deleting edges to make the graph cycle-free is equivalent to finding a minimum spanning tree
, which can be done in polynomial time. In contrast, the problem of deleting edges from a directed graph
to make it acyclic
, the feedback arc set
problem, is NP-complete, see .
, which directly follows from the APX-completeness of the vertex cover problem
, and the existence of an approximation preserving L-reduction
from the vertex cover problem to it. The best known approximation on undirected graphs is by a factor of two.
, the size of a minimum feedback vertex set is within a logarithmic factor of the maximum number of vertex-disjoint cycles in the given graph.
s, feedback vertex sets play a prominent role in the study of deadlock
recovery. In the wait-for graph
of an operating system, each directed cycle corresponds to a deadlock situation. In order to resolve all deadlocks, some blocked processes have to be aborted. A minimum feedback vertex set in this graph corresponds to a minimum number of processes that one needs to abort .
Furthermore, the feedback vertex set problem has applications in VLSI chip design (cf. ) and genome assembly.
A1.1: GT7, pg.191.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
discipline of graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, a feedback vertex set of a graph
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
is a set of vertices whose removal leaves a graph without cycles
Cycle (graph theory)
In graph theory, the term cycle may refer to a closed path. If repeated vertices are allowed, it is more often called a closed walk. If the path is a simple path, with no repeated vertices or edges other than the starting and ending vertices, it may also be called a simple cycle, circuit, circle,...
. In other words, each feedback vertex set contains at least one vertex of any cycle in the graph.
The feedback vertex set problem is an NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
problem in computational complexity theory
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
. It was among the first problems shown to be NP-complete
Karp's 21 NP-complete problems
One of the most important results in computational complexity theory was Stephen Cook's 1971 demonstration of the first NP-complete problem, the boolean satisfiability problem...
. It has wide applications in operating system
Operating system
An operating system is a set of programs that manage computer hardware resources and provide common services for application software. The operating system is the most important type of system software in a computer system...
, database system
Database system
A database system is a term that is typically used to encapsulate the constructs of a data model, database Management system and database....
, genome assembly, and VLSI chip design.
Definition
The decision problemDecision problem
In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem...
is as follows:
- INSTANCE: An (undirected or directed) graphGraph (mathematics)In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
and a positive integer 
. - QUESTION: Is there a subset
with 
such that 
with the vertices from 
deleted is cycle-freeCycle (graph theory)In graph theory, the term cycle may refer to a closed path. If repeated vertices are allowed, it is more often called a closed walk. If the path is a simple path, with no repeated vertices or edges other than the starting and ending vertices, it may also be called a simple cycle, circuit, circle,...
?
The graph
that remains after removing from is an induced forest (resp. an induced directed acyclic graphDirected acyclic graph
In mathematics and computer science, a directed acyclic graph , is a directed graph with no directed cycles. That is, it is formed by a collection of vertices and directed edges, each edge connecting one vertex to another, such that there is no way to start at some vertex v and follow a sequence of...
in the case of directed graph
Directed graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
s). Thus, finding a minimum feedback vertex set in a graph is equivalent to finding a maximum induced forest (resp. maximum induced directed acyclic graph in the case of directed graph
Directed graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
s).
NP-hardness
showed that the feedback vertex set problem for directed graphDirected graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
s is NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
. The problem remains NP-complete on directed graphs with maximum in-degree and out-degree two, and on directed planar graphs with maximum in-degree and out-degree three. Karp's reduction also implies the NP-completeness of the feedback vertex set problem on undirected graphs, where the problem stays NP-hard on graphs of maximum degree
Degree (graph theory)
In graph theory, the degree of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice. The degree of a vertex v is denoted \deg. The maximum degree of a graph G, denoted by Δ, and the minimum degree of a graph, denoted by δ, are the maximum and minimum degree...
four.
Note that the problem of deleting edges to make the graph cycle-free is equivalent to finding a minimum spanning tree
Minimum spanning tree
Given a connected, undirected graph, a spanning tree of that graph is a subgraph that is a tree and connects all the vertices together. A single graph can have many different spanning trees...
, which can be done in polynomial time. In contrast, the problem of deleting edges from a directed graph
Directed graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
to make it acyclic
Directed acyclic graph
In mathematics and computer science, a directed acyclic graph , is a directed graph with no directed cycles. That is, it is formed by a collection of vertices and directed edges, each edge connecting one vertex to another, such that there is no way to start at some vertex v and follow a sequence of...
, the feedback arc set
Feedback arc set
In graph theory, a directed graph may contain directed cycles, a one-way loop of edges. In some applications, such cycles are undesirable, and we wish to eliminate them and obtain a directed acyclic graph . One way to do this is simply to drop edges from the graph to break the cycles...
problem, is NP-complete, see .
Exact algorithms
The corresponding NP optimization problem of finding the size of a minimum feedback vertex set can be solved in time O(1.7347n), where n is the number of vertices in the graph. This algorithm actually computes a maximum induced forest, and when such a forest is obtained, its complement is a minimum feedback vertex set. The number of minimal feedback vertex sets in a graph is bounded by O(1.8638n). The directed feedback vertex set problem can still be solved in time O*(1.9977n), where n is the number of vertices in the given directed graph. The parameterized versions of the directed and undirected problems are both fixed-parameter tractable.Approximation
The problem is APX-completeAPX
In complexity theory the class APX is the set of NP optimization problems that allow polynomial-time approximation algorithms with approximation ratio bounded by a constant...
, which directly follows from the APX-completeness of the vertex cover problem
Vertex cover
In the mathematical discipline of graph theory, a vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set....
, and the existence of an approximation preserving L-reduction
L-reduction
In computer science, in particular in the study of approximation algorithms, anL-reduction is a transformation of optimization problems which linearly preserves approximability features...
from the vertex cover problem to it. The best known approximation on undirected graphs is by a factor of two.
Bounds
According to the Erdős–Pósa theoremErdős–Pósa theorem
In the mathematical discipline of graph theory, the Erdős–Pósa theorem, named after Paul Erdős and Lajos Pósa, states that there is a function such for each positive integer , every graph either contains vertex-disjoint circuits or it has a feedback vertex set of vertices that intersects every...
, the size of a minimum feedback vertex set is within a logarithmic factor of the maximum number of vertex-disjoint cycles in the given graph.
Applications
In operating systemOperating system
An operating system is a set of programs that manage computer hardware resources and provide common services for application software. The operating system is the most important type of system software in a computer system...
s, feedback vertex sets play a prominent role in the study of deadlock
Deadlock
A deadlock is a situation where in two or more competing actions are each waiting for the other to finish, and thus neither ever does. It is often seen in a paradox like the "chicken or the egg"...
recovery. In the wait-for graph
Wait-For Graph
A Wait-For Graph in computer science is a directed graph used for deadlock detection in operating systems and relational database systems.In Computer Science, a system that allows concurrent operation of multiple processes and locking of resources and which does not provide mechanisms to avoid or...
of an operating system, each directed cycle corresponds to a deadlock situation. In order to resolve all deadlocks, some blocked processes have to be aborted. A minimum feedback vertex set in this graph corresponds to a minimum number of processes that one needs to abort .
Furthermore, the feedback vertex set problem has applications in VLSI chip design (cf. ) and genome assembly.
Research articles
- Ann Becker, Reuven Bar-Yehuda, Dan Geiger: Randomized Algorithms for the Loop Cutset Problem. J. Artif. Intell. Res. (JAIR) 12: 219-234 (2000)
- Jianer Chen, Fedor V. Fomin, Yang Liu, Songjian Lu, Yngve Villanger: Improved algorithms for feedback vertex set problems. J. Comput. Syst. Sci. 74(7): 1188-1198 (2008)
- Jianer Chen, Yang Liu, Songjian Lu, Barry O'Sullivan, Igor Razgon: A fixed-parameter algorithm for the directed feedback vertex set problem. J. ACM 55(5): (2008)
A1.1: GT7, pg.191.
- I. Razgon : Computing Minimum Directed Feedback Vertex Set in O*(1.9977n). In: Giuseppe F. Italiano, Eugenio Moggi, Luigi Laura (Eds.), Proceedings of the 10th Italian Conference on Theoretical Computer Science 2007, World Scientific, pp. 70–81 (author's version (pdf), preliminary full version (pdf)).
Textbooks and survey articles
- P. Festa, P.M. Pardalos, and M.G.C. Resende, Feedback set problems, Handbook of Combinatorial Optimization, D.-Z. Du and P.M. Pardalos, Eds., Kluwer Academic Publishers, Supplement vol. A, pp. 209–259, 2000. author's version (pdf)