ALCOMFT-TR-03-19

Camil Demetrescu and Irene Finocchi
Combinatorial Algorithms for Feedback Problems in Directed Graphs
Rome. Work package 4. August 2003.

Abstract: Given a weighted directed graph G=(V,A), the minimum feedback arc set problem consists of finding a minimum weight set of arcs A'\subseteq A such that the directed graph (V,A\setminus A') is acyclic. Similarly, the minimum feedback vertex set problem consists of finding a minimum weight set of vertices containing at least one vertex for each directed cycle. Both problems are NP-complete. We present simple combinatorial algorithms for these problems that achieve an approximation ratio bounded by the length, in terms of number of arcs, of a longest simple cycle of the digraph.

Postscript file: ALCOMFT-TR-03-19.ps.gz (165 kb).