On approximability and LP formulations for multicut and feedback set problems

Madan, Vivek

Permalink

https://hdl.handle.net/2142/102390 Copy

Description

Title

On approximability and LP formulations for multicut and feedback set problems

Author(s)

Madan, Vivek

Issue Date

2018-08-23

Director of Research (if dissertation) or Advisor (if thesis)

Chekuri, Chandra

Doctoral Committee Chair(s)

Chekuri, Chandra

Committee Member(s)

• Har-Peled, Sariel
• Mehta, Ruta
• Chandrasekaran, Karthekeyan
• Gupta, Anupam

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

Approximation, Multicut, Feedback set, Linear programming relaxation, Hardness of approximation, Linear cut, Multiway cut, Subset feedback set, Flow-cut gap

Abstract

Graph cut algorithms are an important tool for solving optimization problems in a variety of areas in computer science. Of particular importance is the min $s$-$t$ cut problem and an efficient (polynomial time) algorithm for it. Unfortunately, efficient algorithms are not known for several other cut problems. Furthermore, the theory of NP-completeness rules out the existence of efficient algorithms for these problems if the $P\neq NP$ conjecture is true. For this reason, much of the focus has shifted to the design of approximation algorithms. Over the past 30 years significant progress has been made in understanding the approximability of various graph cut problems. In this thesis we further advance our understanding by closing some of the gaps in the known approximability results. Our results comprise of new approximation algorithms as well as new hardness of approximation bounds. For both of these, new linear programming (LP) formulations based on a labeling viewpoint play a crucial role. One of the problems we consider is a generalization of the min $s$-$t$ cut problem, known as the multicut problem. In a multicut instance, we are given an undirected or directed weighted supply graph and a set of pairs of vertices which can be encoded as a demand graph. The goal is to remove a minimum weight set of edges from the supply graph such that all the demand pairs are disconnected. We study the effect of the structure of the demand graph on the approximability of multicut. We prove several algorithmic and hardness results which unify previous results and also yield new results. Our algorithmic result generalizes the constant factor approximations known for the undirected and directed multiway cut problems to a much larger class of demand graphs. Our hardness result proves the optimality of the hitting-set LP for directed graphs. In addition to the results on multicut, we also prove results for multiway cut and another special case of multicut, called linear-3-cut. Our results exhibit tight approximability bounds in some cases and improve upon the existing bound in other cases. As a consequence, we also obtain tight approximation results for related problems. Another part of the thesis is focused on feedback set problems. In a subset feedback edge or vertex set instance, we are given an undirected edge or vertex weighted graph, and a set of terminals. The goal is to find a minimum weight set of edges or vertices which hit all of the cycles that contain some terminal vertex. There is a natural hitting-set LP which has an $\Omega(\log k)$ integrality gap for $k$ terminals. Constant factor approximation algorithms have been developed using combinatorial techniques. However, the factors are not tight, and the algorithms are sometimes complicated. Since most of the related problems admit optimal approximation algorithms using LP relaxations, lack of good LP relaxations was seen as a fundamental roadblock towards resolving the approximability of these problems. In this thesis we address this by developing new LP relaxations with constant integrality gaps for subset feedback edge and vertex set problems.

Graduation Semester

2018-12

Type of Resource

text

Permalink

http://hdl.handle.net/2142/102390

Copyright and License Information

Copyright 2018 Vivek Madan

Owning Collections