Fact-checked by Grok 2 weeks ago

Feedback vertex set

In , a feedback vertex set (FVS) of an undirected is a of vertices whose removal renders the remaining acyclic, meaning it contains no cycles. Equivalently, every FVS intersects at least one vertex from each cycle in the . The minimum feedback vertex set problem seeks the smallest such set, which is a classic optimization challenge with significant theoretical and practical implications. The decision version of the FVS problem—determining whether a has an FVS of size at most k—is NP-complete, as established among the original 21 NP-complete problems by Karp in (noting that the directed variant, feedback node set, was explicitly listed, with the undirected case following via standard reductions). This NP-completeness holds even on restricted graph classes like planar graphs. Due to its hardness, exact solutions are infeasible for large instances in polynomial time unless P=, prompting extensive research into and parameterized approaches. For approximation algorithms, a 2-approximation for the undirected FVS problem was developed by Bafna, Berman, and Fujito in 1999, which iteratively contracts cycles and selects vertices to hit them efficiently. More refined approximations exist for special cases, such as a 7/3- for tournaments. In , FVS is fixed-parameter tractable when parameterized by the solution size k, with deterministic algorithms achieving runtimes like O^((2 + φ)^k)* where φ ≈ 1.619, improving on earlier exponential dependencies. These FPT algorithms often combine branching, dynamic programming on tree decompositions, and kernelization techniques to reduce instance size. Applications of FVS span multiple domains, including deadlock detection and recovery in operating systems, where identifying vertices to "break" cyclic dependencies prevents system hangs. In VLSI design and program verification, FVS helps eliminate feedback loops to ensure acyclic flows and correct behavior. Additionally, it models state in , such as biological systems or problems, by selecting minimal interventions to transition from cyclic to desired acyclic states.

Definition and Properties

Formal Definition

In an undirected G = (V, E), a feedback vertex set (FVS) is a S \subseteq V of vertices such that the G - S contains no , meaning G - S is a . Equivalently, every FVS intersects the vertex set of every in G. The minimum feedback vertex set problem is the optimization variant that seeks the FVS of smallest in G; the size of such a minimum FVS is known as the feedback vertex number of G, often denoted \tau(G). The decision version of the problem, denoted Feedback Vertex Set, asks whether there exists an FVS of size at most a given k. This problem is analogous to the problem, which instead seeks a set of edges whose removal acyclicizes the . The concept of a was introduced in the in the context of and elimination, appearing as one of the foundational combinatorial problems studied for computational tractability.

Basic Properties and Characterizations

A (FVS) is minimal if no proper subset of it is also an FVS. This means that for every in the minimal FVS, there exists at least one in the that contains that vertex but no other vertices from the set. Moreover, the size of any minimal FVS satisfies |F| ≤ n - c, where n is the number of vertices in the graph and c is the number of connected components in the induced by V \ F, since the forest has at least c vertices. By definition, every FVS intersects every in the , as the removal of the set must eliminate all cycles. Consequently, the size of the minimum FVS provides a lower bound on the vertex cover number for the collection of all cycles in the . A related structural insight arises from cycle packing: the maximum number of vertex-disjoint cycles in the serves as a lower bound on the size of the minimum FVS, since each such must be hit by at least one distinct in the set. The size of the minimum FVS is closely related to the treewidth of the . Specifically, for any G, the treewidth tw(G) satisfies tw(G) ≤ fvs(G) + 1, where fvs(G) denotes the size of the minimum FVS; equivalently, fvs(G) ≥ tw(G) - 1. This follows from the fact that removing a minimum FVS leaves a forest, which has treewidth 1, and adding back the FVS vertices increases the treewidth by at most fvs(G). Equality holds in certain cases, such as cycles (where tw = 2 and fvs = 1) and complete graphs (where tw = n-1 and fvs = n-2, achieving tw = fvs + 1). An alternative characterization of FVS arises through induced acyclic subgraphs. The complement of any FVS induces in the , as no cycles remain after removal. Conversely, the minimum FVS corresponds exactly to the complement of a maximum induced : finding the largest vertex set whose induced subgraph is acyclic yields the smallest set whose removal achieves acyclicity. This duality highlights that the feedback vertex set problem is equivalent to finding the minimum number of to delete to maximize the size of an induced . The FVS problem admits polynomial-time solutions in certain graph classes with restricted structure. For trees, which are already acyclic, the minimum FVS is empty and can be recognized in constant time (or linear time including graph input). For outerplanar graphs, which have treewidth at most 2, the problem is solvable in linear time via dynamic programming on a tree decomposition of bounded width.

Computational Complexity

NP-Completeness Results

The feedback vertex set problem was among the first problems shown to be NP-complete, with the directed version established by Karp in 1972 via a from the by 3-sets problem. This proof appeared shortly after Cook's 1971 theorem demonstrating the NP-completeness of the problem, highlighting the rapid expansion of known NP-complete problems in . For undirected graphs, the NP-completeness of the minimum feedback vertex set problem was formalized by Garey and Johnson in 1979, using a from the by 3-sets problem that constructs a graph with maximum 4. This reduction preserves the hardness even when restricted to graphs of maximum 4, establishing that the problem remains NP-complete in this bounded-degree setting. In contrast, the problem admits a polynomial-time for graphs of maximum at most 3, achieved through to the problem. Specific reductions for the undirected case include transformations from the Hamiltonian cycle problem in cubic graphs, where the presence of a Hamiltonian cycle implies the need to hit it in any feedback vertex set, combined with gadgets to ensure exact correspondence. Another common reduction originates from the by 3-sets, creating variable and clause gadgets that form cycles only resolvable by selecting vertices corresponding to a valid . The minimum feedback vertex set problem in undirected graphs is APX-complete, meaning it is NP-hard to approximate within a constant better than 1 unless P=. This follows from an L-reduction from the APX-complete problem in cubic graphs, where cycles are introduced in a way that the minimum feedback vertex set size approximates the vertex cover size within a bounded . Consequently, no polynomial-time approximation scheme (PTAS) exists for the problem unless P=.

Parameterized Complexity

The Feedback Vertex Set (FVS) problem is fixed-parameter tractable (FPT) when parameterized by the solution size k, meaning there exist algorithms that solve it in time f(k) \cdot n^{O(1)} for some computable function f depending only on k, where n is the input size. Early FPT algorithms for undirected FVS relied on branching techniques, which achieve running times such as O(3^k n) by recursively branching on vertices in detected cycles. Randomized approaches using color-coding, introduced for related cycle-hitting problems, have also been adapted to FVS, enabling efficient detection of vertex-disjoint cycles and yielding expected running times like O(4^k n^{O(1)}) in seminal works. These methods contrast with the classical NP-hardness of FVS (para-NP-hard without parameterization), highlighting how the parameter k renders the problem tractable. Kernelization results further underscore the FPT nature of FVS, reducing instances to polynomial-size equivalents while preserving solvability. A kernel of size O(k^2) was established in the early , with the first polynomial kernel for undirected FVS confirmed via crown decompositions and LP relaxations, yielding at most $4k^2 vertices. More refined techniques, including linear-time preprocessing, produce kernels with $2k^2 + k vertices and $4k^2 edges, improving practical efficiency for moderate k. While linear-size kernels (e.g., O(k)) remain elusive for undirected FVS—unlike for —edge-based kernels of size O(k) have been explored in extensions, though remains standard. Certain variants of FVS exhibit W-hardness under parameterization by k, distinguishing them from the standard undirected case which is FPT. Recent advances from 2020 to 2025 have tightened FPT bounds, including randomized algorithms achieving O^*(2.7^k) time via randomized branching and measure-and-conquer analysis, outperforming prior O^*(3.619^k) deterministic methods, with the best deterministic runtime remaining O^*((2 + \phi)^k) where \phi \approx 1.618 as of 2025. Additionally, enumeration kernels for FVS, introduced in 2024, facilitate listing all minimal solutions in FPT time with compact representations, aiding applications in enumeration-heavy contexts. Bidimensionality theory provides a structural framework for FVS tractability on restricted graph classes. FVS is a bidimensional parameter, meaning its size scales quadratically with grid minors, implying subexponential FPT algorithms (e.g., $2^{O(\sqrt{k})} n^{O(1)}) on planar graphs, surfaces of bounded genus, and H-minor-free families via dynamic programming on tree decompositions. This approach extends classical FPT results, enabling efficient solutions on these families without relying solely on solution size k.

Algorithms

Exact Algorithms

Branching algorithms for the minimum feedback vertex set (FVS) problem often employ iterative , a technique that starts with a trivial of size n (the full vertex set) and iteratively builds larger induced subgraphs while compressing existing feedback vertex sets to find smaller ones of the same size. This approach reduces the problem to solving disjoint instances, where the goal is to find a feedback vertex set disjoint from a given one of size at most k, enabling fixed-parameter tractable (FPT) algorithms that are also for instances where k is small relative to n. The seminal application of iterative to FVS achieved O(4^k n^2) through branching on cycles in the step. Subsequent refinements in the established a baseline of O(3.618^k n^{O(1)}) time using advanced branching rules and measure-and-conquer analysis on cycle structures. A deterministic improvement from 2019 runs in O(3.460^k n^{O(1)}) time by introducing new reduction rules that bound the branching factor more tightly. A from 2022 further improves this to O^*(2.7^k) time by combining randomized selection with dynamic programming techniques. For specific graph classes, recent results have pushed the base of the exponential term lower. In tournaments, a 2016 algorithm achieved O(1.618^k \cdot n^{O(1)}) time via randomized selection and dynamic programming over topological orders, with a 2024 extension to bipartite tournaments improving this to O(1.6181^k + n^{O(1)}) by exploiting the bipartite structure to reduce the state space in the DP table. For the directed variant (DFVS), a simplified 2024 algorithm resolves the compression step more efficiently, yielding O(k! \cdot 2^{o(k)} \cdot (n + m)) time overall through streamlined branching on strongly connected components without losing the original guarantees. Dynamic programming on tree decompositions provides another cornerstone for exact FVS algorithms, running in O(2^{O(\mathrm{tw})} n) time where \mathrm{tw} is the of the graph. The DP states track the partial feedback vertex set in each bag, ensuring the subgraphs induced by forgotten vertices remain forests, with transitions handling edges within and between bags. This approach is particularly effective when combined with treewidth approximation heuristics, though exact computation of is expensive. For planar graphs, where treewidth is bounded by O(\sqrt{n}), the same DP yields subexponential time O(2^{O(\sqrt{n})}), enabling exact solutions for moderate-sized instances without parameterization. Space-efficient variants of these algorithms trade exponential time for reduced memory usage, often achieving polynomial space at the cost of slightly larger branching factors. For instance, the 2019 deterministic algorithm maintains polynomial space while solving in single-exponential parameterized time, making it suitable for implementations where memory is a bottleneck.

Approximation Algorithms

The minimum feedback vertex set (FVS) problem in undirected graphs admits a polynomial-time 2-approximation algorithm based on linear programming rounding or greedy selection techniques. This approach solves an integer linear program relaxation where variables indicate vertex inclusion in the FVS, subject to constraints ensuring every cycle is hit; rounding the solution yields a set at most twice the optimum size. An alternative greedy method iteratively selects the vertex incident to the maximum number of remaining cycles, analyzed to achieve the same 2-factor guarantee in weighted graphs. For the directed variant, known as directed feedback vertex set (DFVS), the best polynomial-time approximation achieves an O(\log n \log \log n) , where n is the number of vertices, via iterative rounding of a set cover formulation that models cycles as elements to hit. Under the , no polynomial-time algorithm can approximate DFVS to within O(\log \log \log ) of the optimum, where is the size, establishing tightness up to constants. In the parameterized setting, where the algorithm is fixed-parameter tractable in the solution size k, recent advances provide approximation schemes beyond constant factors. A randomized FPT approximation scheme (FPT-AS) achieves a (1 + \epsilon)-approximation for any \epsilon > 0 in time f(k, \epsilon) n^{O(1)}, leveraging dynamic programming over tree decompositions and randomized rounding. For broader vertex deletion problems including FVS, a 2024 result introduces faster parameterized \beta-approximations for 1 < \beta < 2 using sampling techniques combined with black-box solvers, improving prior running times to 2^{O(k \log k)} n^{O(1)} for constant \beta. Greedy algorithms remain foundational, particularly in practice, by prioritizing vertices that cover the most uncovered cycles or feedback arcs, with theoretical analysis confirming constant-factor performance in both undirected and directed cases; these methods often outperform LP-based approaches on sparse graphs due to simplicity and speed. Between 2020 and 2025, progress in parameterized approximations for and related hitting set problems has focused on tighter ratios and reduced exponents, exemplified by iterative compression and sampling hybrids that yield O(\log k)-approximations in subexponential FPT time for hitting set variants underlying FVS.

Theoretical Bounds

Extremal Bounds

The provides a fundamental extremal duality for cycles in undirected graphs, stating that for any integer t \geq 1, every graph on n vertices either contains t vertex-disjoint cycles or admits a of size at most O(t \log t). This bound is tight up to constant factors, as demonstrated by constructions involving or random graphs that require \Omega(t \log t) vertices to hit all cycles when the packing number is small. The theorem implies that graphs without large cycle packings have relatively small feedback vertex sets relative to the packing size. In general graphs, the size of the minimum feedback vertex set equals n minus the order of the largest induced forest. In planar graphs, the minimum feedback vertex set has size at most three times the maximum number of vertex-disjoint cycles, yielding an upper bound of O(n) since the cycle packing number is at most O(n). Tighter bounds hold for restricted classes: for example, planar graphs of girth at least 5 have minimum feedback vertex sets of size at most n/3, and this is tight for certain planar graphs of girth at least 5. For grid graphs, which are a canonical planar class, the minimum feedback vertex set size is exactly \Theta(n), as the numerous disjoint facial cycles require hitting at least a constant fraction of vertices, while simple row-removal strategies achieve the upper bound. Turán-type extremal results characterize the maximum number of edges in graphs with bounded feedback vertex number k, showing that connected graphs of order n and feedback number at most k have at most O(n^{3/2} \sqrt{k}) edges, with the extremal graphs closely related to blow-ups of cycle-free structures like Turán graphs T(n,2) (complete bipartite graphs, which are forests when balanced). This bound is sharp, as constructions based on complete bipartite graphs plus k additional vertices achieve \Theta(n^{3/2} \sqrt{k}) edges while maintaining feedback number k.

Packing-Covering Duality

The packing-covering duality for the feedback vertex set (FVS) problem relates the minimum size of an FVS, denoted \tau(G), to the maximum number of vertex-disjoint cycles in a graph G, denoted \nu(G). By definition, \nu(G) \leq \tau(G), as each cycle in a maximum packing must be intersected by at least one vertex in any FVS. Equality holds in graphs that "pack," meaning \nu(H) = \tau(H) for every induced subgraph H of G; such graphs are precisely those excluding subdivisions of K_{3,3}, wheels, and odd rings as induced subgraphs. In general graphs, the Erdős–Pósa property implies that \tau(G) \leq O(\nu(G) \log \nu(G)), providing a bound on how much larger the covering can be compared to the packing. In specific graph classes, stronger min-max relations exist. For instance, in bipartite tournaments, a min-max theorem equates the minimum FVS size to the maximum number of vertex-disjoint directed cycles, based on the total dual integrality of the cycle-vertex incidence linear system. More broadly, weighted versions of these relations characterize graphs where the maximum weight of a feedback vertex set packing equals the minimum weight of a cycle covering all vertices, with equality holding in graphs avoiding certain forbidden structures. For graphs of maximum degree at most 3, the FVS problem admits a polynomial-time algorithm via matroid duality, modeling it as finding a minimum transversal in the intersection of the cycle matroid and a partition matroid on vertices. This approach leverages the matroid parity algorithm to solve the weighted minimum FVS exactly. Integer linear programming (ILP) formulations further highlight this duality. The standard ILP for minimum FVS minimizes \sum_{v \in V} x_v subject to \sum_{v \in C} x_v \geq 1 for every cycle C, with x_v \in \{0,1\}. The LP relaxation's dual maximizes \sum_C y_C subject to \sum_{C \ni v} y_C \leq 1 for each v, with y_C \geq 0, which corresponds to a fractional cycle packing; weak duality thus bounds the FVS size by the maximum fractional packing value. This formulation underpins approximation algorithms, where the integrality gap is at most 2 in undirected graphs. Recent structural results extend these dualities through antler decompositions, which preprocess graphs to identify vertices guaranteed to be in an optimal FVS. An antler (C, F) certifies that any minimum FVS includes all of C, where |C| packs vertex-disjoint cycles in G[C \cup F] and F is a forest with limited attachments; this yields the min-max relation fvs(G) = |C| + fvs(G - (C \cup F)). Algorithms find such structures in $2^{O(k^5)} n^{O(1)} time for width k, reducing the search space for exact FVS computation.

Variants and Related Concepts

Directed Feedback Vertex Set

In directed graphs, the directed feedback vertex set (DFVS) problem seeks a minimum-sized set of vertices whose removal renders the remaining digraph acyclic, meaning it admits a topological ordering with no directed cycles. Unlike the undirected case, where acyclicity implies a forest structure, in directed graphs, the focus is on eliminating all directed cycles while preserving the orientation of arcs. This set must intersect every directed cycle in the graph, ensuring the induced subgraph on the remaining vertices is a directed acyclic graph (DAG). The undirected feedback vertex set problem arises as a special case when all arc directions are ignored, reducing to hitting all cycles in the underlying undirected graph. The DFVS problem is NP-complete, as established in Richard Karp's seminal 1972 list of 21 NP-complete problems, by reduction from the vertex cover problem. It is fixed-parameter tractable when parameterized by the solution size k, with an algorithm running in O(4^k k^3 n^4) time developed by Chen, Liu, and Lu in 2008, using techniques like bounded search trees and dynamic programming on strongly connected components. A simplified and improved parameterized algorithm was presented in 2024, achieving O(k! \cdot 2^{o(k)} (n + m)) time, where n is the number of vertices and m the number of arcs, by refining the handling of feedback vertex candidates and reducing the branching factor. Approximation algorithms for DFVS in general digraphs are more challenging than in the undirected case, with the best known providing an O(\log n \log \log n)-approximation ratio. Hardness results indicate that DFVS cannot be approximated within a factor of O(n^{1-\epsilon}) for any \epsilon > 0 unless P = NP, stemming from inapproximability reductions involving label cover and other PCP-based constructions. Kernelization for DFVS parameterized by k remains a prominent open question; while no polynomial-sized kernel is known, progress has been made under alternative parameterizations, such as the feedback vertex set size of the underlying undirected graph, yielding kernels of size O(k^{O(1)}). Key properties of DFVS include its equivalence to finding a set that hits all directed cycles, which directly enables in the residual graph for applications like scheduling and dependency resolution. The problem's structure often leverages the of strongly connected components, where feedback vertices are concentrated in cyclic components, facilitating both exact and parameterized solutions.

Other Graph Variants

The weighted feedback vertex set problem extends the standard formulation by assigning nonnegative weights to vertices, with the objective of finding a minimum-weight set S whose removal leaves an acyclic . This variant remains NP-hard but admits fixed-parameter tractable algorithms parameterized by the solution size k, achieving running times such as O(3.83^k + kn^3) via iterative compression and branching techniques adapted from the unweighted case. Kernelization results for weighted FVS are similar to those for the unweighted version, yielding quadratic kernels through crown reductions and relaxations, enabling preprocessing to instances of size O(k^2). Eternal feedback vertex sets introduce a dynamic protection model where a set of mobile guards initially forms a feedback vertex set, and upon the activation of a new (threat), guards can relocate along edges in one step to reestablish acyclicity. This variant, denoted EFVS, models ongoing graph safeguarding against evolving cycles and is NP-hard even on simple graphs. The m-eternal feedback vertex set (m-EFVS) generalizes this to handle up to m simultaneous threats, requiring reconfiguration after each while maintaining the feedback property; both problems are studied on treewidth-bounded graphs, with polynomial-time solvability for trees and paths. On restricted graph classes, feedback vertex set exhibits improved tractability. Although NP-complete on general bipartite graphs, it is solvable in polynomial time on subclasses such as chordal bipartite graphs via dynamic programming on a clique tree representation. In tournaments, the problem admits a fixed-parameter tractable running in O(1.618^k \cdot n^{O(1)}) time, leveraging measure-and-conquer analysis on branching rules; a recent refinement for bipartite tournaments maintains this bound while incorporating matching-based reductions for exact verification. For geometric graphs like pseudo-disk graphs, subexponential fixed-parameter tractability is achieved, with algorithms running in $2^{O(\sqrt{k} \log k)} n^{O(1)} time using theorems and randomized rounding. An independent feedback vertex set requires the hitting set S to induce no edges, ensuring S is while G - S is a forest. This variant is NP-hard on general but polynomial-time solvable on P_5-free graphs through bounded methods combined with modular . It finds applications in structural graph decompositions, such as near-bipartite partitions where the independent set covers all odd cycles. The long-loop feedback vertex set variant, tailored to factor graphs representing bipartite probabilistic models, seeks a minimum set of variable nodes whose removal breaks all cycles longer than a specified length \ell, preserving short loops essential for local approximations. This problem arises in network dismantling and belief propagation efficiency, with an exact algorithm developed using message-passing on the factor graph structure, outperforming greedy heuristics on sparse random graphs.

Applications

In Graph Algorithms and Complexity

The (FVS) problem plays a pivotal role in algorithms as a preprocessing technique for problems defined on directed acyclic graphs (DAGs). By computing a minimum FVS and removing those vertices, the resulting becomes acyclic, enabling efficient solutions to DAG-specific tasks such as and computation. , which orders vertices such that for every directed edge uv, vertex u precedes v, can then be performed in linear time using Kahn's algorithm on the forest structure left after FVS deletion. Similarly, —determining reachability between all pairs of vertices—reduces to a straightforward dynamic programming approach on the DAG, avoiding the complexities of cycles in the original . This preprocessing is particularly valuable in dependency resolution and scheduling algorithms where cycles represent conflicts or deadlocks. In hardness reductions, FVS serves as a foundational NP-hard problem to establish lower bounds for related graph problems. For instance, reductions from FVS demonstrate the NP-hardness of certain variants, where deciding isomorphism under vertex deletions to acyclic structures inherits the intractability of FVS. Likewise, FVS reductions prove for minor testing in specific graph families, as hitting cycles to enforce acyclicity mirrors the structural deletions needed to test for forbidden like cycles. These reductions often involve constructions that embed FVS instances into the target problem, preserving the minimum deletion size while simulating cycle intersections. Within parameterized complexity, FVS exemplifies vertex deletion problems to hereditary graph properties, where the target class (forests) is closed under taking induced subgraphs. The problem is fixed-parameter tractable (FPT) when parameterized by solution size k, with algorithms achieving O(3.83^k n^O(1)) time via branching and kernelization techniques, serving as a prototype for broader classes like chordal or bipartite deletion. This framework has influenced the study of deletion to other hereditary properties, such as perfect graphs, where FVS-inspired reductions show W-hardness or FPT dichotomies based on the property's structural width. Seminal work highlights FVS's role in catalyzing kernelization rules that bound the size by functions of k, facilitating dynamic programming on tree decompositions of the reduced instance. FVS also contributes to cycle-hitting strategies in approximation algorithms for optimization problems like the traveling salesman problem (TSP) and scheduling. In TSP approximations for planar graphs, FVS techniques help decompose the graph into acyclic components, allowing dynamic programming over treewidth-bounded subgraphs to achieve (1+ε)-approximation in 2^{O(1/ε)} n time, generalizing Baker's shifting method to handle cycles via vertex deletions. For scheduling problems with precedence constraints, hitting cycles with an FVS resolves circular dependencies, enabling approximation schemes that integrate with relaxations for makespan minimization, often yielding O(log n)-approximations when combined with arc set variants. Recent advancements (2020–2025) underscore FVS's utility in FPT algorithms for advanced parameters. In 2023, it was shown that the eccentricity shortest path () problem—finding a shortest path with minimum —is FPT parameterized by the combined feedback vertex set size and target ℓ, via kernelization to bounded after cycle hitting. Additionally, a 2022 study established FPT results for FVS above and below structural parameters like degeneracy and feedback vertex number, providing algorithms running in 2^{O(k + d)} n^{O(1)} time where k is the solution size and d the degeneracy, using difference-of-parameters techniques to handle excesses or deficits relative to cores.

In Practical Systems and Modeling

In operating systems, the feedback vertex set problem arises in deadlock recovery, where resource allocation graphs model process-resource dependencies, and cycles represent potential . A minimum feedback vertex set corresponds to the smallest set of processes to terminate in order to break all cycles and restore acyclicity, thereby resolving the with minimal disruption. This approach is particularly useful in systems with multiple instances, as detecting and hitting cycles via removal ensures stability without excessive overhead. In very-large-scale integration (VLSI) design, feedback vertex sets are employed to eliminate cycles in circuit dependency graphs, ensuring acyclic signal propagation for reliable and testing. By identifying and removing a minimal set of vertices (corresponding to gates or components), designers can simplify feedback loops in complex layouts, which is critical for fault detection and in chip fabrication. Heuristic algorithms that construct spanning trees to approximate vertex covers have been developed specifically for VLSI circuits, achieving small feedback vertex sets that maintain functional integrity while reducing cyclic dependencies. Biological networks, such as gene regulatory and metabolic pathways, leverage feedback vertex sets to pinpoint key nodes—genes or proteins—that control cyclic interactions underlying cellular dynamics. Removing these vertices from the network model renders it acyclic, allowing simulation of interventions like gene knockouts to predict steady-state behaviors or fixed points in Boolean network representations. This method has been applied to faithful monitoring of molecular activities, where a feedback vertex set serves as a determining set for the network's attractors, aiding in the design of targeted therapies for regulatory disorders. For instance, in metabolic pathways, identifying minimal feedback vertex sets reveals critical enzymes that sustain oscillatory cycles, informing synthetic biology designs. In communication networks, feedback vertex sets enhance reliability by targeting vertices whose removal eliminates feedback loops that propagate failures or congestion. This is modeled on graphs representing routing dependencies, where cycles can amplify disruptions in data flow; a minimal such set ensures fault-tolerant, acyclic paths, improving overall network resilience. Applications include power grids and telecom infrastructures, where structural control via feedback vertex sets prevents cascading failures by dismantling cyclic dependencies with high efficiency. Recent advancements from 2020 to 2025 have extended feedback vertex sets to dynamic and protective contexts. The eternal feedback vertex set model, introduced for graph protection in dynamic , involves mobile guards repositioning to perpetually hit emerging cycles, with linear-time algorithms developed for interval graphs to support real-time monitoring in evolving systems like sensor . Additionally, in dismantling complex systems, long-loop feedback vertex sets on bipartite factor graphs have been used to selectively break extended cycles while preserving short-range connectivity, applied to for targeted engineering.