Minimum Feedback Vertex Set (MFVS)

Input

A directed graph $G = (V, E)$ that is cyclically reducible (defined below) and a designated vertex $v$.

Problem

Is $v$ contained in the minimum feedback set of $G$ that is computed by the algorithm given by Wang, Lloyd, and Soffa [1]?

Definitions

A vertex $z$ of $G$ is deadlocked if there is a directed path in $G$ from $z$ to a vertex $y$ that lies on a directed cycle. The associated graph of vertex x with respect to G, $A(G,x)$, consists of vertex $x$ and all vertices of $G$ that are not deadlocked if $x$ is removed from $G$. A directed graph is cyclically reducible if and only if there exists a sequence of vertices $(y_1, \ldots, y_k)$ such that each of the graphs $A(G_{i-1},y_i)$ is cyclic, where $G_0 = G$ and $G_i = G_{i-1} - A(G_i, y_i)$, for $1 \leq i \leq k$.

A set is called a feedback vertex set if it contains at least one vertex from every cycle (Karp [2]). It is minimum if no other feedback vertex set has fewer elements.

Status

$\P$-complete (Bovet, De Agostino, and Petreschi [3]).

Remarks

Wang, Lloyd, and Soffa gave a polynomial time algorithm for computing feedback sets in cyclically reducible graphs [1]. Thus, MFVS is in $\P$. The reduction to show hardness is from MCVP.

The question of whether a general graph has a feedback vertex set of size $k$ is $\NP$-complete (Karp [2]). Bovet, De Agostino, and Petreschi give an algorithm for finding a minimum feedback set in cyclically reducible graphs that requires $O(k(\log n)^2)$ time and $O(n^4)$ processors on a CREW-PRAM, where $k$ denotes the size of the minimum feedback set. Greenlaw proved that a related problem, the Lexicographically First Maximal Acyclic Subgraph Problem, is $\P$-complete [4][5].

Ramachandran proved that finding a minimum weight feedback vertex set in a reducible flow graph with arbitrary weights is $\P$-complete [6][7]. She also proved the following four problems are $\NC$ equivalent: finding a minimum feedback arc set in an unweighted reducible flow graph, finding a minimum weight feedback arc set in a reducible flow graph with unary weights on the arcs, finding a minimum weight feedback vertex set in a reducible flow graph with unary weights on the vertices, and finding a minimum cut in a flow network with unary capacities [6][7].