Programme

Please note also the programme of the Update Meeting on Graph-Separation Problems.

Wednesday, 10th April
9:30-11:00 Piotr Sankowski, Monge Property, Dense Distance Graphs and Speeding-up Max-Flow Computations in Planar Graphs.
11:00-11:30 Coffee break
11:30-12:00 Jakub Gajarsky, Petr Hlineny, Jan Obdrzalek, Sebastian Ordyniak, Felix Reidl, Peter Rossmanith, Fernando Sanchez Villaamil, Somnath Sikdar, Kernelization Using Structural Parameters on Sparse Graph Classes
12:00-12:30 Robert Ganian, Friedrich Slivovsky, Stefan Szeider, Meta-Kernelization with Structural Parameters
12:30-13:30 Lunch
13:30-15:00 Stefan Kratsch, Saket Saurabh, Magnus Wahlström, Matroid theory and kernelization, part 1.
15:00-15:30 Coffee break
15:30-17:00 Stefan Kratsch, Saket Saurabh, Magnus Wahlström, Matroid theory and kernelization, part 2.
17:00-18:00 Open problem session
Thursday, 11th April
9:30-11:00 Stefan Kratsch, Saket Saurabh, Magnus Wahlström, Matroid theory and kernelization, part 3.
11:00-11:30 Coffee break
11:30-12:30 Seth Pettie, Everything you ever wanted to know about graph spanners1
1 but were afraid to ask
12:30-13:30 Lunch
13:30-15:00 Andrew Drucker, Kernel-size lower bounds: the evidence from complexity theory, part 1.
15:00-15:30 Coffee break
15:30-17:00 Andrew Drucker, Kernel-size lower bounds: the evidence from complexity theory, part 2.
17:00-17:30 Magnus Wahlström, Abusing the Tutte Matrix: An Algebraic Instance Compression for the K-set-cycle Problem
17:30-18:00 Riko Jacob, Tobias Liebery, Matthias Mnich, Input-Output Efficient Kernelization
19:00-23:00 Workshop dinner
Friday, 12th April
9:30-11:00 Andrew Drucker, Kernel-size lower bounds: the evidence from complexity theory, part 3.
11:00-11:30 Coffee break
11:30-12:20 Mark Jones, Gabriele Muciaccia, Polynomial Kernels for lambda-extendible Properties Parameterized Above the Poljak-Turzik Bound
12:20-13:20 Lunch

Abstracts

For abstracts of contributed talks, see here.

Piotr Sankowski, Monge Property, Dense Distance Graphs and Speeding-up Max-Flow Computations in Planar Graphs

For slides, please see this blog entry.

In my talk, I will introduce the core technique that was used in a series of recent papers to speed-up max-flow computations in planar graphs. Min-cuts in planar graphs are related to shortest paths via duality. This allows to use simpler shortest path computations for finding minimum-cuts. Especially, it is possible to use a faster implementation of Dijkstra algorithm created by Fakcharoenphol and Rao in 2001. This implementation uses the fact that one do not need to search through shortest paths starting in the same source that would cross. In the algorithm one creates so called dense distance graphs, and needs to search only through square root of edges in such graphs. I will introduce the ideas behind the following three applications of this technique:

  • computing all pairs min-cuts in undirected planar graphs in almost linear time by Borradaile, S. and Wulff-Nilsen '10,
  • computing s-t max-flows in undirected planar graphs in O(n log log n) time by Italiano, Nussbaum, S. and Wulff-Nilsen '11,
  • computing single source-all sinks max flows in directed planar graphs by Łącki, Nussbaum, S. and Wulff-Nilsen '12.
Seth Pettie, Everything you ever wanted to know about graph spanners1
1 but were afraid to ask

Slides.

A spanner is a graph that approximates distances in an underlying graph metric up to some stretch (or distortion.) They have been applied to numerous problems in distributed computing and to various approximate shortest path problems. Tree spanners (whose stretch is measured on the average) are used in some near-linear time SDD (symmetric diagonally dominant) linear system solvers.

Despite some intense scrutiny over the last 25 years, the optimal tradeoffs between a spanner's size (number of edges) and its stretch function are still unknown, as is the relationship between size, stretch, and algorithmic efficiency. In this talk I'll survey the classic graph spanner results of the 1980s and 90s, advancements of the last decade, then take a leisurely tour of the main open problems in this area.

Stefan Kratsch, Saket Saurabh, Magnus Wahlström, Matroid theory and kernelization

Slides: Saket's part, Stefan's part, Magnus' part.

In the last two years, a surprising connection has been realized between polynomial kernelization and matroid theory, and the resulting application of powerful tools from matroid theory has allowed the positive resolution of several long-standing open questions, in particular in the area of graph separation problems.

The first of these results was the discovery of a polynomial compression for the Odd Cycle Transversal problem (Kratsch and Wahlström, SODA 2012). This result was essentially a compression; tools of matroid theory were used to show how to create a matrix, which in a certain sense encoded the essential properties of the original graph, while admitting a total coding size polynomial in the parameter. Subsequent developments (FOCS 2012) used deeper results from matroid theory (specifically, a lemma due to Lovász and Marx on so-called representative sets) to derive direct, reduction rule-based kernels, widening the applicability of the tools and allowing for several further results.

In this tutorial, we will give a careful presentation of these tools and applications. We begin from the basics of matroid theory, and proceed through both the compression- and kernelization-type applications. We will assume no background in matroid theory, and only basic knowledge of linear algebra (e.g., linear independence and finite fields).

Andrew Drucker, Kernel-size lower bounds: the evidence from complexity theory

Slides: part 1, part 2, part 3. Exercises.

Kernelization has been a very successful method for developing FPT algorithms, yet some problems in FPT seem not to admit small kernels. Why not? To address this question, Bodlaender et al. (JCSS 2009) initiated a long line of work building a web of reductions between various kernelization tasks. They showed that kernel-size lower bounds for two particular FPT problems (the "OR-SAT" and "AND-SAT" problems) imply lower bounds for many other problems.

Motivated by this work, researchers have obtained strong evidence from computational complexity that the OR-SAT and AND-SAT problems do not have polynomial kernels. Tight kernel-size lower bounds have even been obtained for certain problems that do admit polynomial kernels. In this tutorial I will describe how these works link kernel-size lower bounds to core conjectures in complexity theory.

I will assume only basic knowledge of FPT and kernelization concepts, and some familiarity with the complexity classes P, NP, and co-NP. I will introduce concepts from the theory of interactive proofs, along with useful tools from probability and game theory. Written exercises will also be provided to reinforce the material.

References:

  • H. Bodlaender, R. Downey, M. Fellows, and D. Hermelin: On problems without polynomial kernels. JCSS 2009.
  • L. Fortnow and R. Santhanam: Infeasibility of instance compression and succinct PCPs for NP. JCSS 2011.
  • H. Dell and D. van Melkebeek: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. STOC 2010.
  • A. Drucker: New limits to classical and quantum instance compression. FOCS 2012.