TY - GEN

T1 - Constant factor approximation for subset feedback set problems via a new LP relaxation

AU - Chekuri, Chandra

AU - Madan, Vivek

PY - 2016

Y1 - 2016

N2 - We consider subset feedback edge and vertex set problems in undirected graphs. The input to these problems is an undirected graph G = (V, E) and a set S = {s1, S2,.·, Sk} c V of k terminals. A cycle in G is interesting if it contains a terminal. In the Subset Feedback Edge Set problem (Subset-FES) the input graph is edge-weighted and the goal is to remove a minimum weight set of edges such that no interesting cycle remains. In the Subset Feedback Vertex Set problem (subset-FVS) the input graph is node-weighted and the goal is to remove a minimum weight set of nodes such that no interesting cycle remains. A 2-approximation is known for subset-FES [12] and a 8-approximation is known for SuBSET-FVS [13]. The algorithm and analysis for SuBSET-FVS is complicated. One reason for the difficulty in addressing feedback set problems in undirected graphs has been the lack of LP relaxations with constant factor integrality gaps; the natural LP has an integrality gap of θ(logn). In this paper, we introduce new LP relaxations for subset-FES and Subset-FVS and show that their integrality gap is at most 13. Our LP formulation and rounding are simple although the analysis is non-obvious.

AB - We consider subset feedback edge and vertex set problems in undirected graphs. The input to these problems is an undirected graph G = (V, E) and a set S = {s1, S2,.·, Sk} c V of k terminals. A cycle in G is interesting if it contains a terminal. In the Subset Feedback Edge Set problem (Subset-FES) the input graph is edge-weighted and the goal is to remove a minimum weight set of edges such that no interesting cycle remains. In the Subset Feedback Vertex Set problem (subset-FVS) the input graph is node-weighted and the goal is to remove a minimum weight set of nodes such that no interesting cycle remains. A 2-approximation is known for subset-FES [12] and a 8-approximation is known for SuBSET-FVS [13]. The algorithm and analysis for SuBSET-FVS is complicated. One reason for the difficulty in addressing feedback set problems in undirected graphs has been the lack of LP relaxations with constant factor integrality gaps; the natural LP has an integrality gap of θ(logn). In this paper, we introduce new LP relaxations for subset-FES and Subset-FVS and show that their integrality gap is at most 13. Our LP formulation and rounding are simple although the analysis is non-obvious.

UR - http://www.scopus.com/inward/record.url?scp=84963681280&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84963681280&partnerID=8YFLogxK

U2 - 10.1137/1.9781611974331.ch58

DO - 10.1137/1.9781611974331.ch58

M3 - Conference contribution

AN - SCOPUS:84963681280

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 808

EP - 820

BT - 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016

A2 - Krauthgamer, Robert

PB - Association for Computing Machinery

T2 - 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016

Y2 - 10 January 2016 through 12 January 2016

ER -