Linear kernels for connected dominating set on graphs with excluded topological subgraphsReportar como inadecuado



 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/







Documentos relacionados