Feedback vertex set

Last updated August 21, 2024

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 feedback vertex set. The minimum feedback vertex set problem 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.

Definition

The FVS decision problem is as follows:

INSTANCE: An (undirected or directed) graph

G=(V,E)

and a positive integer

k

.

QUESTION: Is there a subset

X\subseteq V

with

|X|\leq k

such that, when all vertices of

X

and their adjacent edges are deleted from

G

, the remainder is cycle-free?

The graph $G[V\setminus X]$ that remains after removing $X$ from $G$ is an induced forest (resp. an induced directed acyclic graph in the case of directed graphs). Thus, finding a minimum FVS in a graph is equivalent to finding a maximum induced forest (resp. maximum induced directed acyclic graph in the case of directed graphs).

NP-hardness

Karp (1972) showed that the minimum FVS problem for directed graphs 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.^[1]

Karp's reduction also implies the NP-completeness of the FVS problem on undirected graphs, where the problem stays NP-hard on graphs of maximum degree four. The FVS problem can be solved in polynomial time on graphs of maximum degree at most three.^[2]

Exact algorithms

The corresponding NP optimization problem of finding the size of a minimum feedback vertex set can be solved in time O(1.7347ⁿ), where n is the number of vertices in the graph.^[3] 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.8638ⁿ).^[4] The directed feedback vertex set problem can still be solved in time O*(1.9977ⁿ), where n is the number of vertices in the given directed graph.^[5] The parameterized versions of the directed and undirected problems are both fixed-parameter tractable.^[6]

In undirected graphs of maximum degree three, the feedback vertex set problem can be solved in polynomial time, by transforming it into an instance of the matroid parity problem for linear matroids.^[7]

Approximation

The undirected problem is APX-complete. This follows from the following facts.

The APX-completeness of the vertex cover problem;^[8]
The existence of an approximation preserving L-reduction from the vertex cover problem to it;
Existing constant-factor approximation algorithms.^[9]

The best known approximation algorithm on undirected graphs is by a factor of two.^[10]

By contrast, the directed version of the problem appears to be much harder to approximate. Under the unique games conjecture, an unproven but commonly used computational hardness assumption, it is NP-hard to approximate the problem to within any constant factor in polynomial time. The same hardness result was originally proven for the closely related feedback arc set problem,^[11] but since the feedback arc set problem and feedback vertex set problem in directed graphs are reducible to one another while preserving solution sizes,^[12] it also holds for the latter.

Bounds

According to the Erdős–Pósa theorem, 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.^[13]

Related concepts

Instead of vertices, one can consider a feedback edge set - a set of edges in an undirected graph, whose removal makes the graph acyclic. The size of a smallest feedback edge set in a graph is called the circuit rank of the graph. In contrast to the FVS number, the circuit rank can be easily computed: it is $|E|-|V|+|C|$ , where C is the set of connected components of the graph. The problem of finding a smallest feedback edge set is equivalent to finding a spanning forest, which can be done in polynomial time.
The analogous concept in a directed graph is the feedback arc set (FAS) - a set of directed arcs whose removal makes the graph acyclic. Finding a smallest FAS is an NP-hard problem.^[9]

Applications

In operating systems, 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.^[14]
The feedback vertex set problem has applications in VLSI chip design.^[15]
Another application is in complexity theory. Some computational problems on graphs are NP-hard in general, but can be solved in polynomial time for graphs with bounded FVS number. Some examples are graph isomorphism^[16] and the path reconfiguration problem.^[17]

Notes

↑ unpublished results due to Garey and Johnson, cf. Garey & Johnson (1979): GT7
↑ Ueno, Kajitani & Gotoh (1988); Li & Liu (1999)
↑ Fomin & Villanger (2010)
↑ Fomin et al. (2008).
↑ Razgon (2007).
↑ Chen et al. (2008).
↑ Ueno, Kajitani & Gotoh (1988).
↑ Dinur & Safra 2005
1 2 Karp (1972)
↑ Becker & Geiger (1996). See also Bafna, Berman & Fujito (1999) for an alternative approximation algorithm with the same approximation ratio.
↑ Guruswami, Venkatesan; Manokaran, Rajsekar; Raghavendra, Prasad (2008). "Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph". 2008 49th Annual IEEE Symposium on Foundations of Computer Science. pp. 573–582. doi:10.1109/FOCS.2008.51. ISBN 978-0-7695-3436-7. S2CID 8762205.
↑ Even, G.; (Seffi) Naor, J.; Schieber, B.; Sudan, M. (1998). "Approximating Minimum Feedback Sets and Multicuts in Directed Graphs". Algorithmica. 20 (2): 151–174. doi:10.1007/PL00009191. ISSN 0178-4617. S2CID 2437790.
↑ Erdős & Pósa (1965).
↑ Silberschatz, Galvin & Gagne (2008).
↑ Festa, Pardalos & Resende (2000).
↑ Kratsch, Stefan; Schweitzer, Pascal (2010). "Isomorphism for Graphs of Bounded Feedback Vertex Set Number". In Kaplan, Haim (ed.). Algorithm Theory - SWAT 2010. Lecture Notes in Computer Science. Vol. 6139. Berlin, Heidelberg: Springer. pp. 81–92. Bibcode:2010LNCS.6139...81K. doi:10.1007/978-3-642-13731-0_9. ISBN 978-3-642-13731-0.
↑ Algorithms and Data Structures (PDF). Lecture Notes in Computer Science. Vol. 11646. 2019. doi:10.1007/978-3-030-24766-9. ISBN 978-3-030-24765-2. S2CID 198996919.

Related Research Articles

<span class="mw-page-title-main">Directed acyclic graph</span> Directed graph with no directed cycles

In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges, with each edge directed from one vertex to another, such that following those directions will never form a closed loop. A directed graph is a DAG if and only if it can be topologically ordered, by arranging the vertices as a linear ordering that is consistent with all edge directions. DAGs have numerous scientific and computational applications, ranging from biology to information science to computation (scheduling).

In combinatorial mathematics, the Steiner tree problem, or minimum Steiner tree problem, named after Jakob Steiner, is an umbrella term for a class of problems in combinatorial optimization. While Steiner tree problems may be formulated in a number of settings, they all require an optimal interconnect for a given set of objects and a predefined objective function. One well-known variant, which is often used synonymously with the term Steiner tree problem, is the Steiner tree problem in graphs. Given an undirected graph with non-negative edge weights and a subset of vertices, usually referred to as terminals, the Steiner tree problem in graphs requires a tree of minimum weight that contains all terminals and minimizes the total weight of its edges. Further well-known variants are the Euclidean Steiner tree problem and the rectilinear minimum Steiner tree problem.

In graph theory, an independent set, stable set, coclique or anticlique is a set of vertices in a graph, no two of which are adjacent. That is, it is a set $of vertices such that for every two vertices in, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in . A set is independent if and only if it is a clique in the graph's complement. The size of an independent set is the number of vertices it contains. Independent sets have also been called "internally stable sets", of which "stable set" is a shortening.$

In graph theory, a vertex cover of a graph is a set of vertices that includes at least one endpoint of every edge of the graph.

In the mathematical discipline of graph theory, a matching or independent edge set in an undirected graph is a set of edges without common vertices. In other words, a subset of the edges is a matching if each vertex appears in at most one edge of that matching. Finding a matching in a bipartite graph can be treated as a network flow problem.

<span class="mw-page-title-main">Chordal graph</span> Graph where all long cycles have a chord

In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced cycle in the graph should have exactly three vertices. The chordal graphs may also be characterized as the graphs that have perfect elimination orderings, as the graphs in which each minimal separator is a clique, and as the intersection graphs of subtrees of a tree. They are sometimes also called rigid circuit graphs or triangulated graphs: a chordal completion of a graph is typically called a triangulation of that graph.

<span class="mw-page-title-main">Circuit rank</span> Fewest graph edges whose removal breaks all cycles

In graph theory, a branch of mathematics, the circuit rank, cyclomatic number, cycle rank, or nullity of an undirected graph is the minimum number of edges that must be removed from the graph to break all its cycles, making it into a tree or forest. It is equal to the number of independent cycles in the graph. Unlike the corresponding feedback arc set problem for directed graphs, the circuit rank $r$ is easily computed using the formula

<span class="mw-page-title-main">Dominating set</span> Subset of a graphs nodes such that all other nodes link to at least one

In graph theory, a dominating set for a graph $G$ is a subset $D$ of its vertices, such that any vertex of $G$ is in $D$ , or has a neighbor in $D$ . The domination number $γ(G)$ is the number of vertices in a smallest dominating set for $G$ .

In graph theory and graph algorithms, a feedback arc set or feedback edge set in a directed graph is a subset of the edges of the graph that contains at least one edge out of every cycle in the graph. Removing these edges from the graph breaks all of the cycles, producing an acyclic subgraph of the given graph, often called a directed acyclic graph. A feedback arc set with the fewest possible edges is a minimum feedback arc set and its removal leaves a maximum acyclic subgraph; weighted versions of these optimization problems are also used. If a feedback arc set is minimal, meaning that removing any edge from it produces a subset that is not a feedback arc set, then it has an additional property: reversing all of its edges, rather than removing them, produces a directed acyclic graph.

In graph theory, a cut is a partition of the vertices of a graph into two disjoint subsets. Any cut determines a cut-set, the set of edges that have one endpoint in each subset of the partition. These edges are said to cross the cut. In a connected graph, each cut-set determines a unique cut, and in some cases cuts are identified with their cut-sets rather than with their vertex partitions.

In graph theory, a connected dominating set and a maximum leaf spanning tree are two closely related structures defined on an undirected graph.

In graph theory, a minimum degree spanning tree is a subset of the edges of a connected graph that connects all the vertices together, without any cycles, and its maximum degree of its vertices as small as possible. That is, it is a spanning tree whose maximum degree is minimal.

In computer science, a kernelization is a technique for designing efficient algorithms that achieve their efficiency by a preprocessing stage in which inputs to the algorithm are replaced by a smaller input, called a "kernel". The result of solving the problem on the kernel should either be the same as on the original input, or it should be easy to transform the output on the kernel to the desired output for the original problem.

In graph theory and theoretical computer science, the longest path problem is the problem of finding a simple path of maximum length in a given graph. A path is called simple if it does not have any repeated vertices; the length of a path may either be measured by its number of edges, or by the sum of the weights of its edges. In contrast to the shortest path problem, which can be solved in polynomial time in graphs without negative-weight cycles, the longest path problem is NP-hard and the decision version of the problem, which asks whether a path exists of at least some given length, is NP-complete. This means that the decision problem cannot be solved in polynomial time for arbitrary graphs unless P = NP. Stronger hardness results are also known showing that it is difficult to approximate. However, it has a linear time solution for directed acyclic graphs, which has important applications in finding the critical path in scheduling problems.

Bidimensionality theory characterizes a broad range of graph problems (bidimensional) that admit efficient approximate, fixed-parameter or kernel solutions in a broad range of graphs. These graph classes include planar graphs, map graphs, bounded-genus graphs and graphs excluding any fixed minor. In particular, bidimensionality theory builds on the graph minor theory of Robertson and Seymour by extending the mathematical results and building new algorithmic tools. The theory was introduced in the work of Demaine, Fomin, Hajiaghayi, and Thilikos, for which the authors received the Nerode Prize in 2015.

Layered graph drawing or hierarchical graph drawing is a type of graph drawing in which the vertices of a directed graph are drawn in horizontal rows or layers with the edges generally directed downwards. It is also known as Sugiyama-style graph drawing after Kozo Sugiyama, who first developed this drawing style.

In network theory, the Wiener connector is a means of maximizing efficiency in connecting specified "query vertices" in a network. Given a connected, undirected graph and a set of query vertices in a graph, the minimum Wiener connector is an induced subgraph that connects the query vertices and minimizes the sum of shortest path distances among all pairs of vertices in the subgraph. In combinatorial optimization, the minimum Wiener connector problem is the problem of finding the minimum Wiener connector. It can be thought of as a version of the classic Steiner tree problem, where instead of minimizing the size of the tree, the objective is to minimize the distances in the subgraph.

In combinatorial optimization, the matroid parity problem is a problem of finding the largest independent set of paired elements in a matroid. The problem was formulated by Lawler (1976) as a common generalization of graph matching and matroid intersection. It is also known as polymatroid matching, or the matchoid problem.

In graph theory, an odd cycle transversal of an undirected graph is a set of vertices of the graph that has a nonempty intersection with every odd cycle in the graph. Removing the vertices of an odd cycle transversal from a graph leaves a bipartite graph as the remaining induced subgraph.

In graph theory, the cutwidth of an undirected graph is the smallest integer $with the following property: there is an ordering of the vertices of the graph, such that every cut obtained by partitioning the vertices into earlier and later subsets of the ordering is crossed by at most edges. That is, if the vertices are numbered, then for every, the number of edges with and is at most .$

References

Research articles

Bafna, Vineet; Berman, Piotr; Fujito, Toshihiro (1999), "A 2-approximation algorithm for the undirected feedback vertex set problem", SIAM Journal on Discrete Mathematics, 12 (3): 289–297 (electronic), doi:10.1137/S0895480196305124, MR 1710236 .
Becker, Ann; Bar-Yehuda, Reuven; Geiger, Dan (2000), "Randomized algorithms for the loop cutset problem", Journal of Artificial Intelligence Research , 12: 219–234, arXiv: 1106.0225 , doi:10.1613/jair.638, MR 1765590, S2CID 10243677
Becker, Ann; Geiger, Dan (1996), "Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem.", Artificial Intelligence , 83 (1): 167–188, CiteSeerX 10.1.1.25.1442 , doi:10.1016/0004-3702(95)00004-6
Cao, Yixin; Chen, Jianer; Liu, Yang (2010), "On feedback vertex set: new measure and new structures", in Kaplan, Haim (ed.), Proc. 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2010), Bergen, Norway, June 21-23, 2010, Lecture Notes in Computer Science, vol. 6139, pp. 93–104, arXiv: 1004.1672 , Bibcode:2010LNCS.6139...93C, doi:10.1007/978-3-642-13731-0_10, ISBN 978-3-642-13730-3
Chen, Jianer; Fomin, Fedor V.; Liu, Yang; Lu, Songjian; Villanger, Yngve (2008), "Improved algorithms for feedback vertex set problems", Journal of Computer and System Sciences , 74 (7): 1188–1198, doi:10.1016/j.jcss.2008.05.002, MR 2454063
Chen, Jianer; Liu, Yang; Lu, Songjian; O'Sullivan, Barry; Razgon, Igor (2008), "A fixed-parameter algorithm for the directed feedback vertex set problem", Journal of the ACM , 55 (5), Art. 21, doi:10.1145/1411509.1411511, MR 2456546, S2CID 1547510
Dinur, Irit; Safra, Samuel (2005), "On the hardness of approximating minimum vertex cover" (PDF), Annals of Mathematics , Second Series, 162 (1): 439–485, doi:10.4007/annals.2005.162.439, MR 2178966, archived from the original (PDF) on 2009-09-20, retrieved 2010-03-29
Erdős, Paul; Pósa, Lajos (1965), "On independent circuits contained in a graph" (PDF), Canadian Journal of Mathematics , 17: 347–352, doi:10.4153/CJM-1965-035-8, S2CID 123981328
Fomin, Fedor V.; Gaspers, Serge; Pyatkin, Artem; Razgon, Igor (2008), "On the minimum feedback vertex set problem: exact and enumeration algorithms.", Algorithmica , 52 (2): 293–307, CiteSeerX 10.1.1.722.8913 , doi:10.1007/s00453-007-9152-0, S2CID 731997
Fomin, Fedor V.; Villanger, Yngve (2010), "Finding induced subgraphs via minimal triangulations", Proc. 27th International Symposium on Theoretical Aspects of Computer Science (STACS 2010), Leibniz International Proceedings in Informatics (LIPIcs), vol. 5, pp. 383–394, doi: 10.4230/LIPIcs.STACS.2010.2470 , ISBN 9783939897163, S2CID 436224
Karp, Richard M. (1972), "Reducibility Among Combinatorial Problems", Proc. Symposium on Complexity of Computer Computations, IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., New York: Plenum, pp. 85–103
Li, Deming; Liu, Yanpei (1999), "A polynomial algorithm for finding the minimum feedback vertex set of a 3-regular simple graph", Acta Mathematica Scientia, 19 (4): 375–381, doi:10.1016/s0252-9602(17)30520-9, MR 1735603
Razgon, I. (2007), "Computing minimum directed feedback vertex set in O*(1.9977ⁿ)", in Italiano, Giuseppe F.; Moggi, Eugenio; Laura, Luigi (eds.), Proceedings of the 10th Italian Conference on Theoretical Computer Science (PDF), World Scientific, pp. 70–81
Ueno, Shuichi; Kajitani, Yoji; Gotoh, Shin'ya (1988), "On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three", Discrete Mathematics , 72 (1–3): 355–360, doi: 10.1016/0012-365X(88)90226-9 , MR 0975556

Textbooks and survey articles

Festa, P.; Pardalos, P. M.; Resende, M.G.C. (2000), "Feedback set problems", in Du, D.-Z.; Pardalos, P. M. (eds.), Handbook of Combinatorial Optimization, Supplement vol. A (PDF), Kluwer Academic Publishers, pp. 209–259
Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, A1.1: GT7, p. 191, ISBN 978-0-7167-1045-5
Silberschatz, Abraham; Galvin, Peter Baer; Gagne, Greg (2008), Operating System Concepts (8th ed.), John Wiley & Sons. Inc, ISBN 978-0-470-12872-5

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] unpublished results due to Garey and Johnson, cf. Garey & Johnson (1979): GT7

[2] Ueno, Kajitani & Gotoh (1988); Li & Liu (1999)

[3] Fomin & Villanger (2010)

[FOOTNOTEFominGaspersPyatkinRazgon2008-4] Fomin et al. (2008).

[FOOTNOTERazgon2007-5] Razgon (2007).

[FOOTNOTEChenLiuLuO'Sullivan2008-6] Chen et al. (2008).

[FOOTNOTEUenoKajitaniGotoh1988-7] Ueno, Kajitani & Gotoh (1988).

[8] Dinur & Safra 2005

[k72-9] 1 2 Karp (1972)

[10] Becker & Geiger (1996). See also Bafna, Berman & Fujito (1999) for an alternative approximation algorithm with the same approximation ratio.

[11] Guruswami, Venkatesan; Manokaran, Rajsekar; Raghavendra, Prasad (2008). "Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph". 2008 49th Annual IEEE Symposium on Foundations of Computer Science. pp. 573–582. doi:10.1109/FOCS.2008.51. ISBN 978-0-7695-3436-7. S2CID 8762205.

[12] Even, G.; (Seffi) Naor, J.; Schieber, B.; Sudan, M. (1998). "Approximating Minimum Feedback Sets and Multicuts in Directed Graphs". Algorithmica. 20 (2): 151–174. doi:10.1007/PL00009191. ISSN 0178-4617. S2CID 2437790.

[FOOTNOTEErdősPósa1965-13] Erdős & Pósa (1965).

[FOOTNOTESilberschatzGalvinGagne2008-14] Silberschatz, Galvin & Gagne (2008).

[FOOTNOTEFestaPardalosResende2000-15] Festa, Pardalos & Resende (2000).

[16] Kratsch, Stefan; Schweitzer, Pascal (2010). "Isomorphism for Graphs of Bounded Feedback Vertex Set Number". In Kaplan, Haim (ed.). Algorithm Theory - SWAT 2010. Lecture Notes in Computer Science. Vol. 6139. Berlin, Heidelberg: Springer. pp. 81–92. Bibcode:2010LNCS.6139...81K. doi:10.1007/978-3-642-13731-0_9. ISBN 978-3-642-13731-0.

[17] Algorithms and Data Structures (PDF). Lecture Notes in Computer Science. Vol. 11646. 2019. doi:10.1007/978-3-030-24766-9. ISBN 978-3-030-24765-2. S2CID 198996919.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]