# Linear kernels for connected dominating set on graphs with excluded topological subgraphs

Linear kernels for connected dominating set on graphs with excluded topological subgraphs - Download this document for free, or read online. Document in PDF available to download.

Download or read this book online for free in PDF: **
Linear kernels for connected dominating set on graphs with excluded topological subgraphs**

We give the first linear kernels for {\sc Dominating Set} and {\sc Connected Dominating Set} problems on graphs excluding a fixed graph $H$ as a topological minor. In other words, we give polynomial time algorithms that, for a given $H$-topological-minor free graph $G$ and a positive integer $k$, output an $H$-topological-minor free graph $G$ on $\cOk$ vertices such that $G$ has a connected dominating set of size $k$ if and only if $G$ has. Our results extend the known classes of graphs on which {\sc Dominating Set} and {\sc Connected Dominating Set} problems admit linear kernels. The kernelization algorithm is based on a non-trivial combination of the following ingredients \bullet The structural theorem of Grohe and Marx STOC 2012 for graphs excluding a fixed graph $H$ as a topological subgraph; \bullet A novel notion of protrusions, different that the one defined in FOCS 2009; \bullet Reinterpretations of reduction techniques developed for kernelization algorithms for {\sc Dominating Set} and {\sc Connected Dominating Set} from SODA 2012. A protrusion is a subgraph of constant treewidth separated from the remaining vertices by a constant number of vertices. Roughly speaking, in the new notion of protrusion instead of demanding the subgraph of being of constant treewidth, we ask it to contain a {\sl constant} number of vertices from a solution. We believe that the new notion of protrusion will be useful in many other algorithmic settings.

Author: **Fedor V. Fomin; Daniel Lokshtanov; Saket Saurabh; Dimitrios M. Thilikos**

Source: https://archive.org/