Paper Info
Title
The b-MATCHING problem in distance-hereditary graphs and beyond
Abstract
We make progress on the fine-grained complexity of MAXIMUM-CARDINALITY MATCHING within graphs of bounded clique-width. Quasi linear-time algorithms for this problem have been proposed for the important subclasses of bounded-treewidth graphs (Fomin et al., SODA'17) and graphs of bounded modular-width (Coudert et al., SODA'18). We present such algorithm for bounded split-width graphs - a broad generalization of graphs of bounded modular-width, of which an interesting subclass is the distance-hereditary graphs. Specifically, we solve MAXIMUM-CARDINALITY MATCHING in O((k log(2 )k) . (m + n) . log n)-time on graphs with split-width at most k. We stress that the existence of such algorithm was not even known for distance-hereditary graphs until our work. Doing so, we answer an open question of Coudert et al. (SODA'18). Our work brings more insights on the relationships between matchings and splits, a.k.a., join operations between two vertex-subsets in different connected components. Furthermore, our analysis can be extended to the more general (unit cost) b-MATCHING problem. On the way, we introduce new tools for b-MATCHING and dynamic programming over split decompositions, that can be of independent interest. (C) 2021 Elsevier B.V. All rights reserved.
Year
DOI
Venue
2021
10.1016/j.dam.2021.09.012
DISCRETE APPLIED MATHEMATICS
Keywords
DocType
Volume
Maximum-cardinality matching, b-MATCHING, FPT in P, Split decomposition, Distance-hereditary graphs
Journal
305
ISSN
Citations 
PageRank 
0166-218X
0
0.34
References 
Authors
0
2
Name
Order
Citations
PageRank
Guillaume Ducoffe13416.25
Alexandru Popa27013.34