You can now download the complete Worker 2015 Proceedings (PDF).
- Serge Gaspers
- Kernelization in constraint satisfaction and reasoning. PDF
We present a study of kernelization algorithms for important combinatorial problems from various areas in AI. We consider problems from Constraint Satisfaction, Global Constraints, Satisfiability, Nonmonotonic and Bayesian Reasoning under structural restrictions. All these problems involve two tasks: (i) identifying the structure in the input as required by the restriction, and (ii) using the identified structure to solve the reasoning task efficiently. We show that for most of the considered problems, task (i) admits a polynomial-time preprocessing to a problem kernel whose size is polynomial in a structural problem parameter of the input, in contrast to task (ii) which does not admit such a reduction to a problem kernel of polynomial size, subject to a complexity theoretic assumption. As a notable exception we show that the consistency problem for the ATMOST-NVALUE constraint admits a polynomial kernel consisting of a quadratic number of variables and domain values. Our results provide a firm worst-case guarantees and theoretical boundaries for the performance of polynomial-time preprocessing algorithms for the considered problems.
- The talk is based on joint work with Stefan Szeider.
- Robert Krauthgamer
- Vertex Sparsification of Cuts, Flows, and Distances. PDF
A key challenge in designing graph algorithms is to “compress” a graph G so as to preserve some of its basic properties, such as distances and cuts. Both spanners [Peleg and Schaffer, 1989] and cut sparsifiers [Benczur and Karger, 1996] fall into this category, as they reduce the number of edges in G without changing any distance or cut by more than a small factor.
- I will discuss another flavor of this challenge, which asks instead to reduce the number of vertices. Specifically, given a graph G and k terminal vertices, we wish to construct a small graph G’ that contains the terminals, such that all cuts/flows/distances between the terminals are equal in G and in G’. Can we bound the size of G’ by a function of k? And what if G’ only needs to approximate G (say within 1+ε)?
- I plan to survey recent progress in this emerging area.
- Dániel Marx
- Characterizing the Easy-to-Find Subgraphs from the Viewpoint of Polynomial-Time Algorithms, Kernels, and Turing Kernels. PDF
We study two fundamental problems related to finding subgraphs: given graphs G and H, test whether H is isomorphic to a subgraph of G, or determine the maximum number of vertex-disjoint H-subgraphs that can be packed in G. We investigate these problems when the graph H belongs to a fixed hereditary family F. Our goal is to study which classes F make the two problems tractable in one of the following senses: (a) (randomized) polynomial-time solvable, (b) admits a polynomial (many-one) kernel, or (c) admits a polynomial Turing kernel.
- Ankur Moitra
- Vertex Sparsification: An Introduction, Connections and Applications. PDF
The notion of exactly (or approximately) representing certain combinatorial properties of a graph G on a simpler graph is ubiquitous in combinatorial optimization. In this talk, I will introduce the notion of vertex sparsification. Here we are given a graph G = (V, E) and a set of terminals K and our goal is to find one single graph H = (K, EH) on just the terminal set so that H approximately preserves minimum cuts between every bipartition of the terminals, as well as minimum congestion routings of every multi-commodity flow problem.
- I will prove that good vertex sparsifiers exist and in fact the approximation factor is independent of the size of the original graph (and is sub-logarithmic in the number of terminals). Moreover the approximation factor can be improved to a constant for any graph that excludes a fixed minor. I will give applications to approximation algorithms, including a master theorem for flow-cut gaps. Lastly, I will give lower bounds for vertex sparsification and open questions. This talk will be based on a number of connections to metric embeddings.
- Marcin Pilipczuk
- Sparsification for network design problems in planar graphs. PDF
A well-established technique for designing polynomial-time approximation schemes (PTASes) for connectivity or network design problems on planar graphs is to first establish a spanner – a subgraph or minor of the input graph that contains a near-optimal solution, while at the same time has total cost bounded by f(ε) ⋅ optimum cost (where ε is the accuracy parameter) – and then use a variant of the Baker’s shifting technique to solve the problem on the spanner only. This approach turned out to be very fruitful, yielding PTASes on planar graph for such problems as Subset TSP, Steiner Tree, Steiner Forest. Moreover, recently, due to connections between cut problems in the primal graph and network design problems in the dual graph, we have seen a PTAS for Multiway Cut and a bicriteria PTAS for Bisection.In our recent work with Michał Pilipczuk, Piotr Sankowski, and Erik Jan van Leeuwen, we used the insight from the aforementioned approximation schemes to design improved exact algorithms for (unweighted) Steiner Tree in planar graphs: a subexponential algorithm and a polynomial kernel for the parameterization by the number of edges in the solution tree. Some results generalize to bounded-genus graphs, and also to the Steiner Forest and Multiway Cut problems.In the talk I will give an overview of both the spanner framework for designing PTASes on planar graphs and of recent results in parameterized world, focusing on the Steiner Tree problem.
- Michał Pilipczuk
- Kernelization of Dominating Set on sparse graph classes. PDF
During the talk we shall present a new approach to kernelization of Dominating Set (DS) on sparse graph classes, which enables us to show a linear kernel for the problem on every monotone graph class of bounded expansion, and an almost linear kernel for every monotone nowhere dense graph class. Since the class of H-topological-minor-free graphs has bounded expansion for every fixed H, these findings generalize all the previous results on linear kernelization for DS on sparse graph classes. However, the improvement is not only in the generality but also in the simplicity: the new approach is conceptually much easier and relies only on basic properties of graph classes of bounded expansion, and not on deep decomposition theorems, as was the case for H-(topological)-minor-free.
- The talk will be based on a joint work with Pål Grønås Drange, Markus S. Dregi, Fedor V. Fomin, Stephan Kreutzer, Daniel Lokshtanov, Marcin Pilipczuk, Felix Reidl, Fernando Sánchez Villaamil, Saket Saurabh, and Somnath Sikdar.