2026-07-20T06:35:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5584 2024-03-06T10:36:36Z ddc:004 open_access

Maximum Matching Width: New Characterizations and a Fast Algorithm for Dominating Set Jeong, Jisu Sæther, Sigve Hortemo Telle, Jan Arne FPT algorithms treewidth dominating set 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jisu Jeong and Sigve Hortemo Sæther and Jan Arne Telle 2015 Is Part Of LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2015.212 urn:nbn:de:0030-drops-55846 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.212 eng https://creativecommons.org/licenses/by/3.0/legalcode