# zbMATH — the first resource for mathematics

Maximum matching width: new characterizations and a fast algorithm for dominating set. (English) Zbl 1395.05116
Summary: 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^\ast(8^k)$$, thereby beating $$O^\ast(3^{\mathrm{tw}(G)})$$ whenever $$\mathrm{tw}(G) > \log_3 8 \times k \approx 1.893 k$$. Note that $$\mathrm{mmw}(G) \leq \mathrm{tw}(G) + 1 \leq 3 \mathrm{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 $$\mathrm{tw}(G) > 1.549 \times \mathrm{mmw}(G)$$.
##### MSC:
 05C62 Graph representations (geometric and intersection representations, etc.) 05C85 Graph algorithms (graph-theoretic aspects) 05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) 68Q25 Analysis of algorithms and problem complexity
Full Text:
##### References:
  Amir, E., Approximation algorithms for treewidth, Algorithmica, 56, 4, 448-479, (2010) · Zbl 1187.68703  S. Arnborg, A. Proskurowski, Characterization and recognition of partial $$k$$-trees, in: Proceedings of the Sixteenth Southeastern International Conference on Combinatorics, Graph Theory and Computing, Boca Raton, Fla., 1985, vol. 47, 1985, pp. 69-75. · Zbl 0622.05017  Björklund, A.; Husfeldt, T.; Kaski, P.; Koivisto, M., Fourier meets Möbius: fast subset convolution, (STOC’07—PRoceedings of the 39th Annual ACM Symposium on Theory of Computing, (2007), ACM, New York), 67-74 · Zbl 1232.68188  Bodlaender, H. L.; Drange, P. G.; Dregi, M. S.; Fomin, F. V.; Lokshtanov, D.; Pilipczuk, M., An $$O(c^k n)$$ 5-approximation algorithm for treewidth, (Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on, (2013), IEEE), 499-508  Bodlaender, H. L.; van Leeuwen, E. J.; van Rooij, J. M.M.; Vatshelle, M., Faster algorithms on branch and clique decompositions, (Mathematical Foundations of Computer Science 2010, Lecture Notes in Comput. Sci., vol. 6281, (2010), Springer, Berlin), 174-185 · Zbl 1287.05147  Cygan, M.; Fomin, F. V.; Kowalik, Ł.; Lokshtanov, D.; Marx, D.; Pilipczuk, M.; Pilipczuk, M.; Saurabh, S., Parameterized Algorithms, 620, (2016), Springer International Publishing New York  Diestel, R., (Graph Theory, Graduate Texts in Mathematics, vol. 173, (2010), Springer Heidelberg), xviii+437 · Zbl 1204.05001  Gavril, F., The intersection graphs of subtrees in trees are exactly the chordal graphs, J. Combin. Theory Ser. B, 16, 47-56, (1974) · Zbl 0266.05101  Hopcroft, J. E.; Karp, R. M., An $$n^{5 / 2}$$ algorithm for maximum matchings in bipartite graphs, SIAM J. Comput., 2, 4, 225-231, (1973) · Zbl 0266.05114  Jeong, J.; Ok, S.; Suh, G., Characterizing graphs of maximum matching width at most $$2$$, Discrete Appl. Math., (2017), accepted. http://dx.doi.org/10.1016/j.dam.2017.07.028  König, D., Gráfok és mátrixok, Mat. Fizikai Lapok, 38, 116-119, (1931)  Le Gall, F., Powers of tensors and fast matrix multiplication, (ISSAC 2014—PRoceedings of the 39th International Symposium on Symbolic and Algebraic Computation, (2014), ACM, New York), 296-303 · Zbl 1325.65061  Lokshtanov, D.; Marx, D.; Saurabh, S., Known algorithms on graphs of bounded treewidth are probably optimal, (Proceedings of the Twenty-SEcond Annual ACM-SIAM Symposium on Discrete Algorithms, (2011), SIAM Philadelphia, PA), 777-789 · Zbl 1373.68242  Nordstrand, J., Exploring Graph Parameters Similar to Tree-Width and Path-Width, (2017), University of Bergen, (Master thesis)  Oum, S.; Seymour, P., Approximating clique-width and branch-width, J. Combin. Theory Ser. B, 96, 4, 514-528, (2006) · Zbl 1114.05022  Paul, C.; Telle, J. A., Edge-maximal graphs of branchwidth $$k$$: the $$k$$-branches, Discrete Math., 309, 6, 1467-1475, (2009) · Zbl 1229.05153  Robertson, N.; Seymour, P., Graph minors. XX. wagner’s conjecture, J. Combin. Theory Ser. B, 92, 2, 325-357, (2004), Special Issue Dedicated to Professor W.T. Tutte · Zbl 1061.05088  Robertson, N.; Seymour, P. D., Graph minors. X. obstructions to tree-decomposition, J. Combin. Theory Ser. B, 52, 2, 153-190, (1991) · Zbl 0764.05069  Rose, D. J., On simple characterizations of $$k$$-trees, Discrete Math., 7, 317-322, (1974) · Zbl 0285.05128  Sæther, S. H.; Telle, J. A., Between treewidth and clique-width, (Graph-Theoretic Concepts in Computer Science, Lecture Notes in Comput. Sci., vol. 8747, (2014), Springer, Cham), 396-407 · Zbl 1409.05201  van Rooij, J. M.M.; Bodlaender, H. L.; Rossmanith, P., Dynamic programming on tree decompositions using generalised fast subset convolution, (Algorithms—ESA 2009, Lecture Notes in Comput. Sci., vol. 5757, (2009), Springer, Berlin), 566-577 · Zbl 1256.68157  Vatshelle, M., New Width Parameters of Graphs, (2012), University of Bergen, (Ph.D. thesis)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.