Abstract
Kernelization is a strong and widely-applied technique in parameterized complexity. In a nutshell, a kernelization algorithm for a parameterized problem transforms 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.
We consider kernelization for problems on d-degenerate graphs, i.e. 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, e.g. planar graphs, H-minor free graphs, 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 NP ⊆ coNP/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)^2})\).
-
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).
We also give simple kernels for Connected Vertex Cover and Capacitated Vertex Cover of size O(k d) and O(k d + 1) respectively. Both these problems do not have kernels of size O(k d − 1 − ε) unless coNP/poly.
In this extended abstract we will focus on the lower bound for Dominating Set, which we feel is the central result of our study. The proofs of the other results can be found in the full version of the paper.
Partially supported by ERC Starting Grant NEWNET 279352.
A full version of the paper can be found in [8].
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alber, J., Fellows, M.R., Niedermeier, R.: Polynomial-time data reduction for dominating set. Journal of the ACM 51(3), 363–384 (2004)
Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. Journal of Computer and System Sciences 75(8), 423–434 (2009)
Bodlaender, H.L., Fomin, F.V., Lokshtanov, D., Penninkx, E., Saurabh, S., Thilikos, D.M. (Meta) kernelization. In: FOCS, pp. 629–638 (2009)
Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Cross-composition: A new technique for kernelization lower bounds. In: STACS, pp. 165–176 (2011)
Bodlaender, H.L., Thomassé, S., Yeo, A.: Kernel bounds for disjoint cycles and disjoint paths. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol. 5757, pp. 635–646. Springer, Heidelberg (2009)
Cai, L., Chen, J., Downey, R.G., Fellows, M.R.: Advice classes of paramterized tractability. Annals of Pure and Applied Logic 84(1), 119–138 (1997)
Chen, Y., Flum, J., Müller, M.: Lower bounds for kernelizations and other preprocessing procedures. Theory of Computing Systems 48(4), 803–839 (2011)
Cygan, M., Grandoni, F., Hermelin, D.: Tight kernel bounds for problems on graphs with small degeneracy. CoRR, abs/1305.4914 (2013)
Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: Kernelization hardness of connectivity problems in d-degenerate graphs. Discrete Applied Mathematics 160(15), 2131–2141 (2012)
Dell, H., Marx, D.: Kernelization of packing problems. In: SODA, pp. 68–81 (2012)
Dell, H., van Melkebeek, D.: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. In: STOC, pp. 251–260 (2010)
Diestel, R.: Graph Theory, 3rd edn. Springer-Verlag (2005)
Dom, M., Lokshtanov, D., Saurabh, S.: Incompressibility through colors and IDs. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol. 5555, pp. 378–389. Springer, Heidelberg (2009)
Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer-Verlag (1999)
Erman, R., Kowalik, L., Krnc, M., Walen, T.: Improved induced matchings in sparse graphs. Discrete Applied Mathematics 158(18), 1994–2003 (2010)
Fellows, M.R.: The lost continent of polynomial time: Preprocessing and kernelization. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol. 4169, pp. 276–277. Springer, Heidelberg (2006)
Fomin, F.V., Lokshtanov, D., Saurabh, S., Thilikos, D.M.: Bidimensionality and kernels. In: SODA, pp. 503–510 (2010)
Fortnow, L., Santhanam, R.: Infeasibility of instance compression and succinct PCPs for NP. In: STOC, pp. 133–142 (2008)
Guo, J., Niedermeier, R.: Invitation to data reduction and problem kernelization. SIGACT News 38(1), 31–45 (2007)
Guo, J., Niedermeier, R.: Linear problem kernels for NP-hard problems on planar graphs. In: Arge, L., Cachin, C., Jurdziński, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 375–386. Springer, Heidelberg (2007)
Harnik, D., Naor, M.: On the compressibility of NP instances and cryptographic applications. SIAM Journal on Computing 39(5), 1667–1713 (2010)
Hermelin, D., Wu, X.: Weak compositions and their applications to polynomial lower-bounds for kernelization. In: SODA, pp. 104–113 (2012)
Kanj, I.A., Pelsmajer, M.J., Schaefer, M., Xia, G.: On the induced matching problem. Journal of Computer and System Sciences 77(6), 1058–1070 (2011)
Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85–103. Plenum Press (1972)
Kim, E.J., Langer, A., Paul, C., Reidl, F., Rossmanith, P., Sau, I., Sikdar, S.: Linear kernels and single-exponential algorithms via protrusion decompositions. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part I. LNCS, vol. 7965, pp. 613–624. Springer, Heidelberg (2013)
Kratsch, S.: Co-nondeterminism in compositions: a kernelization lower bound for a Ramsey-type problem. In: SODA, pp. 114–122 (2012)
Nemhauser, G.L., Trotter Jr., L.E.: Vertex packings: Structural properties and algorithms. Mathematical Programming 8(2), 232–248 (1975)
Philip, G., Raman, V., Sikdar, S.: Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond. ACM Transactions on Algorithms 9(1), 11 (2012)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cygan, M., Grandoni, F., Hermelin, D. (2013). Tight Kernel Bounds for Problems on Graphs with Small Degeneracy. In: Bodlaender, H.L., Italiano, G.F. (eds) Algorithms – ESA 2013. ESA 2013. Lecture Notes in Computer Science, vol 8125. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40450-4_31
Download citation
DOI: https://doi.org/10.1007/978-3-642-40450-4_31
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40449-8
Online ISBN: 978-3-642-40450-4
eBook Packages: Computer ScienceComputer Science (R0)