License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2021.15
URN: urn:nbn:de:0030-drops-153987
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15398/
Go to the corresponding LIPIcs Volume Portal


Ducoffe, Guillaume

Maximum Matching in Almost Linear Time on Graphs of Bounded Clique-Width

pdf-format:
LIPIcs-IPEC-2021-15.pdf (0.8 MB)


Abstract

Recently, independent groups of researchers have presented algorithms to compute a maximum matching in Õ(f(k) ⋅ (n+m)) time, for some computable function f, within the graphs where some clique-width upper bound is at most k (e.g., tree-width, modular-width and P₄-sparseness). However, to the best of our knowledge, the existence of such algorithm within the graphs of bounded clique-width has remained open until this paper. Indeed, we cannot even apply Courcelle’s theorem to this problem directly, because a matching cannot be expressed in MSO₁ logic.
Our first contribution is an almost linear-time algorithm to compute a maximum matching in any bounded clique-width graph, being given a corresponding clique-width expression. It can be used to also compute the Edmonds-Gallai decomposition. For that, we do apply Courcelle’s theorem, but in order to compute the cardinality of a maximum matching rather than the matching itself, via the classic Tutte-Berge formula. To obtain with this approach a maximum matching, we need to combine it with a recursive dissection scheme for bounded clique-width graphs based on the existence of balanced edge-cuts with bounded neighbourhood diversity, and with a distributed version of Courcelle’s theorem (Courcelle and Vanicat, DAM 2016) - of which we present here a slightly stronger version than the standard one in the literature - in order to evaluate the Tutte-Berge formula on various subgraphs of the input.
Finally, for the bipartite graphs of clique-width at most k, we present an alternative Õ(k²⋅(n+m))-time algorithm for the problem. The algorithm is randomized and it is based on a completely different approach than above: combining various reductions to matching and flow problems on bounded tree-width graphs with a very recent result on the parameterized complexity of linear programming (Dong et. al., STOC'21). Our results for bounded clique-width graphs extend many prior works on the complexity of Maximum Matching within cographs, distance-hereditary graphs, series-parallel graphs and other subclasses.

BibTeX - Entry

@InProceedings{ducoffe:LIPIcs.IPEC.2021.15,
  author =	{Ducoffe, Guillaume},
  title =	{{Maximum Matching in Almost Linear Time on Graphs of Bounded Clique-Width}},
  booktitle =	{16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
  pages =	{15:1--15:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-216-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{214},
  editor =	{Golovach, Petr A. and Zehavi, Meirav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/15398},
  URN =		{urn:nbn:de:0030-drops-153987},
  doi =		{10.4230/LIPIcs.IPEC.2021.15},
  annote =	{Keywords: Maximum Matching, Maximum b-matching, Clique-width, Tree-width, Courcelle’s theorem, FPT in P}
}

Keywords: Maximum Matching, Maximum b-matching, Clique-width, Tree-width, Courcelle’s theorem, FPT in P
Collection: 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)
Issue Date: 2021
Date of publication: 22.11.2021


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI