Графтарда циклдарды жою мәселесі: NP-толықтығы және шешімдері

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.

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. 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.

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. 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.

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.

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 , 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. and the path reconfiguration problem.

.