Note: |
|
(LaTeX) Abstract: |
We show that for every fixed $j\ge i\ge 1$, the $k$-Dominating Set problem
restricted to graphs that do not have $K_{i,j}$ (the complete
bipartite graph on $(i+j)$ vertices, where the two parts have $i$
and $j$ vertices, respectively) as a subgraph is
fixed parameter tractable (FPT) and has a polynomial kernel. We
describe a polynomial-time algorithm that, given a
$K_{i,j}$-free graph $G$ and a nonnegative integer $k$,
constructs a graph $H$ (the ``kernel'') and an integer $k'$ such
that
\begin{enumerate}
\item $G$ has a dominating set of size at most $k$ if and only
if $H$ has a dominating set of size at most $k'$,
\item $H$ has $O((j+1)^{i+1}k^{i^{2}})$ vertices, and
\item $k'=O((j+1)^{i+1}k^{i^{2}})$.
\end{enumerate}
Since $d$-degenerate graphs do not have $K_{d+1,d+1}$ as a
subgraph, this immediately yields a polynomial kernel on
$O((d+2)^{d+2}k^{(d+1)^{2}})$ vertices for the $k$-Dominating Set
problem on $d$-degenerate graphs, solving an open problem posed
by Alon and Gutner.
The most general class of graphs for which a polynomial kernel
was previously known for $k$-Dominating Set is the class of
$K_{h}$-topological-minor-free graphs. Graphs
of bounded degeneracy are the most general class of graphs for
which an FPT algorithm was previously known for this problem.
$K_{h}$-topological-minor-free graphs are $K_{i,j}$-free for
suitable values of \(i,j\) (but not vice versa), and so our
results show that $k$-Dominating Set has both FPT algorithms and
polynomial kernels in strictly more general classes of graphs.
Using the same techniques, we also obtain an
$O\left(jk^{i}\right)$ vertex-kernel for the $k$-Independent Dominating Set problem on
$K_{i,j}$-free graphs. |
URL for the Abstract: |
http://dl.acm.org/citation.cfm?doid=2390176.2390187 |
Categories,
Keywords: |
Degenerate graphs, dominating set, fixed parameter tractability, kernelization |
HyperLinks / References / URLs: |
|
Copyright Message: |
|
Personal Comments: |
|
Download
Access Level: |
Intranet |
|