About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
SIAM Journal on Discrete Mathematics
Paper
Approximating minimum subset feedback sets in undirected graphs with applications
Abstract
Let G = (V, E) be a weighted undirected graph where all weights are at least one. We consider the following generalization of feedback set problems. Let S ⊂ V be a subset of the vertices. A cycle is called interesting if it intersects the set S. A subset feedback edge (vertex) set is a subset of the edges (vertices) that intersects all interesting cycles. In minimum subset feedback problems the goal is to find such sets of minimum weight. This problem has a variety of applications, among them genetic linkage analysis and circuit testing. The case in which S consists of a single vertex is equivalent to the multiway cut problem, in which the goal is to separate a given set of terminals. Hence, the subset feedback problem is NP-complete and also generalizes the multiway cut problem. We provide a polynomial time algorithm for approximating the subset feedback edge set problem that achieves an approximation factor of two. This implies a Δ-approximation algorithm for the subset feedback vertex set problem, where Δ is the maximum degree in G. We also consider the multicut problem and show how to achieve an O(log τ*) approximation factor for this problem, where τ* is the value of the optimal fractional solution. To achieve the O(log τ*) factor we employ a bootstrapping technique.