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

Linear kernels for connected dominating set on graphs with excluded topological subgraphs - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Descargar gratis o leer online en formato PDF el libro: 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.

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

Fuente: https://archive.org/