Approximating minimum feedback sets and multicuts in directed graphs

G. Even, J. Naor, B. Schieber, M. Sudan

Research output: Contribution to journalArticlepeer-review

238 Scopus citations

Abstract

This paper deals with approximating feedback sets in directed graphs. We consider two related problems: the weighted feedback vertex set (FVS) problem, and the weighted feedback edge set (FES) problem. In the FVS (resp. FES) problem, one is given a directed graph with weights (each of which is at least one) on the vertices (resp. edges), and is asked to find a subset of vertices (resp. edges) with minimum total weight that intersects every directed cycle in the graph. These problems are among the classical NP-hard problems and have many applications. We also consider a generalization of these problems: SUBSET-FES and SUBSET-FES, in which the feedback set has to intersect only a subset of the directed cycles in the graph. This subset consists of all the cycles that go through a distinguished input subset of vertices and edges, denoted by X. This generalization is also NP-hard even when |X| = 2. We present approximation algorithms for the SUBSET-FVS and SUBSET-FES problems. The first algorithm we present achieves an approximation factor of O(log2|X|). The second algorithm achieves an approximation factor of O(min{log τ* log log τ*, log n log log n)}, where τ* is the value of the optimum fractional solution of the problem at hand, and n is the number of vertices in the graph. We also define a multicut problem in a special type of directed networks which we call circular networks, and show that the SUBSET-FES and SUBSET-FVS problems are equivalent to this multicut problem. Another contribution of our paper is a combinatorial algorithm that computes a (1 + ε) approximation to the fractional optimal feedback vertex set. Computing the approximate solution is much simpler and more efficient than general linear programming methods. All of our algorithms use this approximate solution.

Original languageEnglish (US)
Pages (from-to)151-174
Number of pages24
JournalAlgorithmica (New York)
Volume20
Issue number2
DOIs
StatePublished - 1998
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • Computer Science Applications
  • Applied Mathematics

Keywords

  • Feedback edge set
  • Feedback vertex set
  • Multicuts

Fingerprint

Dive into the research topics of 'Approximating minimum feedback sets and multicuts in directed graphs'. Together they form a unique fingerprint.

Cite this