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

Abstract

A graph of treewidth k has a representation by subtrees of a ternary tree, with subtrees of adjacent vertices sharing a tree node, and any tree node sharing at most k + 1 subtrees. Likewise for branchwidth, but with a shift to the edges of the tree rather than the nodes. In this paper we show that the mm-width of a graph - maximum matching width - combines aspects of both these representations, targeting tree nodes for adjacency and tree edges for the parameter value. The proof of this new characterization of mm-width is based on a definition of canonical minimum vertex covers of bipartite graphs. We show that these behave in a monotone way along branch decompositions over the vertex set of a graph.

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*(8(k)), thereby beating O*(3(tw(G))) whenever tw(G) > log(3) 8 x k approximate to 1.893k. 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 Minimum Dominating Set whenever tw(G) > 1.549 x mmw(G). (C) 2017 Elsevier B.V. All rights reserved.