research-article

Tight Kernel Bounds for Problems on Graphs with Small Degeneracy

Authors:

Marek Cygan,

Fabrizio Grandoni,

Danny HermelinAuthors Info & Claims

ACM Transactions on Algorithms (TALG), Volume 13, Issue 3

Article No.: 43, Pages 1 - 22

https://doi.org/10.1145/3108239

Published: 09 August 2017 Publication History

Get Access

Abstract

Kernelization is a strong and widely applied technique in parameterized complexity. In a nutshell, a kernelization algorithm for a parameterized problem transforms in polynomial time a given instance of the problem into an equivalent instance whose size depends solely on the parameter. Recent years have seen major advances in the study of both upper and lower bound techniques for kernelization, and by now this area has become one of the major research threads in parameterized complexity.

In this article, we consider kernelization for problems on d-degenerate graphs, that is, graphs such that any subgraph contains a vertex of degree at most d. This graph class generalizes many classes of graphs for which effective kernelization is known to exist, for example, planar graphs, H-minor free graphs, and H-topological-minor free graphs. We show that for several natural problems on d-degenerate graphs the best-known kernelization upper bounds are essentially tight. In particular, using intricate constructions of weak compositions, we prove that unless coNP ⊆ NP/poly:

• Dominating Set has no kernels of size O(k^{(d−1)(d−3)−ε}) for any ε > 0. The current best upper bound is O(k^(d+1)²).

• Independent Dominating Set has no kernels of size O(k^d−4−ε) for any ε > 0. The current best upper bound is O(k^d+1).

• Induced Matching has no kernels of size O(k^d−3−ε) for any ε > 0. The current best upper bound is O(k^d).

To the best of our knowledge, Dominating S^et is the the first problem where a lower bound with superlinear dependence on d (in the exponent) can be proved.

In the last section of the article, we also give simple kernels for Connected Vertex Cover and Capacitated Vertex Cover of size O(k^d) and O(k^d+1), respectively. We show that the latter problem has no kernels of size O(k^d−ε) unless coNP ⊆ NP/poly by a simple reduction from d-Exact Set Cover (the same lower bound for Connected Vertex Cover on d-degenerate graphs is already known).

References

[1]

Jochen Alber, Michael R. Fellows, and Rolf Niedermeier. 2004. Polynomial-time data reduction for dominating set. J. ACM 51, 3 (2004), 363--384.

Abstract

References

Cited By

Index Terms

Recommendations

Kernelization Lower Bounds Through Colors and IDs

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

Kernelization hardness of connectivity problems in d-degenerate graphs

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Funding Sources

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations