Maximum matching width: new characterizations and a fast algorithm for dominating set
From MaRDI portal
Publication:5363776
DOI10.4230/LIPICS.IPEC.2015.212zbMath1378.68082arXiv1507.02384OpenAlexW2770155412MaRDI QIDQ5363776
Jisu Jeong, Jan Arne Telle, Sigve Hortemo Sæther
Publication date: 29 September 2017
Abstract: We give alternative definitions for maximum matching width, e.g. a graph $G$ has $operatorname{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^{operatorname{tw}(G)})$ whenever $operatorname{tw}(G) > log_3{8} imes k approx 1.893 k$. Note that $operatorname{mmw}(G) leq operatorname{tw}(G)+1 leq 3 operatorname{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 $operatorname{tw}(G) > 1.549 imes operatorname{mmw}(G)$.
Full work available at URL: https://arxiv.org/abs/1507.02384
Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (2)
Characterizing graphs of maximum matching width at most 2 ⋮ Computing partial hypergraphs of bounded width
This page was built for publication: Maximum matching width: new characterizations and a fast algorithm for dominating set
