Document Open Access Logo

Twin-Width and Polynomial Kernels

Authors Édouard Bonnet , Eun Jung Kim , Amadeus Reinald, Stéphan Thomassé, Rémi Watrigant

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2021.10.pdf
  • Filesize: 0.92 MB
  • 16 pages

Document Identifiers

Author Details

Édouard Bonnet
  • Univ Lyon, CNRS, ENS de Lyon, Université Claude Bernard Lyon 1, LIP UMR5668, France
Eun Jung Kim
  • Université Paris-Dauphine, PSL University, CNRS UMR7243, LAMSADE, Paris, France
Amadeus Reinald
  • Univ Lyon, CNRS, ENS de Lyon, Université Claude Bernard Lyon 1, LIP UMR5668, France
Stéphan Thomassé
  • Univ Lyon, CNRS, ENS de Lyon, Université Claude Bernard Lyon 1, LIP UMR5668, France
Rémi Watrigant
  • Univ Lyon, CNRS, ENS de Lyon, Université Claude Bernard Lyon 1, LIP UMR5668, France

Funding

The first, fourth, and fifth authors were supported by the ANR project DIGRAPHS (ANR-19-CE48-0013-01), the first, second, fourth, and fifth authors were supported by the ANR project TWIN-WIDTH (ANR-21-CE48-0014-01), and the second author was supported by the ANR project ASSK (ANR-18-CE40-0025-01) from French National Research Agency.

Acknowledgements

We thank Noga Alon and Bart M. P. Jansen for independently asking whether k-Dominating Set admits a polynomial kernel on classes of bounded twin-width, an interesting question that led to our main result.

Cite As Get BibTex

Édouard Bonnet, Eun Jung Kim, Amadeus Reinald, Stéphan Thomassé, and Rémi Watrigant. Twin-Width and Polynomial Kernels. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.IPEC.2021.10

Abstract

We study the existence of polynomial kernels for parameterized problems without a polynomial kernel on general graphs, when restricted to graphs of bounded twin-width. It was previously observed in [Bonnet et al., ICALP'21] that the problem k-Independent Set allows no polynomial kernel on graph of bounded twin-width by a very simple argument, which extends to several other problems such as k-Independent Dominating Set, k-Path, k-Induced Path, k-Induced Matching. In this work, we examine the k-Dominating Set and variants of k-Vertex Cover for the existence of polynomial kernels. 
As a main result, we show that k-Dominating Set does not admit a polynomial kernel on graphs of twin-width at most 4 under a standard complexity-theoretic assumption. The reduction is intricate, especially due to the effort to bring the twin-width down to 4, and it can be tweaked to work for Connected k-Dominating Set and Total k-Dominating Set with a slightly worse bound on the twin-width.
On the positive side, we obtain a simple quadratic vertex kernel for Connected k-Vertex Cover and Capacitated k-Vertex Cover on graphs of bounded twin-width. These kernels rely on that graphs of bounded twin-width have Vapnik-Chervonenkis (VC) density 1, that is, for any vertex set X, the number of distinct neighborhoods in X is at most c⋅|X|, where c is a constant depending only on the twin-width. Interestingly the kernel applies to any graph class of VC density 1, and does not require a witness sequence. We also present a more intricate O(k^{1.5}) vertex kernel for Connected k-Vertex Cover.
Finally we show that deciding if a graph has twin-width at most 1 can be done in polynomial time, and observe that most graph optimization/decision problems can be solved in polynomial time on graphs of twin-width at most 1.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Fixed parameter tractability
Keywords
  • Twin-width
  • kernelization
  • lower bounds
  • Dominating Set

Metrics

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

Related Versions

References

  1. Jochen Alber, Michael R. Fellows, and Rolf Niedermeier. Polynomial-time data reduction for dominating set. J. ACM, 51(3):363-384, 2004. URL: https://doi.org/10.1145/990308.990309.
  2. Noga Alon and Shai Gutner. Linear time algorithms for finding a dominating set of fixed size in degenerated graphs. Algorithmica, 54(4):544-556, 2009. URL: https://doi.org/10.1007/s00453-008-9204-0.
  3. Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width III: Max Independent Set and Coloring. CoRR, abs/2007.14161, 2020. URL: http://arxiv.org/abs/2007.14161.
  4. Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width II: small classes. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1977-1996, 2021. URL: https://doi.org/10.1137/1.9781611976465.118.
  5. Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, Pierre Simon, Stéphan Thomassé, and Szymon Toruńczyk. Twin-width IV: ordered graphs and matrices. CoRR, abs/2102.03117, 2021. URL: http://arxiv.org/abs/2102.03117.
  6. Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width I: tractable FO model checking. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 601-612. IEEE, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00062.
  7. Nicolas Bousquet, Daniel Gonçalves, George B. Mertzios, Christophe Paul, Ignasi Sau, and Stéphan Thomassé. Parameterized domination in circle graphs. Theory Comput. Syst., 54(1):45-72, 2014. URL: https://doi.org/10.1007/s00224-013-9478-8.
  8. Timothy M. Chan, Elyot Grant, Jochen Könemann, and Malcolm Sharpe. Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling. In Yuval Rabani, editor, Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pages 1576-1585. SIAM, 2012. URL: https://doi.org/10.1137/1.9781611973099.125.
  9. Jianer Chen, Henning Fernau, Iyad A. Kanj, and Ge Xia. Parametric duality and kernelization: Lower bounds and upper bounds on kernel size. SIAM J. Comput., 37(4):1077-1106, 2007. URL: https://doi.org/10.1137/050646354.
  10. Jianer Chen, Xiuzhen Huang, Iyad A. Kanj, and Ge Xia. Strong computational lower bounds via parameterized complexity. J. Comput. Syst. Sci., 72(8):1346-1367, 2006. URL: https://doi.org/10.1016/j.jcss.2006.04.007.
  11. Brent N. Clark, Charles J. Colbourn, and David S. Johnson. Unit disk graphs. Discret. Math., 86(1-3):165-177, 1990. URL: https://doi.org/10.1016/0012-365X(90)90358-O.
  12. Bruno Courcelle, Johann A. Makowsky, and Udi Rotics. Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst., 33(2):125-150, 2000. URL: https://doi.org/10.1007/s002249910009.
  13. Marek Cygan. Deterministic parameterized connected vertex cover. In Fedor V. Fomin and Petteri Kaski, editors, Algorithm Theory - SWAT 2012 - 13th Scandinavian Symposium and Workshops, Helsinki, Finland, July 4-6, 2012. Proceedings, volume 7357 of Lecture Notes in Computer Science, pages 95-106. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-31155-0_9.
  14. Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized algorithms, volume 4. Springer, 2015. Google Scholar
  15. Marek Cygan, Fabrizio Grandoni, and Danny Hermelin. Tight kernel bounds for problems on graphs with small degeneracy. ACM Trans. Algorithms, 13(3):43:1-43:22, 2017. URL: https://doi.org/10.1145/3108239.
  16. Marek Cygan, Geevarghese Philip, Marcin Pilipczuk, Michal Pilipczuk, and Jakub Onufry Wojtaszczyk. Dominating set is fixed parameter tractable in claw-free graphs. Theor. Comput. Sci., 412(50):6982-7000, 2011. URL: https://doi.org/10.1016/j.tcs.2011.09.010.
  17. Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, and Jakub Onufry Wojtaszczyk. Kernelization hardness of connectivity problems in d-degenerate graphs. Discret. Appl. Math., 160(15):2131-2141, 2012. URL: https://doi.org/10.1016/j.dam.2012.05.016.
  18. Anuj Dawar and Stephan Kreutzer. Domination problems in nowhere-dense classes. In Ravi Kannan and K. Narayan Kumar, editors, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2009, December 15-17, 2009, IIT Kanpur, India, volume 4 of LIPIcs, pages 157-168. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2009. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2009.2315.
  19. Erik D. Demaine, Fedor V. Fomin, Mohammad Taghi Hajiaghayi, and Dimitrios M. Thilikos. Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs. J. ACM, 52(6):866-893, 2005. URL: https://doi.org/10.1145/1101821.1101823.
  20. Michael Dom, Daniel Lokshtanov, and Saket Saurabh. Kernelization Lower Bounds Through Colors and IDs. ACM Trans. Algorithms, 11(2):13:1-13:20, 2014. URL: https://doi.org/10.1145/2650261.
  21. Frederic Dorn. Dynamic programming and fast matrix multiplication. In Yossi Azar and Thomas Erlebach, editors, Algorithms - ESA 2006, 14th Annual European Symposium, Zurich, Switzerland, September 11-13, 2006, Proceedings, volume 4168 of Lecture Notes in Computer Science, pages 280-291. Springer, 2006. URL: https://doi.org/10.1007/11841036_27.
  22. 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.
  23. Pål Grønås Drange, Markus Sortland Dregi, Fedor V. Fomin, Stephan Kreutzer, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Felix Reidl, Fernando Sánchez Villaamil, Saket Saurabh, Sebastian Siebertz, and Somnath Sikdar. Kernelization and sparseness: the case of dominating set. In Nicolas Ollinger and Heribert Vollmer, editors, 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17-20, 2016, Orléans, France, volume 47 of LIPIcs, pages 31:1-31:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.STACS.2016.31.
  24. Martin Farber and J. Mark Keil. Domination in permutation graphs. J. Algorithms, 6(3):309-321, 1985. URL: https://doi.org/10.1016/0196-6774(85)90001-X.
  25. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M. Thilikos. Kernels for (connected) dominating set on graphs with excluded topological minors. ACM Trans. Algorithms, 14(1):6:1-6:31, 2018. URL: https://doi.org/10.1145/3155298.
  26. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M. Thilikos. Bidimensionality and kernels. SIAM J. Comput., 49(6):1397-1422, 2020. URL: https://doi.org/10.1137/16M1080264.
  27. Fedor V. Fomin and Dimitrios M. Thilikos. Fast parameterized algorithms for graphs on surfaces: Linear kernel and exponential speed-up. In Josep Díaz, Juhani Karhumäki, Arto Lepistö, and Donald Sannella, editors, Automata, Languages and Programming: 31st International Colloquium, ICALP 2004, Turku, Finland, July 12-16, 2004. Proceedings, volume 3142 of Lecture Notes in Computer Science, pages 581-592. Springer, 2004. URL: https://doi.org/10.1007/978-3-540-27836-8_50.
  28. Fedor V. Fomin and Dimitrios M. Thilikos. Dominating sets in planar graphs: Branch-width and exponential speed-up. SIAM J. Comput., 36(2):281-309, 2006. URL: https://doi.org/10.1137/S0097539702419649.
  29. Jakub Gajarský, Petr Hlinený, Jan Obdrzálek, Sebastian Ordyniak, Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, and Somnath Sikdar. Kernelization using structural parameters on sparse graph classes. J. Comput. Syst. Sci., 84:219-242, 2017. URL: https://doi.org/10.1016/j.jcss.2016.09.002.
  30. M. R. Garey, David S. Johnson, and Larry J. Stockmeyer. Some simplified np-complete graph problems. Theor. Comput. Sci., 1(3):237-267, 1976. URL: https://doi.org/10.1016/0304-3975(76)90059-1.
  31. Petr A. Golovach and Yngve Villanger. Parameterized complexity for domination problems on degenerate graphs. In Hajo Broersma, Thomas Erlebach, Tom Friedetzky, and Daniël Paulusma, editors, Graph-Theoretic Concepts in Computer Science, 34th International Workshop, WG 2008, Durham, UK, June 30 - July 2, 2008. Revised Papers, volume 5344 of Lecture Notes in Computer Science, pages 195-205, 2008. URL: https://doi.org/10.1007/978-3-540-92248-3_18.
  32. Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz. Deciding first-order properties of nowhere dense graphs. J. ACM, 64(3):17:1-17:32, 2017. URL: https://doi.org/10.1145/3051095.
  33. Shai Gutner. Polynomial kernels and faster algorithms for the dominating set problem on graphs with an excluded minor. In Jianer Chen and Fedor V. Fomin, editors, Parameterized and Exact Computation, 4th International Workshop, IWPEC 2009, Copenhagen, Denmark, September 10-11, 2009, Revised Selected Papers, volume 5917 of Lecture Notes in Computer Science, pages 246-257. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-11269-0_20.
  34. Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen, and Gerhard J. Woeginger. Domination when the stars are out. ACM Trans. Algorithms, 15(2):25:1-25:90, 2019. URL: https://doi.org/10.1145/3301445.
  35. Eun Jung Kim, Alexander Langer, Christophe Paul, Felix Reidl, Peter Rossmanith, Ignasi Sau, and Somnath Sikdar. Linear kernels and single-exponential algorithms via protrusion decompositions. ACM Trans. Algorithms, 12(2):21:1-21:41, 2016. URL: https://doi.org/10.1145/2797140.
  36. Tomohiro Koana, Christian Komusiewicz, and Frank Sommer. Exploiting c-closure in kernelization algorithms for graph problems. In Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders, editors, 28th Annual European Symposium on Algorithms, ESA 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference), volume 173 of LIPIcs, pages 65:1-65:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ESA.2020.65.
  37. David Lichtenstein. Planar formulae and their uses. SIAM J. Comput., 11(2):329-343, 1982. URL: https://doi.org/10.1137/0211025.
  38. Adam Marcus and Gábor Tardos. Excluded permutation matrices and the Stanley-Wilf conjecture. J. Comb. Theory, Ser. A, 107(1):153-160, 2004. URL: https://doi.org/10.1016/j.jcta.2004.04.002.
  39. Jaroslav Nesetril and Patrice Ossona de Mendez. Sparsity - Graphs, Structures, and Algorithms, volume 28 of Algorithms and combinatorics. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-27875-4.
  40. Geevarghese Philip, Venkatesh Raman, and Somnath Sikdar. Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond. ACM Trans. Algorithms, 9(1):11:1-11:23, 2012. URL: https://doi.org/10.1145/2390176.2390187.
  41. Wojciech Przybyszewski and Szymon Toruńczyk. personal communication, 2021. Google Scholar
  42. Venkatesh Raman and Saket Saurabh. Short Cycles Make W -hard Problems Hard: FPT Algorithms for W-hard Problems in Graphs with no Short Cycles. Algorithmica, 52(2):203-225, 2008. URL: https://doi.org/10.1007/s00453-007-9148-9.
  43. Jan Arne Telle and Yngve Villanger. FPT algorithms for domination in sparse graphs and beyond. Theor. Comput. Sci., 770:62-68, 2019. URL: https://doi.org/10.1016/j.tcs.2018.10.030.
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 About DROPS Imprint Privacy Contact