Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:




Library Locked Library locked




Author, Editor(s)

Author(s):

Philip, Geevarghese
Raman, Venkatesh
Sikdar, Somnath

dblp
dblp
dblp

Not MPG Author(s):

Raman, Venkatesh
Sikdar, Somnath

BibTeX cite key*:

PhilipRamanSikdar2012

Title

Title*:

Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond

Journal

Journal Title*:

ACM Transactions on Algorithms

Journal's URL:

http://talg.acm.org/

Download URL
for the article:


Language:

English

Publisher

Publisher's
Name:

Association for Computing Machinery

Publisher's URL:

http://www.acm.org

Publisher's
Address:

New York, NY

ISSN:

1549-6325

Vol, No, pp, Date

Volume*:

9

Number:

1

Publishing Date:

December 2012

Pages*:

23

Number of
VG Pages:

23

Page Start:

11:1

Page End:

11:23

Sequence Number:

11

DOI:

10.1145/2390176.2390187

Note, Abstract, ©

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

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:

@ARTICLE{PhilipRamanSikdar2012,
AUTHOR = {Philip, Geevarghese and Raman, Venkatesh and Sikdar, Somnath},
TITLE = {Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond},
JOURNAL = {ACM Transactions on Algorithms},
PUBLISHER = {Association for Computing Machinery},
YEAR = {2012},
NUMBER = {1},
VOLUME = {9},
PAGES = {23},
ADDRESS = {New York, NY},
MONTH = {December},
ISBN = {1549-6325},
DOI = {10.1145/2390176.2390187},
}


Entry last modified by Anja Becker, 07/08/2014
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]
Created
03/06/2013 01:08:58 PM
Revisions
4.
3.
2.
1.
0.
Editor(s)
Anja Becker
Anja Becker
Geevarghese Philip
Geevarghese Philip
Geevarghese Philip
Edit Dates
13.03.2013 13:04:53
08.03.2013 14:59:39
03/06/2013 01:11:28 PM
03/06/2013 01:09:20 PM
03/06/2013 01:08:58 PM