Nothing Special   »   [go: up one dir, main page]
Document Open Access Logo

Co-Degeneracy and Co-Treewidth: Using the Complement to Solve Dense Instances

Authors Gabriel L. Duarte, Mateus de Oliveira Oliveira , Uéverton S. Souza

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2021.42.pdf
  • Filesize: 0.75 MB
  • 17 pages

Document Identifiers

Author Details

Gabriel L. Duarte
  • Institute of Computing, Fluminense Federal University, Niterói, Brazil
Mateus de Oliveira Oliveira
  • Department of Informatics, University of Bergen, Norway
Uéverton S. Souza
  • Institute of Computing, Fluminense Federal University, Niterói, Brazil

Funding

  • de Oliveira Oliveira, Mateus: Bergen Research Foundation, and by the Research Council of Norway (Grant Number: 288761).
  • Souza, Uéverton S.: Grant E-26/203.272/2017 - Carlos Chagas Filho Research Support Foundation (FAPERJ), and Grant 309832/2020-9 - National Council for Scientific and Technological Development (CNPq).

Cite AsGet BibTex

Gabriel L. Duarte, Mateus de Oliveira Oliveira, and Uéverton S. Souza. Co-Degeneracy and Co-Treewidth: Using the Complement to Solve Dense Instances. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 42:1-42:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.MFCS.2021.42

Abstract

Clique-width and treewidth are two of the most important and useful graph parameters, and several problems can be solved efficiently when restricted to graphs of bounded clique-width or treewidth. Bounded treewidth implies bounded clique-width, but not vice versa. Problems like Longest Cycle, Longest Path, MaxCut, Edge Dominating Set, and Graph Coloring are fixed-parameter tractable when parameterized by the treewidth, but they cannot be solved in FPT time when parameterized by the clique-width unless FPT = W[1], as shown by Fomin, Golovach, Lokshtanov, and Saurabh [SIAM J. Comput. 2010, SIAM J. Comput. 2014]. For a given problem that is fixed-parameter tractable when parameterized by treewidth, but intractable when parameterized by clique-width, there may exist infinite families of instances of bounded clique-width and unbounded treewidth where the problem can be solved efficiently. In this work, we initiate a systematic study of the parameters co-treewidth (the treewidth of the complement of the input graph) and co-degeneracy (the degeneracy of the complement of the input graph). We show that Longest Cycle, Longest Path, and Edge Dominating Set are FPT when parameterized by co-degeneracy. On the other hand, Graph Coloring is para-NP-complete when parameterized by co-degeneracy but FPT when parameterized by the co-treewidth. Concerning MaxCut, we give an FPT algorithm parameterized by co-treewidth, while we leave open the complexity of the problem parameterized by co-degeneracy. Additionally, we show that Precoloring Extension is fixed-parameter tractable when parameterized by co-treewidth, while this problem is known to be W[1]-hard when parameterized by treewidth. These results give evidence that co-treewidth is a useful width parameter for handling dense instances of problems for which an FPT algorithm for clique-width is unlikely to exist. Finally, we develop an algorithmic framework for co-degeneracy based on the notion of Bondy-Chvátal closure.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • FPT
  • treewidth
  • degeneracy
  • complement graph
  • Bondy-Chvátal closure

Metrics

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

References

  1. Stefan Arnborg, Jens Lagergren, and Detlef Seese. Easy problems for tree-decomposable graphs. Journal of Algorithms, 12(2):308-340, 1991. Google Scholar
  2. Richard Bellman. Dynamic programming treatment of the travelling salesman problem. Journal of the ACM (JACM), 9(1):61-63, 1962. Google Scholar
  3. Hans L. Bodlaender. A partial k-arboretum of graphs with bounded treewidth. Theoretical Computer Science, 209(1):1-45, 1998. Google Scholar
  4. Hans L Bodlaender, Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. In International Colloquium on Automata, Languages, and Programming, pages 196-207. Springer, 2013. Google Scholar
  5. Hans L Bodlaender, Pål Grønås, Markus S Dregi, Fedor V Fomin, Daniel Lokshtanov, and Michał Pilipczuk. A c^kn 5-approximation algorithm for treewidth. SIAM Journal on Computing, 45(2):317-378, 2016. Google Scholar
  6. Hans L. Bodlaender and Klaus Jansen. On the complexity of the maximum cut problem. Nordic Journal of Computing, 7(1):14-31, 2000. Google Scholar
  7. Hans L Bodlaender, Erik Jan Van Leeuwen, Johan MM Van Rooij, and Martin Vatshelle. Faster algorithms on branch and clique decompositions. In International Symposium on Mathematical Foundations of Computer Science, pages 174-185. Springer, 2010. Google Scholar
  8. J Adrian Bondy and Vasek Chvátal. A method in graph theory. Discrete Mathematics, 15(2):111-135, 1976. Google Scholar
  9. Richard B Borie, R Gary Parker, and Craig A Tovey. Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families. Algorithmica, 7(1-6):555-581, 1992. Google Scholar
  10. Andreas Brandstädt, Feodor F Dragan, Hoàng-Oanh Le, and Raffaele Mosca. New graph classes of bounded clique-width. Theory of Computing Systems, 38(5):623-645, 2005. Google Scholar
  11. Stephan Brandt and Henk Jan Veldman. Degree sums for edges and cycle lengths in graphs. Journal of graph theory, 25(4):253-256, 1997. Google Scholar
  12. Hajo Broersma, Zdeněk Ryjáček, and Ingo Schiermeyer. Closure concepts: a survey. Graphs and Combinatorics, 16(1):17-48, 2000. Google Scholar
  13. Derek G Corneil and Udi Rotics. On the relationship between clique-width and treewidth. SIAM Journal on Computing, 34(4):825-847, 2005. Google Scholar
  14. Stavros S Cosmadakis and Christos H Papadimitriou. The traveling salesman problem with many visits to few cities. SIAM Journal on Computing, 13(1):99-108, 1984. Google Scholar
  15. B. Courcelle, J. A. Makowsky, and U. Rotics. Linear time solvable optimization problems on graphs of bounded clique-width. Theory of Computing Systems, 33(2):125-150, 2000. Google Scholar
  16. Bruno Courcelle. The monadic second-order logic of graphs. I. recognizable sets of finite graphs. Information and Computation, 85(1):12-75, 1990. Google Scholar
  17. Bruno Courcelle. The monadic second-order logic of graphs III: Tree-decompositions, minors and complexity issues. RAIRO-Theoretical Informatics and Applications-Informatique Théorique et Applications, 26(3):257-286, 1992. Google Scholar
  18. Bruno Courcelle. The monadic second order logic of graphs VI: On several representations of graphs by relational structures. Discrete Applied Mathematics, 54(2-3):117-149, 1994. Google Scholar
  19. Bruno Courcelle and Joost Engelfriet. Graph structure and monadic second-order logic: a language-theoretic approach, volume 138. Cambridge University Press, 2012. Google Scholar
  20. Bruno Courcelle and Stephan Olariu. Upper bounds to the clique width of graphs. Discrete Applied Mathematics, 101(1-3):77-114, 2000. Google Scholar
  21. Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  22. David P Dailey. Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete. Discrete Mathematics, 30(3):289-293, 1980. Google Scholar
  23. Guilherme de C. M. Gomes, Carlos V. G. C. Lima, and Vinícius Fernandes dos Santos. Parameterized complexity of equitable coloring. Discrete Mathematics & Theoretical Computer Science, 21(1), 2019. URL: http://dmtcs.episciences.org/5464.
  24. Rodney G. Downey and Michael R. Fellows. Fundamentals of parameterized complexity, volume 4. Springer, 2013. Google Scholar
  25. Pavel Dvořák, Dusan Knop, and Tomás Masarík. Anti-path cover on sparse graph classes. In Jan Bouda, Lukás Holík, Jan Kofron, Jan Strejcek, and Adam Rambousek, editors, Proceedings 11th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science, MEMICS 2016, Telč, Czech Republic, 21st-23rd October 2016, volume 233 of EPTCS, pages 82-86, 2016. Google Scholar
  26. Eduard Eiben, Robert Ganian, Thekla Hamm, and O joung Kwon. Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth. In Peter Rossmanith, Pinar Heggernes, and Joost-Pieter Katoen, editors, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019), volume 138 of Leibniz International Proceedings in Informatics (LIPIcs), pages 42:1-42:15, Dagstuhl, Germany, 2019. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.MFCS.2019.42.
  27. Michael R. Fellows, Fedor V. Fomin, Daniel Lokshtanov, Frances Rosamond, Saket Saurabh, Stefan Szeider, and Carsten Thomassen. On the complexity of some colorful problems parameterized by treewidth. Information and Computation, 209(2):143-153, 2011. Google Scholar
  28. Fedor V Fomin, Petr A Golovach, Daniel Lokshtanov, and Saket Saurabh. Clique-width: on the price of generality. In Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms, pages 825-834. SIAM, 2009. Google Scholar
  29. Fedor V Fomin, Petr A Golovach, Daniel Lokshtanov, and Saket Saurabh. Algorithmic lower bounds for problems parameterized by clique-width. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pages 493-502. SIAM, 2010. Google Scholar
  30. Fedor V Fomin, Petr A Golovach, Daniel Lokshtanov, and Saket Saurabh. Intractability of clique-width parameterizations. SIAM Journal on Computing, 39(5):1941-1956, 2010. Google Scholar
  31. Fedor V Fomin, Petr A Golovach, Daniel Lokshtanov, and Saket Saurabh. Almost optimal lower bounds for problems parameterized by clique-width. SIAM Journal on Computing, 43(5):1541-1563, 2014. Google Scholar
  32. Jakub Gajarsky, Michael Lampis, and Sebastian Ordyniak. Parameterized algorithms for modular-width. In International Symposium on Parameterized and Exact Computation, pages 163-176. Springer, 2013. Google Scholar
  33. Robert Ganian. Twin-cover: Beyond vertex cover in parameterized algorithmics. In International Symposium on Parameterized and Exact Computation, pages 259-271. Springer, 2011. Google Scholar
  34. Robert Ganian, Petr Hliněny, Jaroslav Nešetřil, Jan Obdržálek, Patrice Ossona de Mendez, and Reshma Ramadurai. When trees grow low: shrubs and fast MSO 1. In International Symposium on Mathematical Foundations of Computer Science, pages 419-430. Springer, 2012. Google Scholar
  35. Martin Charles Golumbic and Udi Rotics. On the clique-width of some perfect graph classes. International Journal of Foundations of Computer Science, 11(03):423-443, 2000. Google Scholar
  36. Michael Held and Richard M Karp. A dynamic programming approach to sequencing problems. Journal of the Society for Industrial and Applied mathematics, 10(1):196-210, 1962. Google Scholar
  37. Petr Hliněny, Sang-il Oum, Detlef Seese, and Georg Gottlob. Width parameters beyond tree-width and their applications. The computer journal, 51(3):326-362, 2008. Google Scholar
  38. Dušan Knop, Martin Koutecky, Tomáš Masařík, and Tomáš Toufar. Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity. In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 344-357. Springer, 2017. Google Scholar
  39. Daniel Král', Jan Kratochvíl, Zsolt Tuza, and Gerhard J. Woeginger. Complexity of coloring graphs without forbidden induced subgraphs. In Andreas Brandstädt and Van Bang Le, editors, Graph-Theoretic Concepts in Computer Science, pages 254-262, Berlin, Heidelberg, 2001. Springer Berlin Heidelberg. Google Scholar
  40. Michael Lampis. Algorithmic meta-theorems for restrictions of treewidth. Algorithmica, 64(1):19-37, 2012. Google Scholar
  41. Clemens Lautemann. Logical definability of NP-optimisation problems with monadic auxiliary predicates. In International Workshop on Computer Science Logic, pages 327-339. Springer, 1992. Google Scholar
  42. Meena Mahajan and Venkatesh Raman. Parameterizing above guaranteed values: Maxsat and maxcut. J. Algorithms, 31(2):335-354, 1999. Google Scholar
  43. Sang-il Oum and Paul Seymour. Approximating clique-width and branch-width. Journal of Combinatorial Theory, Series B, 96(4):514-528, 2006. Google Scholar
  44. Elena Prieto. The method of extremal structure on the k-maximum cut problem. In Proceedings of the 2005 Australasian Symposium on Theory of Computing-Volume 41, pages 119-126. Australian Computer Society, Inc., 2005. Google Scholar
  45. Neil Robertson and Paul D. Seymour. Graph minors. X. obstructions to tree-decomposition. Journal of Combinatorial Theory, Series B, 52(2):153-190, 1991. Google Scholar
  46. Sigve Hortemo Sæther and Jan Arne Telle. Between treewidth and clique-width. Algorithmica, 75(1):218-253, 2016. Google Scholar
  47. Johan M. M. van Rooij, Hans L. Bodlaender, Erik Jan van Leeuwen, Peter Rossmanith, and Martin Vatshelle. Fast dynamic programming on graph decompositions, 2018. URL: http://arxiv.org/abs/1806.01667.
  48. Johan MM Van Rooij, Hans L Bodlaender, and Peter Rossmanith. Dynamic programming on tree decompositions using generalised fast subset convolution. In European Symposium on Algorithms, pages 566-577. Springer, 2009. Google Scholar
  49. Mihalis Yannakakis and Fanica Gavril. Edge dominating sets in graphs. SIAM Journal on Applied Mathematics, 38(3):364-372, 1980. Google Scholar
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