Maximum matching width: New characterizations and a fast algorithm for dominating set

We use these representations to compare mm-width with treewidth and branchwidth, and also to give another new characterization of mm-width, by subgraphs of chordal graphs. We prove that given a graph G and a branch decomposition of maximum matching width k we can solve the Minimum Dominating Set Problem in time O∗(8k), thereby beating O∗(3tw(G)) whenever tw(G)>log38×k≈1.893k. Note that mmw(G)≤tw(G)+1≤3mmw(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 Minimum Dominating Set whenever tw(G)>1.549×mmw(G).