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 cliquewidth upper bound is at most k (e.g., treewidth, modularwidth and P₄sparseness). However, to the best of our knowledge, the existence of such algorithm within the graphs of bounded cliquewidth 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 lineartime algorithm to compute a maximum matching in any bounded cliquewidth graph, being given a corresponding cliquewidth expression. It can be used to also compute the EdmondsGallai 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 TutteBerge formula. To obtain with this approach a maximum matching, we need to combine it with a recursive dissection scheme for bounded cliquewidth graphs based on the existence of balanced edgecuts 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 TutteBerge formula on various subgraphs of the input.
Finally, for the bipartite graphs of cliquewidth 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 treewidth graphs with a very recent result on the parameterized complexity of linear programming (Dong et. al., STOC'21). Our results for bounded cliquewidth graphs extend many prior works on the complexity of Maximum Matching within cographs, distancehereditary graphs, seriesparallel 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 CliqueWidth}},
booktitle = {16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
pages = {15:115:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772167},
ISSN = {18688969},
year = {2021},
volume = {214},
editor = {Golovach, Petr A. and Zehavi, Meirav},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/15398},
URN = {urn:nbn:de:0030drops153987},
doi = {10.4230/LIPIcs.IPEC.2021.15},
annote = {Keywords: Maximum Matching, Maximum bmatching, Cliquewidth, Treewidth, Courcelle’s theorem, FPT in P}
}
Keywords: 

Maximum Matching, Maximum bmatching, Cliquewidth, Treewidth, 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 