Document Open Access Logo

Maximum Matching Width: New Characterizations and a Fast Algorithm for Dominating Set

Authors Jisu Jeong, Sigve Hortemo Sæther, Jan Arne Telle

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2015.212.pdf
  • Filesize: 0.5 MB
  • 12 pages

Document Identifiers

Author Details

Jisu Jeong
Sigve Hortemo Sæther
Jan Arne Telle

Cite As Get BibTex

Jisu Jeong, Sigve Hortemo Sæther, and Jan Arne Telle. Maximum Matching Width: New Characterizations and a Fast Algorithm for Dominating Set. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 212-223, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.IPEC.2015.212

Abstract

We give alternative definitions for maximum matching width, e.g., a graph G has mmw(G) <= k if and only if it is a subgraph of a chordal graph H and for every maximal clique X of H there exists A,B,C \subseteq X with A \cup B \cup C=X and |A|,|B|,|C| <= k such that any subset of X that is a minimal separator of H is a subset of either A, B or C.  Treewidth and branchwidth have alternative definitions through intersections of subtrees, where treewidth focuses on nodes and branchwidth focuses on edges. We show that mm-width combines both aspects, focusing on nodes and on edges. Based on this we prove that given a graph G and a branch decomposition of mm-width k we can solve Dominating Set in time O^*(8^k), thereby beating O^*(3^{tw(G)}) whenever tw(G) > log_3(8) * k ~ 1.893  k. Note that mmw(G) <= tw(G)+1 <= 3 mmw(G) and these inequalities are tight. Given only the graph G and using the best known  algorithms to find decompositions, maximum matching width will be better for solving Dominating Set whenever tw(G) >  1.549 * mmw(G).

Subject Classification

Keywords
  • FPT algorithms
  • treewidth
  • dominating set

Metrics

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

References

  1. Eyal Amir. Approximation algorithms for treewidth. Algorithmica, 56(4):448-479, 2010. Google Scholar
  2. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Fourier meets Möbius: fast subset convolution. In STOC'07 - Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pages 67-74. ACM, New York, 2007. Google Scholar
  3. Hans L Bodlaender, Pal Gronas Drange, Markus S Dregi, Fedor V Fomin, Daniel Lokshtanov, and Michal Pilipczuk. An o(c^k n) 5-approximation algorithm for treewidth. In Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on, pages 499-508. IEEE, 2013. Google Scholar
  4. Hans L. Bodlaender and Ton Kloks. Efficient and constructive algorithms for the pathwidth and treewidth of graphs. J. Algorithms, 21(2):358-402, 1996. Google Scholar
  5. Hans L. Bodlaender, Erik Jan van Leeuwen, Johan M. M. van Rooij, and Martin Vatshelle. Faster algorithms on branch and clique decompositions. In Mathematical foundations of computer science 2010, volume 6281 of Lecture Notes in Comput. Sci., pages 174-185. Springer, Berlin, 2010. Google Scholar
  6. Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer International Publishing, New York, 2016. Google Scholar
  7. Reinhard Diestel. Graph theory, volume 173 of Graduate Texts in Mathematics. Springer, Heidelberg, fourth edition, 2010. Google Scholar
  8. Fănică Gavril. The intersection graphs of subtrees in trees are exactly the chordal graphs. J. Combinatorial Theory Ser. B, 16:47-56, 1974. Google Scholar
  9. Jisu Jeong, Sigve Hortemo Sæther, and Jan Arne Telle. An FPT algorithm computing a decomposition of optimal mm-width. in preparation, 2015. Google Scholar
  10. Dénes König. Gráfok és mátrixok. Matematikai és Fizikai Lapok, 38:116-119, 1931. Google Scholar
  11. François Le Gall. Powers of tensors and fast matrix multiplication. In ISSAC 2014 - Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, pages 296-303. ACM, New York, 2014. Google Scholar
  12. Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Known algorithms on graphs of bounded treewidth are probably optimal. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, pages 777-789. SIAM, Philadelphia, PA, 2011. Google Scholar
  13. Sang-il Oum and Paul Seymour. Approximating clique-width and branch-width. J. Combin. Theory Ser. B, 96(4):514-528, 2006. Google Scholar
  14. Christophe Paul and Jan Arne Telle. Edge-maximal graphs of branchwidth k: the k-branches. Discrete Math., 309(6):1467-1475, 2009. Google Scholar
  15. Neil Robertson and P. D. Seymour. Graph minors. X. Obstructions to tree-decomposition. J. Combin. Theory Ser. B, 52(2):153-190, 1991. Google Scholar
  16. Sigve Hortemo Sæther and Jan Arne Telle. Between treewidth and clique-width. In Graph-theoretic concepts in computer science, volume 8747 of Lecture Notes in Comput. Sci., pages 396-407. Springer, Cham, 2014. Google Scholar
  17. Johan M. M. van Rooij, Hans L. Bodlaender, and Peter Rossmanith. Dynamic programming on tree decompositions using generalised fast subset convolution. In Algorithms - ESA 2009, volume 5757 of Lecture Notes in Comput. Sci., pages 566-577. Springer, Berlin, 2009. Google Scholar
  18. Martin Vatshelle. New Width Parameters of Graphs. PhD thesis, University of Bergen, 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact