# zbMATH — the first resource for mathematics

Maximum matching width: new characterizations and a fast algorithm for dominating set. (English) Zbl 1378.68082
Husfeldt, Thore (ed.) et al., 10th international symposium on parameterized and exact computation, IPEC 2015, Patras, Greece, September 16–18, 2015. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-92-7). LIPIcs – Leibniz International Proceedings in Informatics 43, 212-223 (2015).
Summary: We give alternative definitions for maximum matching width, e.g., a graph $$G$$ has $$\text{mmw}(G)\leq 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|\leq 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^{\text{tw}(G)})$$ whenever $$\text{tw}(G)>\log_38\times k\approx 1.893k$$. Note that $$\text{mmw}(G)\leq\text{tw}(G)+1\leq 3\text{\,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 $$\text{tw}(G)>1.549\times\text{mmw}(G)$$.
For the entire collection see [Zbl 1338.68007].

##### MSC:
 68Q25 Analysis of algorithms and problem complexity 05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) 05C85 Graph algorithms (graph-theoretic aspects)
##### Keywords:
FPT algorithms; treewidth; dominating set
Full Text: