Document Open Access Logo

Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth

Authors Eduard Eiben , Robert Ganian, Thekla Hamm, O-joung Kwon

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2019.42.pdf
  • Filesize: 0.58 MB
  • 15 pages

Document Identifiers

Author Details

Eduard Eiben
  • Department of Informatics, University of Bergen, Bergen, Norway
Robert Ganian
  • Vienna University of Technology, Vienna, Austria
Thekla Hamm
  • Vienna University of Technology, Vienna, Austria
O-joung Kwon
  • Department of Mathematics, Incheon National University, Korea

Funding

E. Eiben was supported by Pareto-Optimal Parameterized Algorithms (ERC Starting Grant 715744). R. Ganian acknowledges support by the Austrian Grant Agency (FWF, project P31336 NFPC), and is also affiliated with FI MUNI, Czech Republic. O. Kwon was supported by the National Research Foundation of Korea (NRF) grant funded by the Ministry of Education (No. NRF-2018R1D1A1B07050294).

Cite AsGet BibTex

Eduard Eiben, Robert Ganian, Thekla Hamm, and O-joung Kwon. Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 42:1-42:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.MFCS.2019.42

Abstract

We develop a framework for applying treewidth-based dynamic programming on graphs with "hybrid structure", i.e., with parts that may not have small treewidth but instead possess other structural properties. Informally, this is achieved by defining a refinement of treewidth which only considers parts of the graph that do not belong to a pre-specified tractable graph class. Our approach allows us to not only generalize existing fixed-parameter algorithms exploiting treewidth, but also fixed-parameter algorithms which use the size of a modulator as their parameter. As the flagship application of our framework, we obtain a parameter that combines treewidth and rank-width to obtain fixed-parameter algorithms for Chromatic Number, Hamiltonian Cycle, and Max-Cut.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • Parameterized complexity
  • treewidth
  • rank-width
  • fixed-parameter algorithms

Metrics

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

References

  1. Takanori Akiyama, Takao Nishizeki, and Nobuji Saito. NP-completeness of the Hamiltonian cycle problem for bipartite graphs. J. Inform. Process., 3:73-76, January 1980. Google Scholar
  2. Hans L. Bodlaender, Fedor V. Fomin, Daniel Lokshtanov, Eelko Penninkx, Saket Saurabh, and Dimitrios M. Thilikos. (Meta) Kernelization. J. ACM, 63(5):44:1-44:69, November 2016. URL: https://doi.org/10.1145/2973749.
  3. Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization. SIAM J. Discrete Math., 27(4):2108-2142, 2013. Google Scholar
  4. Hans L. Bodlaender and Babette van Antwerpen-de Fluiter. Reduction Algorithms for Graphs of Small Treewidth. Inf. Comput., 167(2):86-119, 2001. Google Scholar
  5. Leizhen Cai. Parameterized complexity of vertex colouring. Discrete Applied Mathematics, 127(3):415-429, 2003. Google Scholar
  6. Bruno Courcelle. The Monadic Second-Order Logic of Graphs. I. Recognizable Sets of Finite Graphs. Inf. Comput., 85(1):12-75, 1990. Google Scholar
  7. 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.
  8. Bruno Courcelle and Stephan Olariu. Upper bounds to the clique width of graphs. Discrete Applied Mathematics, 101(1):77-114, 2000. URL: https://doi.org/10.1016/S0166-218X(99)00184-5.
  9. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Texts in Computer Science. Springer, 2013. Google Scholar
  10. Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Fast Hamiltonicity Checking Via Bases of Perfect Matchings. J. ACM, 65(3):12:1-12:46, 2018. Google Scholar
  11. Reinhard Diestel. Graph Theory, volume 173 of Graduate Texts in Mathematics. Springer Verlag, New York, 2nd edition, 2000. Google Scholar
  12. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. Google Scholar
  13. Eduard Eiben, Robert Ganian, and O-joung Kwon. A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion. J. Comput. Syst. Sci., 97:121-146, 2018. Google Scholar
  14. Eduard Eiben, Robert Ganian, and Stefan Szeider. Solving Problems on Graphs of High Rank-Width. Algorithmica, 80(2):742-771, 2018. Google Scholar
  15. Wolfgang Espelage, Frank Gurski, and Egon Wanke. Deciding Clique-Width for Graphs of Bounded Tree-Width. J. Graph Algorithms Appl., 7(2):141-180, 2003. Google Scholar
  16. Michael R. Fellows, Daniel Lokshtanov, Neeldhara Misra, Frances A. Rosamond, and Saket Saurabh. Graph Layout Problems Parameterized by Vertex Cover. In Proc. ISAAC 2008, volume 5369 of Lecture Notes in Computer Science, pages 294-305. Springer, 2008. Google Scholar
  17. Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, and Saket Saurabh. Clique-width: on the price of generality. In Proc. SODA 2009, pages 825-834. SIAM, 2009. Google Scholar
  18. Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, and Saket Saurabh. Intractability of Clique-Width Parameterizations. SIAM J. Comput., 39(5):1941-1956, 2010. Google Scholar
  19. Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, and Saket Saurabh. Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width. SIAM J. Comput., 43(5):1541-1563, 2014. Google Scholar
  20. 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. Google Scholar
  21. Robert Ganian and Petr Hlinený. On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width. Discrete Applied Mathematics, 158(7):851-867, 2010. Google Scholar
  22. Robert Ganian, Petr Hlinený, and Jan Obdrzálek. A unified approach to polynomial algorithms on graphs of bounded (bi-)rank-width. Eur. J. Comb., 34(3):680-701, 2013. Google Scholar
  23. Robert Ganian, Sebastian Ordyniak, and M. S. Ramanujan. Going Beyond Primal Treewidth for (M)ILP. In Proc. AAAI 2017, pages 815-821. AAAI Press, 2017. Google Scholar
  24. Robert Ganian, M. S. Ramanujan, and Stefan Szeider. Backdoor Treewidth for SAT. In Proc. SAT 2017, volume 10491 of Lecture Notes in Computer Science, pages 20-37. Springer, 2017. Google Scholar
  25. Robert Ganian, M. S. Ramanujan, and Stefan Szeider. Combining Treewidth and Backdoors for CSP. In Proc. STACS 2017, volume 66 of LIPIcs, pages 36:1-36:17. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  26. Petr Hliněný and Sang-il Oum. Finding Branch-Decompositions and Rank-Decompositions. SIAM J. Comput., 38(3):1012-1032, June 2008. URL: https://doi.org/10.1137/070685920.
  27. Lars Jaffke, O-joung Kwon, and Jan Arne Telle. A Unified Polynomial-Time Algorithm for Feedback Vertex Set on Graphs of Bounded Mim-Width. In Proc. STACS 2018, volume 96 of LIPIcs, pages 42:1-42:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  28. Klaus Jansen and Petra Scheffler. Generalized Coloring for Tree-like Graphs. Discrete Applied Mathematics, 75(2):135-155, 1997. Google Scholar
  29. Mamadou Moustapha Kanté, Eun Jung Kim, O-joung Kwon, and Christophe Paul. An FPT Algorithm and a Polynomial Kernel for Linear Rankwidth-1 Vertex Deletion. Algorithmica, 79(1):66-95, 2017. URL: https://doi.org/10.1007/s00453-016-0230-z.
  30. Eun Jung Kim and O-joung Kwon. A Polynomial Kernel for Distance-Hereditary Vertex Deletion. In Proc. WADS 2017, volume 10389 of Lecture Notes in Computer Science, pages 509-520. Springer, 2017. Google Scholar
  31. Daniel Kobler and Udi Rotics. Edge dominating set and colorings on graphs with fixed clique-width. Discrete Applied Mathematics, 126(2-3):197-221, 2003. Google Scholar
  32. Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Slightly Superexponential Parameterized Problems. SIAM J. Comput., 47(3):675-702, 2018. Google Scholar
  33. Dániel Marx and Paul Wollan. Immersions in Highly Edge Connected Graphs. SIAM J. Discrete Math., 28(1):503-520, 2014. Google Scholar
  34. Sang-il Oum and Paul D. Seymour. Approximating clique-width and branch-width. J. Comb. Theory, Ser. B, 96(4):514-528, 2006. URL: https://doi.org/10.1016/j.jctb.2005.10.006.
  35. Neil Robertson and Paul D. Seymour. Graph minors. III. Planar tree-width. J. Comb. Theory, Ser. B, 36(1):49-64, 1984. Google Scholar
  36. Sigve Hortemo Sæther and Jan Arne Telle. Between Treewidth and Clique-Width. In Proc. WG 2014, pages 396-407, 2014. 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