Document Open Access Logo

A New Framework for Kernelization Lower Bounds: The Case of Maximum Minimal Vertex Cover

Authors Júlio Araújo , Marin Bougeret , Victor Campos , Ignasi Sau

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2021.4.pdf
  • Filesize: 0.97 MB
  • 19 pages

Document Identifiers

Author Details

Júlio Araújo
  • Departament of Mathematics, Federal University of Ceará, Fortaleza, Brazil
Marin Bougeret
  • LIRMM, Université de Montpellier, France
Victor Campos
  • Departament of Computer Science, Federal University of Ceará, Fortaleza, Brazil
Ignasi Sau
  • LIRMM, Université de Montpellier, CNRS, France

Funding

  • Araújo, Júlio: CNPq-Pq 304478/2018-0, CAPES-PrInt 88887.466468/2019-00 and CAPES-STIC-AmSud 88881.569474/2020-01.
  • Campos, Victor: FUNCAP - PNE-011200061.01.00/16.
  • Sau, Ignasi: DEMOGRAPH (ANR-16-CE40-0028), ESIGMA (ANR-17-CE23-0010), ELIT (ANR-20-CE48-0008-01), and French-German Collaboration ANR/DFG Project UTMA (ANR-20-CE92-0027).

Acknowledgements

We would like to thank Michael Lampis (resp. Magnus Wahlström, Venkatesh Raman) for pointing us to reference [Louis Dublois et al., 2020] (resp. reference [Archontia C. Giannopoulou et al., 2016], references [Arindam Biswas et al., 2020; Stefan Kratsch et al., 2014]).

Cite AsGet BibTex

Júlio Araújo, Marin Bougeret, Victor Campos, and Ignasi Sau. A New Framework for Kernelization Lower Bounds: The Case of Maximum Minimal Vertex Cover. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.IPEC.2021.4

Abstract

In the Maximum Minimal Vertex Cover (MMVC) problem, we are given a graph G and a positive integer k, and the objective is to decide whether G contains a minimal vertex cover of size at least k. Motivated by the kernelization of MMVC with parameter k, our main contribution is to introduce a simple general framework to obtain lower bounds on the degrees of a certain type of polynomial kernels for vertex-optimization problems, which we call {lop-kernels}. Informally, this type of kernels is required to preserve large optimal solutions in the reduced instance, and captures the vast majority of existing kernels in the literature. As a consequence of this framework, we show that the trivial quadratic kernel for MMVC is essentially optimal, answering a question of Boria et al. [Discret. Appl. Math. 2015], and that the known cubic kernel for Maximum Minimal Feedback Vertex Set is also essentially optimal. On the positive side, given the (plausible) non-existence of subquadratic kernels for MMVC on general graphs, we provide subquadratic kernels on H-free graphs for several graphs H, such as the bull, the paw, or the complete graphs, by making use of the Erdős-Hajnal property in order to find an appropriate decomposition. Finally, we prove that MMVC does not admit polynomial kernels parameterized by the size of a minimum vertex cover of the input graph, even on bipartite graphs, unless NP ⊆ coNP / poly. This indicates that parameters smaller than the solution size are unlike to yield polynomial kernels for MMVC.

Subject Classification

ACM Subject Classification
  • Theory of computation → Fixed parameter tractability
Keywords
  • Maximum minimal vertex cover
  • parameterized complexity
  • polynomial kernel
  • kernelization lower bound
  • Erdős-Hajnal property
  • induced subgraphs

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Faisal N. Abu-Khzam, Cristina Bazgan, Morgan Chopin, and Henning Fernau. Approximation algorithms inspired by kernelization methods. In Proc. of the 25th International Symposium on Algorithms and Computation (ISAAC), volume 8889 of LNCS, pages 479-490, 2014. URL: https://doi.org/10.1007/978-3-319-13075-0_38.
  2. Noga Alon, János Pach, and József Solymosi. Ramsey-type theorems with forbidden subgraphs. Combinatorica, 21(2):155-170, 2001. URL: https://doi.org/10.1007/s004930100016.
  3. Júlio Araújo, Marin Bougeret, Victor A. Campos, and Ignasi Sau. A new framework for kernelization lower bounds: the case of Maximum Minimal Vertex Cover. Full version of the current article, 2021. URL: http://arxiv.org/abs/2102.02484.
  4. Júlio Araújo, Marin Bougeret, Victor A. Campos, and Ignasi Sau. Parameterized complexity of computing maximum minimal blocking and hitting sets. Manuscript submitted for publication, 2021. URL: http://arxiv.org/abs/2102.03404.
  5. Cristina Bazgan, Ljiljana Brankovic, Katrin Casel, Henning Fernau, Klaus Jansen, Kim-Manuel Klein, Michael Lampis, Mathieu Liedloff, Jérôme Monnot, and Vangelis Th. Paschos. The many facets of upper domination. Theoretical Computer Science, 717:2-25, 2018. URL: https://doi.org/10.1016/j.tcs.2017.05.042.
  6. Daniel Binkele-Raible, Henning Fernau, Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Yngve Villanger. Kernel(s) for problems with no kernel: On out-trees with many leaves. ACM Transactions on Algorithms, 8(4):38:1-38:19, 2012. URL: https://doi.org/10.1145/2344422.2344428.
  7. Arindam Biswas, Venkatesh Raman, and Saket Saurabh. Approximation in (poly-) logarithmic space. In Proc. of the 45th International Symposium on Mathematical Foundations of Computer Science (MFCS), volume 170 of LIPIcs, pages 16:1-16:15, 2020. URL: https://doi.org/10.4230/LIPIcs.MFCS.2020.16.
  8. Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, and Danny Hermelin. On problems without polynomial kernels. Journal of Computer and System Sciences, 75(8):423-434, 2009. URL: https://doi.org/10.1016/j.jcss.2009.04.001.
  9. Hans L. Bodlaender, Fedor V. Fomin, Daniel Lokshtanov, Eelko Penninkx, Saket Saurabh, and Dimitrios M. Thilikos. (Meta) Kernelization. Journal of the ACM, 63(5):44:1-44:69, 2016. Google Scholar
  10. Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. Kernelization lower bounds by cross-composition. SIAM Journal on Discrete Mathematics, 28(1):277-305, 2014. URL: https://doi.org/10.1137/120880240.
  11. Hans L. Bodlaender, Stéphan Thomassé, and Anders Yeo. Kernel bounds for disjoint cycles and disjoint paths. Theoretical Computer Science, 412(35):4570-4578, 2011. URL: https://doi.org/10.1016/j.tcs.2011.04.039.
  12. Rodica Boliac and Vadim V. Lozin. Independent domination in finitely defined classes of graphs. Theoretical Computer Science, 301(1-3):271-284, 2003. URL: https://doi.org/10.1016/S0304-3975(02)00586-8.
  13. Édouard Bonnet, Michael Lampis, and Vangelis Th. Paschos. Time-approximation trade-offs for inapproximable problems. Journal of Computer and System Sciences, 92:171-180, 2018. URL: https://doi.org/10.1016/j.jcss.2017.09.009.
  14. Édouard Bonnet and Vangelis Th. Paschos. Sparsification and subexponential approximation. Acta Informatica, 55(1):1-15, 2018. URL: https://doi.org/10.1007/s00236-016-0281-2.
  15. Édouard Bonnet, Stéphan Thomassé, Xuan Thang Tran, and Rémi Watrigant. An algorithmic weakening of the Erdős-Hajnal conjecture. In Proc. of the 28th Annual European Symposium on Algorithms (ESA), volume 173 of LIPIcs, pages 23:1-23:18, 2020. URL: https://doi.org/10.4230/LIPIcs.ESA.2020.23.
  16. Nicolas Boria, Federico Della Croce, and Vangelis Th. Paschos. On the max min vertex cover problem. Discrete Applied Mathematics, 196:62-71, 2015. URL: https://doi.org/10.1016/j.dam.2014.06.001.
  17. Katrin Casel, Henning Fernau, Mehdi Khosravian Ghadikolaei, Jérôme Monnot, and Florian Sikora. Extension of Vertex Cover and Independent Set in Some Classes of Graphs. In Proc. of the 11th International Conference on Algorithms and Complexity (CIAC), volume 11485 of LNCS, pages 124-136, 2019. URL: https://doi.org/10.1007/978-3-030-17402-6_11.
  18. Jianer Chen, Henning Fernau, Iyad A. Kanj, and Ge Xia. Parametric duality and kernelization: Lower bounds and upper bounds on kernel size. SIAM Journal on Computing, 37(4):1077-1106, 2007. URL: https://doi.org/10.1137/050646354.
  19. Maria Chudnovsky. The Erdős-Hajnal Conjecture - A Survey. Journal of Graph Theory, 75(2):178-190, 2014. URL: https://doi.org/10.1002/jgt.21730.
  20. Maria Chudnovsky and Shmuel Safra. The Erdős-Hajnal conjecture for bull-free graphs. Journal of Combinatorial Theory, Series B, 98(6):1301-1310, 2008. URL: https://doi.org/10.1016/j.jctb.2008.02.005.
  21. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21275-3.
  22. Peter Damaschke. Parameterized algorithms for double hypergraph dualization with rank limitation and maximum minimal vertex cover. Discrete Optimization, 8(1):18-24, 2011. URL: https://doi.org/10.1016/j.disopt.2010.02.006.
  23. Holger Dell and Dániel Marx. Kernelization of packing problems. In Proc. of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 68-81, 2012. URL: https://doi.org/10.1137/1.9781611973099.6.
  24. Holger Dell and Dieter van Melkebeek. Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. Journal of the ACM, 61(4):23:1-23:27, 2014. URL: https://doi.org/10.1145/2629620.
  25. Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. URL: https://dblp.org/rec/books/daglib/0030488.bib.
  26. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. URL: https://doi.org/10.1007/978-1-4471-5559-1.
  27. Louis Dublois, Tesshu Hanaka, Mehdi Khosravian Ghadikolaei, Michael Lampis, and Nikolaos Melissinos. (In)approximability of Maximum Minimal FVS. In Proc. of the 31st International Symposium on Algorithms and Computation (ISAAC), volume 181 of LIPIcs, pages 3:1-3:14, 2020. The cubic kernel appears in the full version, available at https://arxiv.org/abs/2009.09971. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2020.3.
  28. Louis Dublois, Michael Lampis, and Vangelis Th. Paschos. Upper Dominating Set: Tight Algorithms for Pathwidth and Sub-Exponential Approximation. CoRR, abs/2101.07550, 2021. URL: http://arxiv.org/abs/2101.07550.
  29. Paul Erdős and András Hajnal. Ramsey-type theorems. Discrete Applied Mathematics, 25(1-2):37-52, 1989. URL: https://doi.org/10.1016/0166-218X(89)90045-0.
  30. Henning Fernau. Parameterized algorithms: a graph-theoretic approach. Habilitationsschrift, Universität Tübingen, 2005. URL: http://www.informatik.uni-trier.de/~fernau/papers/habil.pdf.
  31. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Kernelization. Theory of Parameterized Preprocessing. Cambridge University Press, 2019. URL: https://doi.org/10.1017/9781107415157.
  32. Lance Fortnow and Rahul Santhanam. Infeasibility of instance compression and succinct PCPs for NP. Journal of Computer and System Sciences, 77(1):91-106, 2011. URL: https://doi.org/10.1016/j.jcss.2010.06.007.
  33. Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. URL: https://doi.org/https://dl.acm.org/doi/book/10.5555/574848.
  34. Archontia C. Giannopoulou, Daniel Lokshtanov, Saket Saurabh, and Ondrej Suchý. Tree Deletion Set has a polynomial kernel but no OPT^O(1) approximation. SIAM Journal on Discrete Mathematics, 30(3):1371-1384, 2016. URL: https://doi.org/10.1137/15M1038876.
  35. Wayne Goddard and Michael A. Henning. Independent domination in graphs: A survey and recent results. Discrete Mathematics, 313(7):839-854, 2013. URL: https://doi.org/10.1016/j.disc.2012.11.031.
  36. Wayne Goddard and Jeremy Lyle. Independent dominating sets in triangle-free graphs. Journal of Combinatorial Optimization, 23(1):9-20, 2012. URL: https://doi.org/10.1007/s10878-010-9336-4.
  37. Jiong Guo, Iyad A. Kanj, and Stefan Kratsch. Safe approximation and its relation to kernelization. In Proc. of the 6th International Symposium on Parameterized and Exact Computation (IPEC), volume 7112 of LNCS, pages 169-180, 2011. URL: https://doi.org/10.1007/978-3-642-28050-4_14.
  38. András Gyárfás. Reflections on a Problem of Erdős and Hajnal. In Ronald L. Graham, Jaroslav Nesetril, and Steve Butler, editors, The Mathematics of Paul Erdős II, pages 135-141. Springer, 2013. URL: https://doi.org/10.1007/978-1-4614-7254-4_11.
  39. Julie Haviland. Independent domination in triangle-free graphs. Discrete Mathematics, 308(16):3545-3550, 2008. URL: https://doi.org/10.1016/j.disc.2007.07.010.
  40. Danny Hermelin and Xi Wu. Weak compositions and their applications to polynomial lower bounds for kernelization. In Proc. of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 104-113, 2012. URL: https://doi.org/10.1137/1.9781611973099.9.
  41. Dorit S. Hochbaum and David B. Shmoys. Using dual approximation algorithms for scheduling problems theoretical and practical results. Journal of the ACM, 34(1):144-162, 1987. URL: https://doi.org/10.1145/7531.7535.
  42. Johann L. Hurink and Tim Nieberg. Approximating minimum independent dominating sets in wireless networks. Information Processing Letters, 109(2):155-160, 2008. URL: https://doi.org/10.1016/j.ipl.2008.09.021.
  43. Stefan Kratsch. Polynomial kernelizations for MIN F^+ Π₁ and MAX NP. Algorithmica, 63(1-2):532-550, 2012. URL: https://doi.org/10.1007/s00453-011-9559-5.
  44. Stefan Kratsch, Marcin Pilipczuk, Ashutosh Rai, and Venkatesh Raman. Kernel lower bounds using co-nondeterminism: Finding induced hereditary subgraphs. ACM Transactions on Computation Theory, 7(1):4:1-4:18, 2014. URL: https://doi.org/10.1145/2691321.
  45. Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, and Saket Saurabh. Lossy kernelization. In Proc. of the 49th Annual ACM Symposium on Theory of Computing (STOC), pages 224-237, 2017. URL: https://doi.org/10.1145/3055399.3055456.
  46. Oystein Ore. Theory of Graphs. American Mathematical Society Colloquium Publications, volume 38, 1962. URL: https://bookstore.ams.org/coll-38.
  47. Neil Robertson, Daniel P. Sanders, Paul D. Seymour, and Robin Thomas. The four-colour theorem. Journal of Combinatorial Theory, Series B, 70(1):2-44, 1997. URL: https://doi.org/10.1006/jctb.1997.1750.
  48. David P. Williamson and David B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2011. URL: http://www.cambridge.org/de/knowledge/isbn/item5759340/?site_locale=de_DE.
  49. Mihalis Yannakakis. The effect of a connectivity requirement on the complexity of maximum subgraph problems. Journal of the ACM, 26(4):618-630, 1979. URL: https://doi.org/10.1145/322154.322157.
  50. Meirav Zehavi. Maximum Minimal Vertex Cover Parameterized by Vertex Cover. SIAM Journal on Discrete Mathematics, 31(4):2440-2456, 2017. URL: https://doi.org/10.1137/16M109017X.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact