More Applications of the d-Neighbor Equivalence: Connectivity and Acyclicity Constraints

Authors Benjamin Bergougnoux , Mamadou Moustapha Kanté



PDF
Thumbnail PDF

File

LIPIcs.ESA.2019.17.pdf
  • Filesize: 0.55 MB
  • 14 pages

Document Identifiers

Author Details

Benjamin Bergougnoux
  • Université Paris Diderot, IRIF, CNRS, Paris, France
Mamadou Moustapha Kanté
  • Université Clermont Auvergne, LIMOS, CNRS, Aubière, France

Acknowledgements

This work is supported by French Agency for Research under the GraphEN project (ANR-15-CE40-0009).

Cite As Get BibTex

Benjamin Bergougnoux and Mamadou Moustapha Kanté. More Applications of the d-Neighbor Equivalence: Connectivity and Acyclicity Constraints. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 17:1-17:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ESA.2019.17

Abstract

In this paper, we design a framework to obtain efficient algorithms for several problems with a global constraint (acyclicity or connectivity) such as Connected Dominating Set, Node Weighted Steiner Tree, Maximum Induced Tree, Longest Induced Path, and Feedback Vertex Set. For all these problems, we obtain 2^O(k)* n^O(1), 2^O(k log(k))* n^O(1), 2^O(k^2) * n^O(1) and n^O(k) time algorithms parameterized respectively by clique-width, Q-rank-width, rank-width and maximum induced matching width. Our approach simplifies and unifies the known algorithms for each of the parameters and match asymptotically also the running time of the best algorithms for basic NP-hard problems such as Vertex Cover and Dominating Set. Our framework is based on the d-neighbor equivalence defined in [Bui-Xuan, Telle and Vatshelle, TCS 2013]. The results we obtain highlight the importance and the generalizing power of this equivalence relation on width measures. We also prove that this equivalence relation could be useful for Max Cut: a W[1]-hard problem parameterized by clique-width. For this latter problem, we obtain n^O(k), n^O(k) and n^(2^O(k)) time algorithm parameterized by clique-width, Q-rank-width and rank-width.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • connectivity problem
  • feedback vertex set
  • d-neighbor equivalence
  • {sigma,rho}-domination
  • clique-width
  • rank-width
  • mim-width

Metrics

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

References

  1. Rémy Belmonte and Martin Vatshelle. Graph classes with structured neighborhoods and algorithmic applications. Theoret. Comput. Sci., 511:54-65, 2013. URL: http://dx.doi.org/10.1016/j.tcs.2013.01.011.
  2. Benjamin Bergougnoux. Matrix Decomposition and Algorithmic Application to (Hyper)Graphs. PhD thesis, Université Clermont Auvergne, 2019. lien vers chapitre. Google Scholar
  3. Benjamin Bergougnoux and Mamadou Moustapha Kanté. Fast exact algorithms for some connectivity problems parametrized by clique-width. To appear at Theoretical Computer Science, 2017. URL: https://hal.archives-ouvertes.fr/hal-01560555.
  4. Benjamin Bergougnoux, Mamadou Moustapha Kanté, and O-joung Kwon. An Optimal XP Algorithm for Hamiltonian Cycle on Graphs of Bounded Clique-Width. In Algorithms and Data Structures - 15th International Symposium, WADS 2017, St. John’s, NL, Canada, July 31 - August 2, 2017, Proceedings, pages 121-132, 2017. URL: http://dx.doi.org/10.1007/978-3-319-62127-2_11.
  5. Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Inform. and Comput., 243:86-111, 2015. URL: http://dx.doi.org/10.1016/j.ic.2014.12.008.
  6. Binh-Minh Bui-Xuan, Jan Arne Telle, and Martin Vatshelle. Boolean-Width of Graphs. In Jianer Chen and Fedor V. Fomin, editors, IWPEC, volume 5917 of Lecture Notes in Computer Science, pages 61-74. Springer, 2009. URL: http://dx.doi.org/10.1007/978-3-642-11269-0_5.
  7. Binh-Minh Bui-Xuan, Jan Arne Telle, and Martin Vatshelle. Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems. Theoret. Comput. Sci., 511:66-76, 2013. URL: http://dx.doi.org/10.1016/j.tcs.2013.01.009.
  8. Bruno Courcelle and Stephan Olariu. Upper bounds to the clique width of graphs. Discrete Applied Mathematics, 101(1-3):77-114, 2000. Google Scholar
  9. Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michał Pilipczuk, Johan M. M. van Rooij, and Jakub Onufry Wojtaszczyk. Solving connectivity problems parameterized by treewidth in single exponential time (extended abstract). In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science - FOCS 2011, pages 150-159. IEEE Computer Soc., Los Alamitos, CA, 2011. URL: http://dx.doi.org/10.1109/FOCS.2011.23.
  10. Reinhard Diestel. Graph Theory. Number 173 in Graduate Texts in Mathematics. Springer, third edition, 2005. Google Scholar
  11. 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. URL: http://dx.doi.org/10.1137/130910932.
  12. Robert Ganian and Petr Hliněný. On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width. Discrete Appl. Math., 158(7):851-867, 2010. URL: http://dx.doi.org/10.1016/j.dam.2009.10.018.
  13. Petr A. Golovach, Pinar Heggernes, Mamadou Moustapha Kanté, Dieter Kratsch, Sigve Hortemo Sæther, and Yngve Villanger. Output-Polynomial Enumeration on Graphs of Bounded (Local) Linear MIM-Width. Algorithmica, 80(2):714-741, 2018. URL: http://dx.doi.org/10.1007/s00453-017-0289-1.
  14. Lars Jaffke, O-joung Kwon, and Jan Arne Telle. Polynomial-Time Algorithms for the Longest Induced Path and Induced Disjoint Paths Problems on Graphs of Bounded Mim-Width. In 12th International Symposium on Parameterized and Exact Computation, IPEC 2017, September 6-8, 2017, Vienna, Austria, pages 21:1-21:13, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.IPEC.2017.21.
  15. 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 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, February 28 to March 3, 2018, Caen, France, pages 42:1-42:14, 2018. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2018.42.
  16. Ki Hang Kim. Boolean matrix theory and applications, volume 70. Dekker, 1982. Google Scholar
  17. Pedro Montealegre and Ioan Todinca. On Distance-d Independent Set and Other Problems in Graphs with "few" Minimal Separators. In Graph-Theoretic Concepts in Computer Science - 42nd International Workshop, WG 2016, Istanbul, Turkey, June 22-24, 2016, Revised Selected Papers, pages 183-194, 2016. URL: http://dx.doi.org/10.1007/978-3-662-53536-3_16.
  18. Sang-Il Oum. Graphs of Bounded Rank Width. PhD thesis, Princeton University, 2005. Google Scholar
  19. Sang-il Oum, Sigve Hortemo Sæther, and Martin Vatshelle. Faster algorithms for vertex partitioning problems parameterized by clique-width. Theoret. Comput. Sci., 535:16-24, 2014. URL: http://dx.doi.org/10.1016/j.tcs.2014.03.024.
  20. Sang-il Oum and Paul Seymour. Approximating clique-width and branch-width. J. Combin. Theory Ser. B, 96(4):514-528, 2006. URL: http://dx.doi.org/10.1016/j.jctb.2005.10.006.
  21. Michaël Rao. Décompositions de Graphes et Algorithmes Efficaces. PhD thesis, Université Paul Verlaine, Metz, 2006. Google Scholar
  22. Jan Arne Telle and Andrzej Proskurowski. Algorithms for vertex partitioning problems on partial k-trees. SIAM J. Discrete Math., 10(4):529-550, 1997. URL: http://dx.doi.org/10.1137/S0895480194275825.
  23. Martin Vatshelle. New width parameters of graphs. PhD thesis, University of Bergen, Bergen, Norway, 2012. 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