---

In an informal blackboard-talk I will describe some results of a recent paper at ICALP, where we studied whether efficient preprocessing schemes for the Treewidth problem can give provable bounds on the size of the processed instances using the framework of kernelization. Assuming the AND-distillation conjecture to hold, the standard parameterization of Treewidth does not have a kernel of polynomial size and thus instances (G, k) of the decision problem of Treewidth cannot be efficiently reduced to equivalent instances of size polynomial in k. We therefore consider different (structural) parameterizations of the Treewidth problem. We show that Treewidth has a kernel with O(l^3) vertices, with l the size of a vertex cover, and a kernel with O(l^4) vertices, with l the size of a feedback vertex set. I will try to share some insights into how the reduction rules were found, and their relationship to experimental work on preprocessing heuristics for treewidth. We also obtained various kernel lower-bounds. Treewidth parameterized by the vertex-deletion distance to a co-cluster graph and Weighted Treewidth parameterized by the size of a vertex cover do not have polynomial kernels unless NP \subseteq coNP/poly. Treewidth parameterized by the deletion distance to a cluster graph has no polynomial kernel unless the AND-distillation conjecture does not hold. If time permits I will show which properties of treewidth were exploited in the reductions that yield these lower-bounds.

---

There are various reasons to study the kernelization complexity of non-standard parameterizations. Problems such as Chromatic Number are NP-complete for a constant value of the natural parameter, hence we should not hope to obtain kernels for this parameter. For other problems such as Long Path, the natural parameterization is fixed-parameter tractable but is known not to admit a polynomial kernel unless the polynomial hierarchy collapses. We may therefore guide the search for meaningful preprocessing rules for these problems by studying the existence of polynomial kernels for different parameterizations.

Another motivation is formed by the Vertex Cover problem. Its natural parameterization admits a small kernel, but there exist refined parameters (such as the feedback vertex number) which are structually smaller than the natural parameter, for which polynomial kernels still exist; hence we may obtain better preprocessing studying the properties of such refined parameters.

In this survey talk we discuss recent results on the kernelization complexity of structural parameterizations of these important graph problems. We consider a hierarchy of structural graph parameters, and try to pinpoint the best parameters for which polynomial kernels still exist.

---

This paper studies the kernelization complexity of graph coloring problems, with respect to certain structural parameterizations of the input instances. We are interested in how well polynomial-time data reduction can provably shrink instances of coloring problems, in terms of the chosen parameter. It is well known that deciding 3-colorability is already NP-complete, hence parameterizing by the requested number of colors is not fruitful. Instead, we pick up on a research thread initiated by Cai (DAM, 2003) who studied coloring problems parameterized by the modification distance of the input graph to a graph class on which coloring is polynomial-time solvable; for example parameterizing by the number k of vertex-deletions needed to make the graph chordal. We obtain various upper and lower bounds for kernels of such parameterizations of q-Coloring, complementing Cai's study of the time complexity with respect to these parameters.

---

Kernelization is a concept that enables the formal mathematical analysis of data reduction through the framework of parameterized complexity. The parameterized Vertex Cover problem, which asks whether a given undirected graph G has a vertex subset S of size k such that G - S is edgeless, has been a testbed for various kernelization techniques. One of the major results in this direction is that it is possible to preprocess an instance (G,k) of Vertex Cover in polynomial time to obtain an equivalent instance (G',k') such that |V(G')| <= 2k' and k' <= k. This means that we can effectively reduce the size of the graphs that we have to consider for Vertex Cover, to a size which only depends on the size of the set we are looking for. In this work we consider whether we can bound the size of instances of Vertex Cover in a measure which is smaller than the size k of the desired vertex cover. A feedback vertex of a graph G is a set S such that G - S is a forest. Since any edgeless graph is a forest, the size of a minimum-size feedback vertex set (FVS) is at most the size of a vertex cover. Hence the parameter "size of a minimum FVS" is structurally smaller than the parameter "size of a minimum Vertex Cover". We prove that an instance of the decision problem "does graph G have a vertex cover of size k" can be preprocessed in polynomial time to obtain an equivalent instance where the number of vertices in the resulting instance is bounded by a polynomial in the minimum size of a FVS of G. In sharp contrast, we give complexity-theoretic evidence that no such data reduction is possible in the variant where the vertices of the graph G are weighted and we are looking for a minimum-weight vertex cover.

---

This presentation focuses on super-polynomial lower bounds on kernel sizes. The first half of the talk treats the existing techniques for proving such lower bounds. We start by considering OR-compositions, which allow us to prove that k-Path does not admit a polynomial kernel unless the polynomial hierarchy collapses. We then show that the framework can be extended by using polynomial-parameter transformations, which leads to a kernel lower bound for Disjoint Cycles by using the intermediate problem Disjoint Factors. Without going into details we discuss several other applications of this framework to obtain lower bounds for Connected Vertex Cover, Small Universe Set Cover and Small Universe Hitting Set. In the second half of the talk we introduce the new technique of cross-composition. We discuss how cross-composition generalizes and extends the two existing techniques, and give an application of cross-composition by proving that the Clique problem parameterized by size of a vertex cover of the graph does not admit a polynomial kernel (unless ..).

---

Kernelization is a concept that enables the formal mathematical analysis of data reduction through the framework of parameterized complexity. The parameterized Vertex Cover problem, which asks whether a given undirected graph G has a vertex subset S of size k such that G - S is edgeless, has been a testbed for various kernelization techniques. One of the major results in this direction is that it is possible to preprocess an instance (G,k) of Vertex Cover in polynomial time to obtain an equivalent instance (G',k') such that |V(G')| <= 2k' and k' <= k. This means that we can effectively reduce the size of the graphs that we have to consider for Vertex Cover, to a size which only depends on the size of the set we are looking for. In this work we consider whether we can bound the size of instances of Vertex Cover in a measure which is smaller than the size k of the desired vertex cover. A feedback vertex of a graph G is a set S such that G - S is a forest. Since any edgeless graph is a forest, the size of a minimum-size feedback vertex set (FVS) is at most the size of a vertex cover. Hence the parameter "size of a minimum FVS" is structurally smaller than the parameter "size of a minimum Vertex Cover". We prove that an instance of the decision problem "does graph G have a vertex cover of size k" can be preprocessed in polynomial time to obtain an equivalent instance where the number of vertices in the resulting instance is bounded by a polynomial in the minimum size of a FVS of G. In sharp contrast, we give complexity-theoretic evidence that no such data reduction is possible in the variant where the vertices of the graph G are weighted and we are looking for a minimum-weight vertex cover.

---

Kernelization is a powerful tool to obtain fixed-parameter tractable algorithms. Recent breakthroughs show that many graph problems admit small polynomial kernels when restricted to sparse graph classes such as planar graphs, bounded-genus graphs or H-minor-free graphs. We consider the intersection graphs of (unit) disks in the plane, which can be arbitrarily dense but do exhibit some geometric structure. We give the first kernelization results on these dense graph classes. Connected Vertex Cover has a kernel with 12k vertices on unit-disk graphs and with 3k2+6k vertices on disk graphs with arbitrary radii. Red-Blue Dominating Set parameterized by the size of the smallest color class has a linear-vertex kernel on planar graphs, a quadratic-vertex kernel on unit-disk graphs and a quartic-vertex kernel on disk graphs. Finally we prove that H-matching on unit-disk graphs has a linear-vertex kernel for every fixed graph H.

---

Kernelization is a powerful tool to obtain fixed-parameter tractable algorithms. Recent breakthroughs show that many graph problems admit small polynomial kernels when restricted to sparse graph classes such as planar graphs, bounded-genus graphs or H-minor-free graphs. We consider the intersection graphs of (unit) disks in the plane, which can be arbitrarily dense but do exhibit some geometric structure. We give the first kernelization results on these dense graph classes. Connected Vertex Cover has a kernel with 12k vertices on unit-disk graphs and with 3k2+6k vertices on disk graphs with arbitrary radii. Red-Blue Dominating Set parameterized by the size of the smallest color class has a linear-vertex kernel on planar graphs, a quadratic-vertex kernel on unit-disk graphs and a quartic-vertex kernel on disk graphs. Finally we prove that H-matching on unit-disk graphs has a linear-vertex kernel for every fixed graph H.

---

In this paper we consider the fixed parameter complexity of the Weighted Max Leaf problem, where we get as input an undirected connected graph G = (V,E) with a weight function w: V -> N on the vertices and are asked whether a spanning tree for G exists such that the combined weight of the leaves of the tree is at least k. The fixed parameter complexity of this problem strongly depends on the weight range that is allowed. If we allow vertices to have a weight of zero (the range of the weight function is the non-negative integers) then this problem is hard for W[1] on general graphs. When we restrict the problem to specific graph classes, we can obtain linear size problem kernels for these non-negative weights. We show the existence of a kernel with 78k vertices on planar graphs, O(sqrt(g)k + g) vertices on graphs of oriented genus at most g, and with (1 + 4d)(1 + d/2)k vertices on graphs in which the degree of positive-weight vertices is bounded by d. If we require all vertex weights to be strictly positive integers, we can prove the existence of a problem kernel with 7.5k vertices on general graphs. For the correctness proofs of the problem kernels we develop some extremal graph theory about spanning trees with many leaves in bipartite graphs, and in graphs that do not have long paths of degree-2 vertices.

---

The Maximum Leaf Spanning Tree asks for a connected graph G and integer k whether there exists a spanning tree for G with at least k leaves. Recall that a leaf in a tree is a vertex with degree 1. The subject of this talk is the generalization of this problem into the Maximum Leaf Weight Spanning Tree (MLWST) problem, in which we give each vertex a non-negative integer weight and ask if the graph has a spanning tree such that the combined weight of all the leaves is at least k. We consider the fixed parameter (in)tractability of this problem. We show that MLWST is hard for W[1] on general graphs. The problem is Fixed Parameter Tractable (FPT) when restricted to graphs of bounded genus, which will be shown by presenting a linear sized problem kernel for these classes of graphs. This means that for those classes of graphs we can always apply polynomial time data reduction to simplify the problem instance to an equivalent instance whose size does not depend on |G|, but only on k.