Keywords

In recent years (1990) feedback set problems have been the subject of growing interest. They have found applications in many fields, including deadlock prevention [90], program verification [79], and Bayesian inference [2]. Therefore, it is natural that in the past few years there have been intensive efforts on exact and approximation algorithms for these kinds of problems. Exact algorithms have been proposed for solving the problems restricted to special classes of graphs as well as several approximation algorithms with provable bounds for the cases that are not known to be polynomially solvable. The most general feedback set problem consists in finding a minimum-weight (or minimum cardinality) set of vertices (arcs) that meets all cycles in a collection C of cycles in a graph (G, w), where w is a nonnegative function defined on the set of vertices V(G) (on the set of edges E(G)). This kind of problem is also known as the hitting cycle problem , since one must hit every cycle in C. It generalizes a number of problems, including the minimum feedback vertex (arc) set problem in both directed and undirected graphs, the subset minimum feedback vertex (arc) set problem and the graph bipartization problem , in which one must remove a minimum-weight set of vertices so that the remaining graph is bipartite. In fact, if C is the set of all cycles in G, then the hitting cycle problem is equivalent to the problem of finding the minimum feedback vertex (arc) set in a graph. If we are given a set of special vertices and C is the set of all cycles of an undirected graph G that contains some special vertex, then we have the subset feedback vertex (arc) set problem and, finally, if C contains all odd cycles of G, then we have the graph bipartization problem . All these problems are also special cases of vertex (arc) deletion problems , where one seeks a minimum-weight (or minimum cardinality) set of vertices (arcs) whose deletion gives a graph satisfying a given property. There are different versions of feedback set problems , depending on whether the graph is directed or undirected and/or the vertices (arcs) are weighted or unweighted. See [30] for a complete survey, and [91] for a general NP-hardness proof for almost all vertex and arc deletion problems restricted to planar graphs. These results apply to the planar bipartization problem, the planar (directed, undirected, or subset) feedback vertex set problems, already proved to be NP-hard [33,46]. Furthermore, it is NP-complete for planar graphs with no indegree or outdegree exceeding three [46], general graphs with no indegree or outdegree exceeding two [46], and edge-directed graphs [46].

The scope of this article is to give a complete state-of-art survey of exact and approximation algorithms and to analyze a new practical heuristic method called GRASP for solving both feedback vertex and feedback arc set problems.

Notation and Graph Representation

Throughout this paper, we use the following notation and definitions.

A graph G = (V, E) consists of a finite set of vertices V(G), and a set of arcs E(G) ⊆ V(G) × V(G).

An arc (or edge) e = (v 1, v 2) of a directed graph (digraph) G = (V, E) is an incoming arc to v 2 and an outgoing arc from v 1 and it is incident to both v 1 and v 2. If G is undirected, then e is said to be only incident to v 1 and v 2.

For each vertex i ∊ V(G), let in(i) and out(i) denote the set of incoming and outgoing edges of i, respectively. They are defined only in case of a digraph G. If G is undirected, we will take into account only the degree Δ G (i) of i as the number of edges that are incident to i in G.

Δ(G) denotes the maximum degree among all vertices of a graph G and it is called the graph degree .

A vertex v ∊ G is called an endpoint if it has degree one, a  linkpoint if it has degree two, while a vertex having degree higher than two is called a  branchpoint .

A path P in G connecting vertex u to vertex v is a sequence of arcs e 1, …, e r in E(G), such that e i = (v i , v i + 1), i = 1, …, r, with v 1 = u and v r + 1 = v. A cycle C in G is a path C = (v 1, …, v r ), with v 1 = v r .

A subgraph G′ = (V′, E′) of G = (V, E) induced by V′ is a graph such that E′ = E ∩ (V′ × V′). A graph G is said to be a  singleton , if |V(G)| = 1. Any graph G can be partitioned into isolated connected components G 1, …, G k and the partition is unique. Similarly, every feedback vertex set V′ of G can be partitioned into feedback vertex sets F 1, …, F k such that F i is a feedback vertex set of G i . Therefore, following the additive property and denoting by μ(G, w) the weight of a minimum feedback vertex (arc) set for (G, w), we have:

$$ \mu(G, w) = \sum_{i = 1}^{k}\mu(G_{i}, w). $$

The Feedback Vertex Set Problem

Formally, the feedback vertex set problem can be described as follows. Let G = (V, E) be a graph and let w: V(G) → R + be a weight function defined on the vertices of G. A  feedback vertex set of G is a subset of vertices V′⊆ V(G) such that each cycle in G contains at least one vertex in V′. In other words, a feedback vertex set V′ is a set of vertices of G such that by removing V′ from G along with all the edges incident to V′, results in a forest. The weight of a feedback vertex set is the sum of the weights of its vertices, and a  minimum feedback vertex set of a  weighted graph (G, w) is a feedback vertex set of G of minimum weight. The weight of a minimum feedback vertex set will be denoted by μ(G, w). The minimum weighted feedback vertex set problem (MWFVS) is to find a minimum feedback vertex set of a given weighted graph (G, w). The special case of identical weights is called the unweighted feedback vertex set problem (UFVS).

Mathematical Model of the Feedback Vertex Set Problem

As a covering-type problem, the feedback vertex set problem admits an integer zero-one programming formulation. Given a feedback vertex set V′ for a graph (G, w), G = (V, E), and a set of weights w = {w(v)} v ∊ V(G), let x = {x v } v ∊ V(G) be a binary vector such that x v = 1 if v ∊ V′, and x v = 0 otherwise. Let C be the set of cycles in (G, w). The problem of finding the minimum feedback vertex set of G can be formulated as an integer programming problem as follows:

$$ \begin{cases} \displaystyle \min & \displaystyle \sum_{v \in V(G)}w(v) x_{v} \\ \text{s.t.} & \displaystyle \sum_{v\in V( \Gamma)}x_{v}\ge 1, \quad \forall \Gamma\in C, \\ & 0\le x_{v}\le 1\ \text{integer}, \quad v\in V(G). \end{cases} $$

If one denotes by C v the set of cycles passing through vertex v ∊ V(G), then the dual of the corresponding linear programming relaxation is a  packing problem :

$$ \begin{cases} \displaystyle \max & \displaystyle \sum_{\Gamma \in C} y_{\Gamma} \\ \text{s.t.} & \displaystyle \sum_{\Gamma\in C_{v}}y_{\Gamma}\le w(v), \quad \forall v\in V(G), \\ & y_{\Gamma}\ge 0, \quad \forall \Gamma\in C. \end{cases} $$

Polynomially Solvable Cases

Given the NP-completeness of the feedback vertex set problem, a recent line of research has focused on identifying the largest class of specially structured graphs on which such problems remain polynomially solvable. A pioneering work is due to A. Shamir [79], who proposed a linear time algorithm to find a feedback vertex set for a reducible flow graph. C. Wang, E. Lloyd, and M. Soffa [90] developed an O(|E(G)|·|V(G)|2) algorithm for finding a feedback vertex set in the class of graphs known as cyclically reducible graphs , which is shown to be unrelated to the class of quasireducible graphs. Although the exact algorithm proposed by G.W. Smith and R.B. Walford [83] has exponential running time in general, it returns an optimal solution in polynomial time for certain types of graphs. A variant of the algorithm, called the Smith–Walford-one algorithm , selects only candidate sets F of size one and runs in O(|E(G)|·|V(G)|2) time. The class of graphs for which it finds a feedback vertex set is called Smith–Walford one-reducible . In the study of feedback vertex set problems a set of operations called contraction operations has had significant impact. They contract the graph G(V, E), while preserving all the important properties relevant to the minimum feedback vertex set. See [56] for a detailed analysis of these reduction procedures which are important for the following two reasons. First, a class of graphs of increasing size is computed, where the feedback vertex set of each graph can be found exactly. Second, most proposed heuristics and approximation algorithms use the reduction schemes in order to reduce the size of the problem. Another line of research on polynomially solvable cases focuses on other special classes, including chordal and interval graphs , permutation graphs , convex bipartite graphs , cocomparability graphs and on meshes and toroidal meshes , butterflies , and toroidal butterflies . The feedback vertex set on chordal and interval graphs can be viewed as a special instance of the generalized clique cover problem, which is solved in polynomial time on chordal graphs [20,93] and interval graphs [65]. For permutation graphs, an algorithm due to A. Brandstädt and D. Kratsch [8] was improved by Brandstädt [7] to run in O(|V(G)|6) time. More recently (1994), Y.D. Liang [58] presented an O(|V(G)|·|E(G)|) algorithm for permutation graphs that can be easily extended to trapezoid graphs while keeping the same time complexity. On interval graphs, C.L. Lu and C.Y. Tang [61] developed a linear-time algorithm to solve the minimum weighted feedback vertex set problem using dynamic programming. S.R. Coorg and C.P. Rangan [19] present an O(|V(G)|4) time and O(|V(G)|4) space exact algorithm for cocomparability graphs, which are a superclass of permutation graphs. More recently, Liang and M.S. Chang [13] developed a polynomial time algorithm, that by exploring the structural properties of a cocomparability graph uses dynamic programming to get a minimum feedback vertex set in O(|V(G)2| |E(G)|) time. A recent (1998) line of research [63] on polynomially solvable cases focuses on special undirected graphs having bounded degree and that are widely used as connection networks, namely mesh, butterfly and k-dimensional cube connected cycle (CCC k ).

Approximation Algorithms and Provable Bounds on Undirected Graphs

A 2 log2|V(G)|-approximation algorithm for the unweighted minimum feedback vertex set problem on undirected graphs is contained in a lemma due to P. Erdös and L. Posa [25]. This result was improved in [66] to obtain a performance ratio of \( O(\sqrt{\log |V(G)|}) \). R. Bar-Yeruda, D. Geiger, J. Naor, and R.M. Roth [2] gave an approximation algorithm for the unweighted undirected case having ratio less than or equal to 4 and two approximation algorithms for the weighted undirected case having ratios 4 log2 |V(G)| and 2Δ2(G), respectively. To speedup the algorithm, they show how to preprocess the input valid graph by applying the corresponding undirected versions of the Levy–Lowe reduction transformations. For the feedback vertex set problem in general undirected graphs, two slightly different 2-approximation algorithms are described in [3] and [1]. These algorithms improve the approximation algorithms of [2]. They also can find a loop cutset which, under specific conditions, is guaranteed in the worst case to contain less than four times the number of variables contained in a minimum loop cutset. Subsequently, A. Becker and Geiger [4] applied the same reduction procedure from the loop cutset problem to the minimum weighted feedback vertex set problem of [2], but their result is independent of any condition and is guaranteed in the worst case to contain less than twice the number of variables contained in a minimum loop cutset. They [4] propose two greedy approximation algorithms for finding the minimum feedback vertex set V′ in a vertex-weighted undirected graph (G, w), one of them having performance ratio bounded by the constant 2 and complexity O(m+n log n), where m = |E(G)| and n = |V(G)|. In [17], F.A. Chudak, M.X. Goemans, D. Hochbaum, and D.P. Williamson showed how the algorithms due to Becker and Geiger [3] and V. Bafna, P. Berman, and T. Fujito [1] can be explained in terms of the primal-dual method for approximation algorithms that are used to obtain approximation algorithms for network design problems. The primal-dual method starts with an integer programming formulation of the problem under consideration. It then simultaneously builds a feasible integral solution and a feasible solution to the dual of the linear programming relaxation. If it can be shown that the value of these two solutions is within a factor of α, then an α-approximation algorithm is found. The integrality gap of an integer program is the worst-case ratio between the optimum value of the integer program and the optimum value of its linear relaxation. Therefore, by applying the primal-dual method it is possible to proof that the integrality gap of the integer program under consideration is bounded. In fact, Chudak et al., after giving a new integer programming formulation of the feedback vertex set problem, provided a proof that its integrality gap is at most 2. They also gave the proofs of some key inequalities needed to prove the correctness of their new integer programming formulation.

Theorem 1

Let V′ denote any feedback vertex set of a graph G = (V, E), E ≠ ∅, let τ denote the cardinality of the smallest feedback vertex set for G, and let E(S) denote the subset of edges that have both endpoints in S ⊆ V(G), b(S) = |E(S)| − |S|+1. Then

$$ \sum_{v\in V^{\prime}}[ \Delta_{G}(v) - 1]\ge b(V(G)), $$
(1)
$$ \sum_{v\in V^{\prime}} \Delta_{G}(v)\ge b(V(G))+\tau. $$
(2)

If every vertex in G has degree at least two, and V′ M is any minimal feedback vertex set (i. e. ∀ v ∊ V′ M , V′ M \ {v} is not a feedback vertex set), then

$$ \sum_{v\in {V^{\prime}}_{M}} \Delta_{G}(v)\le 2 (b(V(G))+\tau)-2. $$
(3)

G. Even, Naor, B. Schieber, and L. Zosin [28] showed that the integrality gap of that integer program for the standard cycle formulation of the feedback vertex set problem is Ω(log n). The new integer programming formulation given in [17] is as follows:

$$ \begin{cases} \displaystyle \min & \displaystyle \sum_{v \in V(G)}w(v) x_{v} \\ \text{s.t.} & \displaystyle \sum_{v\in S}( \Delta_{S}(v) - 1) x_{v}\ge b(S), \\ & \quad S\subseteq V(G):\ E(S)\neq \emptyset, \\ & x_{v}\in \{ 0, 1\}, \quad v\in V(G). \end{cases} $$

The linear programming relaxation is:

$$ \begin{cases} \displaystyle \min & \displaystyle \sum_{v \in V(G)}w(v) x_{v} \\ \text{s.t.} & \displaystyle \sum_{v\in S}( \Delta_{S}(v) - 1) x_{v}\ge b(S), \\ & \quad S\subseteq V(G):\ E(S)\neq \emptyset, \\ & x_{v}\ge 0, \quad v\in V(, G), \end{cases} $$

and its dual is:

$$ \begin{cases} \displaystyle \max & \displaystyle \sum_{S} b(S) y_{S} \\ \text{s.t.} & \displaystyle \sum_{S: v\in S}(\Delta_{S}(v) - 1) y_{S}\le w_{v}, \quad v\in V(G), \\ & y_{S}\ge 0, \quad S\subseteq V(G):\ E(S)\neq \emptyset. \end{cases} $$

For the subset feedback vertex problem, the authors of [28] showed that it can be approximated in polynomial time by a factor of min{2 Δ(G), 8 log(|V′|+1), O(log τ∗)}, where τ∗ denotes the value of the optimal fractional solution. In [28] the authors also proposed a technique, called bootstrapping , that enhances the O(log |V′|) to a factor of O(log τ∗/β), where β denotes the minimum weight of a vertex. The bootstrapping technique iteratively uses a graph partition algorithm. The output of each iteration is by itself a subset feedback vertex set and is used as part of the input of the next iteration. After O(log |V′|) iterations the algorithm gives as output a subset feedback vertex set having weight at most O(τ∗ log τ∗). Even, Naor and Zosin [26] improved this result proposing an 8-approximation algorithm. The main tool that they used in developing their approximation algorithm and its analysis is a new version of multicommodity flow, called relaxed multicommodity flow , a hybrid of multicommodity flow and multiterminal flow, in which there are additional constraints, called intercommodity constraints . For each arc, the authors considered the maximum flow among all the commodities, which is shipped along it. They required that for each vertex v ∊ V(G) the sum of the maximum flows shipped along its incident arcs be bounded by four times the capacity of v. By considering the multicommodity flow, the vertices for which the intercommodity constraints are tight play an important role from the point of view of the connectivity of the graph. They are called intersatured vertices . The main result of [26] is a theorem that bounds the weight of the vertices that must be intersatured, so as to satisfy a given demand vector by the sum of demands.

Approximation Algorithms and Provable Bounds on Directed Graphs

In general, problems on undirected graphs are relatively easier to handle than problems on directed graphs, since more graph theory can be utilized. Not surprisingly, the approximation results obtained so far for the undirected version are stronger than those for the directed version. In fact, none of the algorithms referred to in the previous subsections apply to the feedback vertex set problem in directed graphs and, in contrast with the undirected version, no analytical results are known for the directed case. A very recent direction of research on approximation algorithms in the directed version focuses on the complete equivalence among all feedback set (and/or feedback subset) problems and among these and the directed minimum capacity multicut problem in circular networks. An exhaustive description of the procedures that reduce any feedback set problem to any other or any of them to the directed minimum capacity multicut problem and vice versa are formalized and used in [27] to obtain an approximation algorithm for the subset feedback arc set problem of a weighted directed graph G = (V, E), where the interesting cycles to be hit are contained in a set of special vertices X ⊆ V(G), where |X| = k. The weight of the feedback arc set found by their approximation algorithm is O(τ∗ log2|X|), where τ∗ is the weight of an optimal fractional feedback set. Nevertheless, their approach can be used to solve any other feedback set problem as well as the directed minimum capacity multicut problem. Even et al. [27] also proposed an algorithm for approximating the minimum weighted subset vertex set problem in the weighted and directed case, leading to a result that holds for any other feedback set problem as well. This approach is an algorithmic adaptation of a theoretical result due to P.D. Seymour [78], who proved that the integrality gap in the case of the unweighted feedback vertex set problem can be at most O(log τ∗ log log τ∗), where τ∗ is defined as above. Even et al. observe that all existence arguments contained in the proof of Seymour's statement can be made constructive and thus, with some additional operations, an algorithm for the unweighted feedback vertex set problem having an approximation factor of O(log τ∗ log log τ∗) can be obtained. Further modifications of the algorithm lead to a polynomial time approximation scheme applicable to the weighted problem. In O(|E(G)|·|V(G)|2) time the algorithm finds a feedback vertex set having weight

$$ O\left(\min\left\{\tau^{\ast}\log \tau^{\ast}\log\log \tau^{\ast}, \right.\right. \\ \left.\left. \tau^{\ast}\log |V(G)| \log\log |V(G)|\right\}\right). $$

All the observations contained in [27] improve the O(log2 |V(G)|)-approximation algorithm for this case [54]. In the case of directed planar graphs, H. Stamm [86] presented an O(|V(G)|log |V(G)|)-approximation algorithm, whose performance guarantee is bounded by the maximum degree of the graph and an O(|V(G)|2) time approximation algorithm with performance guarantee no more than the number of cyclic faces in the planar embedding of the graph minus 1. M. Cai, X. Deng, and W. Zang [10] obtained a 2.5-approximation algorithm for the minimum feedback vertex set problem on tournaments, improving the previously known algorithm with performance guarantee of 3 by E. Speckenmeyer [85]. Let H be the triangle-vertex incidence matrix of a tournament T and let e be the all-one vector. In [10], necessary and sufficient conditions are established for the linear system {x: Hx ≥ e, x ≥ 0} to be a totally dual integral system (TDI).

Definition 2

A rational linear system {x: Ax ≥ b, x ≥ 0} is called totally dual integral , if the optimization problem max {y ⊺ b: y ⊺ A ≤ c ⊺, y ≥ 0} has an integral optimum solution y for every integral vector c for which the maximum is finite.

It has been shown that any rational polyhedron P has a  TDI system P = {x: Ax ≤ b} representation with A integral, and that, if P is full-dimension, there is a unique minimal TDI system P = {x: Ax ≤ b} with A and b integral if and only if P is integral. In [11] the authors have extended this approach to the feedback vertex set problems and the cycle packing problem in bipartite tournaments , where a bipartite tournament is an orientation of a complete bipartite graph. For the aforementioned problems they have found strongly polynomial time algorithms, which are a consequence of a min-max relaxation on packing and covering directed cycles.

Exact Algorithms

In contrast to the numerous approximation schemes that have been studied, relatively few exact algorithms for the feedback vertex set problem have been proposed. To our knowledge, the first algorithm to find an exact minimal cardinality FVS is due to Smith and Walford [83], who proposed a particular graph partition technique. Although their algorithm solves the problem in an arbitrary directed graph in exponential running time, it returns an optimal solution in polynomial time for certain types of graphs. Later, exact algorithms of enumerative nature often used the graph reduction procedures to speed up the process. One study, [16], essentially used direct enumeration plus reduction and reported satisfactory computational results for a set of partial scan design test problems. T. Orenstein, Z. Kohavi, and I. Pomeranz [67] proposed a somewhat more involved exact enumerative procedure based on graph reduction and efficient graph partitioning methods. Their algorithm has been designed for identifying a minimum feedback vertex set in a digital circuit and it is efficient in random graphs, even though in cliques or graphs that are ‘almost’ cliques it has an exponential behavior, since the reduction and partition techniques cannot be applied.

Somewhat surprising, exact algorithms for feedback vertex set based on mathematical programming formulation are quite few. Recently (1996), M. Funke and G. Reinelt [32] considered a special variant of feedback problems, namely the problem of finding a maximum weight node induced acyclic subdigraph. They discussed valid and facet defining inequalities for the associated polytope and developed a polyhedral-based exact algorithm presenting computational results obtained by applying a branch and cut algorithm.

The Feedback Arc Set Problem

Given a graph G = (V, E) and a nonnegative weight function w: E(G) → R + defined on the arcs of G, the feedback arc set problem consists of finding a minimum-weight subset of arcs E′ ⊆ E(G) that meets every cycle in a given collection C of cycles in (G, w). As in the vertex case, this leads to the minimum feedback arc set problem (MWFAS) in both directed and undirected graphs, the minimum weighted graph bipartization problem via arc removals, and so on.

Mathematical Model of the Feedback Arc Set Problem

Given an arc weighted graph (G, w), G = (V, E) and the set C of all cycles in G, the minimum weighted feedback arc set problem can be formulated as the following integer programming problem:

$$ \begin{cases} \displaystyle \min & \displaystyle \sum_{e \in E(G)}w(e) x_{e} \\ \text{s.t.} & \displaystyle \sum_{e\in \Gamma}x_{e}\ge 1, \quad \forall \Gamma\in C, \\ & x_{e}\in \{ 0, 1\}, \quad \forall e\in E(G). \end{cases} $$

In its relaxation, the constraints x e ∊ {0, 1}, ∀ e ∊ E(G) are replaced by x e ≥ 0, ∀ e ∊ E(G), obtaining a fractional feedback arc set. As with the feedback vertex set problem, the feedback arc set problem is a  covering problem and its (linear programming) dual is called a  packing problem . In the case of the feedback arc set problem this means assigning a dual variable to all interesting cycles to be hit in the given graph, such that for each arc the sum of the variables corresponding to the interesting cycles passing through that arc is at most the weight of the arc itself.

State of the Art of Feedback Arc Set Problems

Feedback arc set problems tend to be easier than their vertex counterparts, especially for planar graphs. In the directed case feedback vertex and feedback arc set problems are each reducible to one another. Even, Naor, Schieber, and Sudan [27] showed how to perform reductions among feedback set problems and feedback subset problems and vice versa, preserving feasible solutions and their costs. In all reductions, there is a one-to-one correspondence between feasible solutions and their corresponding costs. Therefore, an approximate solution to one problem can be translated to an approximate solution of the other problem reducible to this problem. Because most of the reduction procedures can be performed in linear time, these problems can be viewed as different representations of the same problem. Hence, as feedback vertex sets are reduced into feedback arc sets with the same weight and vice versa, all of these problems are equally hard to approximate. In the literature of feedback set problems most of the proposed algorithms are designed to solve the problem in vertex-weighted graphs. One of the pioneering papers on feedback arc set problems is [76], where it is proved that finding a minimum feedback arc set in an arc-weighted reducible flow graph is as difficult as finding a minimum cut in a flow network. The proposed algorithm has complexity O(m n 2 log (n 2/m)), where m = |E(G)| and n = |V(G)|. The algorithm was adapted to solve the problem in the vertex-weighted case. Shamir's linear time algorithm [79], used for the unit-weighted case, cannot be applied to solve the arc-weighted problem, because any reduction between arc and vertex set problems does not preserve the reducibility property. Given a directed graph G = (V, E), a  dijoin E′ ⊆ E(G) is a set of arcs such that the graph G′ = (V, B), B = E ∪ {(v, u): (u, v)∊ E′} is strongly connected. Given nonnegative weights w e , e ∊ E(G), the minimum-weight dijoin problem is to find the dijoin with minimum weight. The feedback arc set problem in planar digraphs is reducible to the problem of finding a minimum-weight dijoin in the dual graph, which is solvable in polynomial time [39]. Stamm [86] proposed a simple 2-approximation algorithm for the minimum weight dijoin problem by superposing two arborescences. It is interesting to observe that, when translated to the dual graph, all these problems lead to problems of hitting certain cutsets of the dual graph, problems which can be approximated within a ratio of 2 by the primal-dual method. Goemans and Williamson [37] proposed a primal-dual algorithm that finds a 9/4-approximate solution to feedback set problems in planar graphs. The first approximation algorithm for the feedback arc set problem was given in [54]. The approximation factor is O(log2 n) in the unweighted case, where n is the number of vertices of the input graph. This bound was obtained by using a O(log n) approximation algorithm for a directed separator that splits the graph into two approximately equally-sized components, S and \( \overline{S} \). This separator can be found by approximating special cuts called quotient cuts . This result was improved by Seymour [78], who gave a O(log n log log n)-approximation algorithm that solves the linear relaxation of the feedback arc set mathematical model and then interprets the optimal fractional solution x ∗ as a length function defined on the arcs. Systematically, in a recursive fashion, it uses this length function to delete from the graph G all arcs between S and \( \overline{S} \). Note that the linear program can be solved in polynomial time by using the ellipsoid or an interior point algorithm. Hence, the quality of the bound in this approach depends on the way the graph is partitioned. Seymour [78] proved the following lemma:

Lemma 3

For a given strongly connected digraph G = (V, E), suppose there exists a feasible solution x to the feedback arc set problem. If ϕ is the value of the optimal fractional solution x ∗, then there exists a partition \( (S, \overline{S}) \) such that, for some ϵ, 0 < ϵ < 1, the following conditions hold: If \( \delta^{ +} (S) = \{(u, v)\colon\ (u, v)\in E(G), \ u\in S, \ v\in \overline{S}\} \) and \( \delta^{ -} (S) = \{(v, u)\colon\ (v, u)\in E(G), \ u\in S, \ v\in \overline{S}\} \), then the following is true:

$$ \sum_{e\in E(S)} w(e) x(e)\le \epsilon\phi, $$
(4)
$$ \sum_{e\in E( \overline{S})}w(e) x(e)\le (1 - \epsilon)\phi, $$
(5)

and either

$$ \sum_{e\in \delta^{ +} (S)} w(e)\le 20\epsilon\phi\log\left( \frac{1}{\epsilon}\right)\log\log\phi $$
(6)

or

$$ \sum_{e\in \delta^{ -} ( S)} w(e)\le 20\epsilon\phi\log\left( \frac{1}{\epsilon} \right)\log\log\phi. $$
(7)

Furthermore, the partition \( (S, \overline{S}) \) can be found in polynomial time.

This Lemma admits a constructive proof, [27]. The algorithm in this proof finds a feedback arc set having weight O(τ∗ log2|X|), where X is a special set of vertices defining the cycles to be hit and τ∗ is the weight of an optimal fractional feedback set. The idea is to reduce the problem to the directed minimum capacity multicut problem in circular networks and of adapting the undirected sphere growing technique described in [35] to directed circular networks. Then the graph is decomposed in the following way. A fractional and optimal solution to the directed feedback set problem induces a distance metric on the set of arcs (on the set of vertices) E(G). The approximation algorithm arbitrarily picks a vertex v ∊ X and solves the shortest path tree problem rooted at v with respect to the metric induced by the fractional solution. The procedure that finds the shortest path tree defines layers with respect to the source v. Each layer is a directed cut that partitions the graph into two parts. The next step of the approximation algorithm is to choose a directed cut and to add the cut to the feedback set constructed so far. The algorithm continues recursively in each part and ends when the graph does not contain any interesting cycles. The key of the algorithm is the choice of the criterion to select the directed cut that partitions the graph. Even et al. decided to relate the weight of the cut to the cost of the fractional solution. More recently (1996), Even, Naor, Schieber, and Zosin [28] showed that, for any weight function defined on the arcs, the subset feedback arc set problem can be approximated in polynomial time by a factor of two. The approximation algorithm consists of successive computations of minimum cuts. Its approximation factor is estimated by considering the capacities of minimum cuts as flow paths. When new minimum cuts are computed, previous flow paths are updated according to the decomposition of the graph induced by an optimal solution.

A GRASP for Feedback Set Problems

Although the approximation algorithms guarantee a solution of a certain quality, for many practical real world cases, heuristic methods can lead to better solutions in a reasonable amount of CPU time. Metaheuristics, such as genetic algorithms, simulated annealing, greedy randomized adaptive search procedures (GRASP), Lagrangian relaxation, and others have been developed with successful computational performance on a wide range of combinatorial optimization problems. Interestingly, however, feedback vertex set problems seem to be an exception. For this family of problems relatively few practical heuristics have been developed. Furthermore, most of the heuristics that seem to be quite successful computationally are greedy type heuristics or generalized greedy type heuristics (e. g. GRASP). Almost all the efficient heuristics developed so far employ the solution-preserved reduction rules studied in [56]. It has been observed in practice that this group of heuristics greatly reduces the cardinality of the graph not only at the beginning of the algorithm, but also dynamically during the execution of node deletion type heuristics. A recent line of research on heuristic approaches is due to P.M. Pardalos, T. Qian, and M.G.C. Resende [70] where three variants of the so-called greedy randomized adaptive search procedure (GRASP) metaheuristic are proposed for finding approximate solutions of large instances of the feedback vertex set problem in a digraph. GRASP is a multistart method characterized by two phases: a construction phase and a local search phase, also known as a local improvement phase. During the construction phase a feasible solution is iteratively constructed. One element at time is randomly chosen from a  restricted candidate list ( RCL), whose elements are sorted according to some greedy criterion, and is added to the building feedback vertex set and removed from the graph with all its incident arcs. Since the computed solution, in general, may not be locally optimal with respect to the adopted neighborhood definition, the local search phase tries to improve it. These two phases are iterated and the best solution found is kept as an approximation of the optimal solution. To improve the efficiency of the method, Pardalos et al. incorporated in each iteration of their algorithm solution-preserving graph reduction techniques in their directed version and that can be used also to check if a digraph is acyclic, returning an empty reduced graph in case of positive answer. The authors employed the following three greedy functions used to select the node with the maximum G(i) values:

  • G A (i) = in(i) + out(i);

  • G B (i) = in(i) ∗ out(i);

  • G C (i) = max {in(i), out(i)}.

Greedy function G A assigns equal weight to in- and out-degrees. G B favors the balance between in- and out-degrees. G C only considers the largest value of the degrees. As demonstrated in [70], G B produced the best computational results. GRASP was tested on two randomly generated problem sets, finding the optimal solutions to all the problems in the first set, where the optimal values are known (computed in [32]). Furthermore, this GRASP dominates the pure greedy heuristics in all the test instances with comparable running time. In [31], Fortran subroutines are given for finding approximate solutions of both the directed feedback vertex set problem and the directed feedback arc set problem using GRASP. The subroutines for solving approximately the feedback vertex set problem corresponds to the pseudocode algorithm proposed in [70]. The subroutines for solving approximately the feedback arc set problem uses a linear-time procedure proposed in [27] in order to reduce the given feedback arc set problem instance to an equivalent feedback vertex set problem instance, and then the reduced vertex version problem is solved.

Future Research

As has been pointed out in [38], fast construction heuristics combined with local improvement techniques tailored for special applications have been the ‘workhorse’ of combinatorial optimization in practice. As the design of efficient construction heuristics and local search procedures will be a key to the effective computational procedure for feedback set problems, new approaches are considered that will lead to higher quality solution. New variants of the classical GRASP approach are considered, called Reactive GRASP techniques. The first idea along this line has been due to M. Prais and C.C. Ribeiro [74], who used reactive GRASP to a matrix decomposition problem arising in the context of traffic scheduling in satellite-division-multiple-access systems (SS/TDMA). In the reactive GRASP, the restricted candidate list parameter α is not fixed, but selfadjusted according to the quality of the solution previously found during the search. In more detail, the parameter α is randomly chosen from a set of m predeterminated acceptable values A = {α1, …, α m }. Associated with the choice of α i there is a probability p i , initially corresponding to a uniform distribution. During the search phase some information is collected in order to change the discrete set of probabilities {p i } i = 1, …, m . Several possible strategies can be explored for this update operation. One among them has been proposed by Prais and Ribeiro. It is an absolute qualification rule , based on the average value of the solutions obtained with each value of α = α i . Once chosen the updating criterion of the probabilities {p i } i = 1, …, m, it is possible to use different values of α at different iterations. Therefore, different restricted candidate lists can be built and eventually different solutions can be constructed, which would never be built by using a single, fixed value of α.

T.A. Feo and Resende have discussed in [29] the effects the parameter α can have on the quality of the solution and, at least analyzing the results obtained by Prais and Ribeiro, it seems that α can have an evident impact on the outcome of a GRASP procedure.

Conclusions

Despite the large body of work on approximation algorithms, computational studies of feedback set problems seem to be still in their embryonic stage. No modern metaheuristics, except the GRASP procedure recently (1996) developed in [70] have ever been applied to the feedback vertex set problem. The size of the general problem that can be handled is still quite limited. It seems that this area of computational research has the greatest potential for progress and impact in the coming years. It has to be also underlined that, since detecting cycles is a relatively expensive operation, the local search of feedback vertex set appears to be even more difficult than other notorious combinatorial problems like the traveling salesperson or set covering problems. Therefore, the design of efficient local search procedures and fast construction heuristics will be a key to the effective computational procedure for feedback set problems.

See also

Generalized Assignment Problem

Graph Coloring

Graph Planarization

Greedy Randomized Adaptive Search Procedures

Quadratic Assignment Problem

Quadratic Semi-assignment Problem