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 Goto entry point

 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: (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, ﬁxed 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},