Here are the abstracts of the contributed talks (in alphabetical order of the speaker’s last name):
A Turing Kernelization Dichotomy for Structural Parameterizations of F-Minor-Free Deletion
Huib Donkers
For a fixed finite family of graphs F, the F-Minor-Free Deletion problem takes as input a graph G and an integer k and asks whether there exists a set X ⊆ V(G) of size at most k such that G-X is F-minor-free. For F={K_2} and F={K_3} this encodes Vertex Cover and Feedback Vertex Set respectively. When parameterized by the feedback vertex number of G these two problems are known to admit a polynomial kernelization. Such a polynomial kernelization also exists for any F containing a planar graph but no forests. In this paper we show that F-Minor-Free Deletion parameterized by the feedback vertex number is MK[2]-hard for F = {P_3}. This rules out the existence of a polynomial kernel assuming NP ⊈ coNP/poly, and also gives evidence that the problem does not admit a polynomial Turing kernel. Our hardness result generalizes to any F not containing a P_3-subgraph-free graph, using as parameter the vertex-deletion distance to treewidth mintw(F), where mintw(F) denotes the minimum treewidth of the graphs in F. For the other case, where F contains a P_3-subgraph-free graph, we present a polynomial Turing kernelization. Our results extend to F-Subgraph-Free Deletion.
Approximate Kernelization Schemes for Steiner Networks
Andreas Feldmann
Borchers and Du proved that there always exists a near-optimal Steiner tree for which every full component is allowed to contain only a fixed number of terminals. It was recently shown by Lokshtanov et al. that this theorem can be reinterpreted in terms of approximate kernels for the Steiner Tree problem parameterized by the number of terminals. In this talk I will present some extensions of this result to other parameterizations, such as the number of Steiner vertices in the optimum, and more general problems, such as Steiner Forest and Directed Steiner Network. For the directed setting we prove a generalisation of Borchers and Du’s theorem. This is joint work with Rajesh Chitnis, Pavel Dvořák, Dušan Knop, Pasin Manurangsi, Tomáš Masařík, Tomáš Toufar, and Pavel Veselý.
Matrix Clustering and Completion: Fixed-Parameter Tractability via Kernelization
Robert Ganian
We consider the parameterized complexity of fundamental matrix completion problems, in which we are given a matrix with missing entries and the task is to complete the matrix in a way that ensures that the rows are distributed into a small number of clusters. After summarizing some recent parameterized results on the matrix completion problem, we use kernelization to establish the fixed-parameter tractability of completing a matrix to achieve a good clustering. The talk is based on recent work with Eduard Eiben, Iyad Kanj, Sebastian Ordyniak and Stefan Szeider.
Polynomial kernels for cycle transversal in bounded independence digraphs
William Lochet
We present a kernel for directed feedback arc set in digraphs with bounded independence number. The main ingredient of our proof is a result on fault tolerant subgraphs for this class of digraphs. In fact, this result allows us to prove the existence of a polynomial kernel for odd cycle transversal and more generally for cycle of length 1 mod p, for any fixed integer p, in this class.
Joint work with D. Lokshtanov, P. Misra, S. Saurabh, R. Sharma and M. Zehavi.
Parameterized Complexity of Conflict-free Graph Coloring
Astrid Pieterse
In this talk we will look at the q-closed neighborhood conflict-free coloring problem (q-CNCF-coloring) and the q-open neighborhood conflict-free coloring problem (q-ONCF-coloring). The problem asks, given a graph G, whether we can color the vertices of G with at most q colors, such that for every vertex v in the graph, the closed (respectively, open) neighborhood of v contains a vertex whose color is unique among the colors used to color N[v] (respectively, N(v)). In our setting, every vertex of G must receive a color by this coloring.
First of all, we study the kernelizability of the problem when parameterized by the size of a vertex cover in the graph. We will see a polynomial kernel for 2-CNCF-coloring and observe that q-CNCF-coloring for q >= 3 and q-ONCF-coloring for q >= 2 are unlikely to admit polynomial kernels.
When time permits, we will discuss some combinatorial results on the number of colors needed to conflict-free color graphs of bounded treewidth, vertex cover size, or feedback vertex set size.
This talk is based on joint work with Hans Bodlaender and Sudeshna Kolay.