Graph Cuts

Prior to the workshop, on 9th of April, we plan to organize an update meeting on parameterized complexity of graph separation problems.

The topic of graph separation problems, starting from a paper of Dániel Marx in 2004, has become one of the most active subareas of parameterized complexity in the last few years. The developed techniques turned out to be robust enough to yield FPT algorithms for Directed Feedback Vertex Set and its variants as well as Almost 2-SAT. Among many works, fixed-parameter tractability of Multicut (Marx-Razgon and Bousquet et al) and k-Way Cut has been estabilished. At ICALP 2012, 6 out of 10 papers on parameterized complexity was related to graph separation problems.

The aim of the update meeting is twofold. First, we would like to summarize the current state of knowledge, update on recent (and very interesting) techniques, and identify next goals. Second, we would like to give the opportunity to the `newcomers' to get compact knowledge on latest toolbox and current challenges. Thus, the update meeting will be mostly focused on techniques and open problems.

Programme

Here you can find the programme of the main part of the workshop.

9:30-9:55 Marcin Pilipczuk, Introduction and a glimpse on the history.
9:55-10:45 Dániel Marx, Important separators.
10:45-11:10 Coffee break
11:10-11:50 Marek Cygan, Shadow removal.
11:50-12:30 Daniel Lokshtanov, LP-guided branching algorithms.
12:30-13:30 Lunch
13:30-14:15 Igor Razgon, Finding small separators in linear time via treewidth reduction.
14:15-15:00 Michał Pilipczuk, Randomized contractions.
15:00-15:30 Coffee break
15:30-16:10 MS Ramanujan, Parity constrained graph separation problems.
16:10-17:30 Open problem session

Abstracts

Marcin Pilipczuk, Introduction and a glimpse on the history

Slides.

In my short introductory talk, I will take a brief tour over the parameterized complexity of graph separation problems, putting the results on the timeline and pointing out milestones and crucial ideas.

Dániel Marx, Important separators

Slides.

The notion of important separators and bounding the number of such separators turned out to be a very useful technique in the design of parameterized cut and transversal problems. For example, the fixed-parameter tractability of Undirected Multiway Cut and Directed Feedback Vertex Set can be conveniently explained using this notion. In my talk, I will overview some of the combinatorial and algorithmic results that can be obtained by studying such separators.

Marek Cygan, Shadow removal

Slides.

Shadow removal is a technique involving random sampling of important separators. For the first time it was used by Marx and Razgon in the FPT algorithm for the multicut problem. Later the technique was also used for directed multiway cut (Chitnis, Hajiaghayi, Marx), directed multicut in dags, directed subset feedback vertex set and graph clustering.

In the talk we will see a general form of the shadow removal theorem, which is a joint work with Rajesh Chitnis, Mohammadtaghi Hajiaghayi and Daniel Marx, together some applications to the mentioned problems.

Daniel Lokshtanov, LP-guided branching algorithms

Slides.

Igor Razgon, Finding small separators in linear time via treewidth reduction

Slides.

We introduce the so-called Treewidth Reduction Theorem. Given a graph G, two specified vertices s and t, and an integer k, let C be the union of all minimal s-t (vertex) separators of size at most k. Furthermore, let G* be the graph obtained from G by contracting all the connected components of G - C into single vertices. The theorem states that the treewidth of G* is bounded by a function of k and that the graph G* can be computed in linear time for any fixed k.

The above theorem allows us to solve the following generic graph separation problem in linear time for every fixed k. Let G be a graph with two specified vertices s and t and let Z be a hereditary class of graphs. The problem asks if G has an s-t vertex separator S of size at most k such that the subgraph induced by S belongs to the class Z.

In other words, we show that this generic problem is fixed-parameter tractable. This allows us to resolve a number of seemingly unrelated open questions scattered in the literature concerning fixed-parameter tractability of various graph separation problems under specific constraints.

The role of the Treewidth Reduction Theorem is that it reduces an arbitrary instance of the given problem to an instance of the problem where the treewidth is bounded. Then the standard methodology using Courcelle's theorem can be applied.

The purpose of this talk is to convey the main technical ideas of the above work at an intuitive level. Joint work with D. Marx and B. O'Sullivan. Available at http://arxiv.org/abs/1110.4765.

Michał Pilipczuk, Randomized contractions

Slides.

During the talk I will describe a new technique for designing fixed-parameter algorithms for cut problems, namely randomized contractions. The approach heavily exploits the colour coding technique of Alon, Yuster, and Zwick, and can be viewed as an alternative for important separators. In particular, using our framework we were able to obtain a number of new algorithmic results for several important problems. More precisely, we obtained the first FPT algorithm for the Unique Label Cover problem and new FPT algorithms with exponential speed up for the Steiner Cut and Node Multiway Cut-Uncut problems.

A joint work with Rajesh Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi, and Marcin Pilipczuk, published at FOCS 2012.

MS Ramanujan, Parity constrained graph separation problems

Slides.

In this talk, we will mainly describe a generalization of important separators which allows us to perform (not necessarily parity based) constrained separation where the constraint is placed on certain parts of the graph disjoint from the separator. Following this, we will look at a shadow removal operation which seems very useful for parity based graph separation problems. We will describe both these ideas from the point of view of 2 parity based problems- a parity version of the multiway cut problem and the subset version of the odd cycle transversal problem.

The ideas which will be outlined in the talk led to a proof of the fixed parameter tractability of the parity version of multiway cut and a faster fixed parameter tractable algorithm for the subset version of odd cycle transversal. This is joint work with Daniel Lokshtanov, Pranabendu Misra and Saket Saurabh.