Operations Research Seminar
— 2:30pm
Location:
In Person

Tepper 4242
Speaker:
CHANDRA CHEKURI
,
Paul and Cynthia Saylor Professor, Algorithms / Theory Group, Department of Computer Science, University of Illinois, UrbanaChampaign
http://chekuri.cs.illinois.edu/
Polyhedral Formulations for (Subset) Feedback Vertex Set
We consider feedback vertex set (FVS) in undirected graphs, and its generalization the subset feedback vertex set (SFVS) problem. In FVS the input is a vertexweighted graph G=(V,E) and the goal is to remove a minimum weight susbet of vertices S such that the GS has no cycles. In SFVS we are also given a subset T of the vertices called terminals, and the goal is to remove a minimum weight subset of vertices S such that GS has no cycle containing a terminal. FVS is a wellknown NPHard problem and admits a 2approximation from several decades ago via the localratio method (Bafna et al, Becker and Geiger). Moreover 2 is the best approximation ratio one can hope for assuming the unique games conjecture. Chudak et al. developed an LP relaxation for FVS and interpreted the localratio algorithms as primaldual algorithms with respect to this relaxation. However, their LP relaxation was not known to be solvable in polynomial time.
We develop a new LP relaxation that is polytime solvable and has an integrality gap of 2. This LP relaxation is based on a connection to a relaxation for densest subgraph by Charikar. A few years ago Chekuri and Madan developed a polytime solvable LP relaxation for the more general SFVS problem and they showed that it had an integrality gap of at most 13 via a rounding algorithm. They raised the question of whether their LP relaxation had an integrality gap of at most 2 for FVS (and also SFVS). We answer this question in the affirmative for FVS. Despite proving that these two LP relaxations (which come from different perspectives on the problem) have an integrality gap of at most 2 for FVS, we do not know a direct way to round the relaxations to achieve this bound. We conjecture an extreme point property for one of the LP relaxations that would allow one to obtain an iterated rounding 2approximation algorithm, and provide evidence for this conjecture via a related result for the pseudoforest deletion set problem.
The goal of the talk is to highlight the ideas and connections behind the several LP relaxations for these problems, and to point out several open problems.
Based on joint work with Karthik Chandrasekharan, Samuel Fiorini, Shubhang Kulkarni, and Stefan Weltge , and an older paper with Vivek Madan
—
Chandra Chekuri is the Paul and Cynthia Saylor Professor in the Department of Computer Science at University of Illinois, UrbanaChampaign. He joined the university in 2006 after spending eight years at Lucent Bell Labs. Prior to that he received his PhD from Stanford University and an undergraduate degree from IIT Chennai. He is interested in the design and analysis of algorithms, combinatorial optimization, and theoretical computer science. He is happy about some of his contributions to (fast) approximation algorithms, graphs and networks, scheduling, and optimizing with submodular functions.