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 polynomialtime 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}$topologicalminorfree 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}$topologicalminorfree 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)$ vertexkernel 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, ﬁxed parameter tractability, kernelization 
HyperLinks / References / URLs: 

Copyright Message: 

Personal Comments: 

Download
Access Level: 
Intranet 
