Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2015.212
URN: urn:nbn:de:0030-drops-55846
URL: https://drops.dagstuhl.de/opus/volltexte/2015/5584/
Jeong, Jisu ; Sæther, Sigve Hortemo ; Telle, Jan Arne
Maximum Matching Width: New Characterizations and a Fast Algorithm for Dominating Set
| pdf-format: |
|
Abstract
We give alternative definitions for maximum matching width, e.g., a graph G has mmw(G) <= 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| <= 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^{tw(G)}) whenever tw(G) > log_3(8) * k ~ 1.893 k. 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 solving Dominating Set whenever tw(G) > 1.549 * mmw(G).
BibTeX - Entry
@InProceedings{jeong_et_al:LIPIcs:2015:5584,
author = {Jisu Jeong and Sigve Hortemo Sæther and Jan Arne Telle},
title = {{Maximum Matching Width: New Characterizations and a Fast Algorithm for Dominating Set}},
booktitle = {10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
pages = {212--223},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-92-7},
ISSN = {1868-8969},
year = {2015},
volume = {43},
editor = {Thore Husfeldt and Iyad Kanj},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5584},
URN = {urn:nbn:de:0030-drops-55846},
doi = {10.4230/LIPIcs.IPEC.2015.212},
annote = {Keywords: FPT algorithms, treewidth, dominating set}
}
| Keywords: | FPT algorithms, treewidth, dominating set | |
| Seminar: | 10th International Symposium on Parameterized and Exact Computation (IPEC 2015) | |
| Issue date: | 2015 | |
| Date of publication: | 19.11.2015 |
