×

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
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Amir, E., Approximation algorithms for treewidth, Algorithmica, 56, 4, 448-479, (2010) · Zbl 1187.68703
[2] 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
[3] 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
[4] 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
[5] 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
[6] 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
[7] Diestel, R., (Graph Theory, Graduate Texts in Mathematics, vol. 173, (2010), Springer Heidelberg), xviii+437 · Zbl 1204.05001
[8] 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
[9] 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
[10] 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
[11] König, D., Gráfok és mátrixok, Mat. Fizikai Lapok, 38, 116-119, (1931)
[12] 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
[13] 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
[14] Nordstrand, J., Exploring Graph Parameters Similar to Tree-Width and Path-Width, (2017), University of Bergen, (Master thesis)
[15] Oum, S.; Seymour, P., Approximating clique-width and branch-width, J. Combin. Theory Ser. B, 96, 4, 514-528, (2006) · Zbl 1114.05022
[16] Paul, C.; Telle, J. A., Edge-maximal graphs of branchwidth \(k\): the \(k\)-branches, Discrete Math., 309, 6, 1467-1475, (2009) · Zbl 1229.05153
[17] 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
[18] 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
[19] Rose, D. J., On simple characterizations of \(k\)-trees, Discrete Math., 7, 317-322, (1974) · Zbl 0285.05128
[20] 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
[21] 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
[22] 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.