License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2018.30
URN: urn:nbn:de:0030-drops-99783
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9978/
Go to the corresponding LIPIcs Volume Portal

Ducoffe, Guillaume ; Popa, Alexandru

The b-Matching Problem in Distance-Hereditary Graphs and Beyond

pdf-format:
LIPIcs-ISAAC-2018-30.pdf (0.5 MB)

Abstract

We make progress on the fine-grained complexity of Maximum-Cardinality Matching on graphs of bounded clique-width. Quasi linear-time algorithms for this problem have been recently 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 are 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 improve the state of the art (Dragan, WG'97) and 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.

BibTeX - Entry

@InProceedings{ducoffe_et_al:LIPIcs:2018:9978,
  author =	{Guillaume Ducoffe and Alexandru Popa},
  title =	{{The b-Matching Problem in Distance-Hereditary Graphs and Beyond}},
  booktitle =	{29th International Symposium on Algorithms and Computation  (ISAAC 2018)},
  pages =	{30:1--30:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Wen-Lian Hsu and Der-Tsai Lee and Chung-Shou Liao},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9978},
  URN =		{urn:nbn:de:0030-drops-99783},
  doi =		{10.4230/LIPIcs.ISAAC.2018.30},
  annote =	{Keywords: maximum-cardinality matching, b-matching, FPT in P, split decomposition, distance-hereditary graphs}
}

Keywords: maximum-cardinality matching, b-matching, FPT in P, split decomposition, distance-hereditary graphs
Collection: 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Issue Date: 2018
Date of publication: 06.12.2018

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