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].

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)
Full Text: DOI arXiv