ملخص: Given a weighted directed graph G=(V,A), the minimum feedback arc set problem consists of finding a minimum weight set of arcs A'A such that the directed graph (V,AA') 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.

لغة: إنجليزية