The b-matching problem in distance-hereditary graphs and beyond

Guillaume Ducoffe, Alexandru Popa

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)

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((klog 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.

Original languageEnglish
Title of host publication29th International Symposium on Algorithms and Computation, ISAAC 2018
EditorsDer-Tsai Lee, Chung-Shou Liao, Wen-Lian Hsu
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770941
DOIs
Publication statusPublished - Dec 1 2018
Event29th International Symposium on Algorithms and Computation, ISAAC 2018 - Jiaoxi, Yilan, Taiwan
Duration: Dec 16 2018Dec 19 2018

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume123
ISSN (Print)1868-8969

Conference

Conference29th International Symposium on Algorithms and Computation, ISAAC 2018
CountryTaiwan
CityJiaoxi, Yilan
Period12/16/1812/19/18

Fingerprint

Dynamic programming
Decomposition
Costs

Keywords

  • B-matching
  • Distance-hereditary graphs
  • FPT in P
  • Maximum-cardinality matching
  • Split decomposition

ASJC Scopus subject areas

  • Software

Cite this

Ducoffe, G., & Popa, A. (2018). The b-matching problem in distance-hereditary graphs and beyond. In D-T. Lee, C-S. Liao, & W-L. Hsu (Eds.), 29th International Symposium on Algorithms and Computation, ISAAC 2018 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 123). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ISAAC.2018.30

The b-matching problem in distance-hereditary graphs and beyond. / Ducoffe, Guillaume; Popa, Alexandru.

29th International Symposium on Algorithms and Computation, ISAAC 2018. ed. / Der-Tsai Lee; Chung-Shou Liao; Wen-Lian Hsu. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2018. (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 123).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Ducoffe, G & Popa, A 2018, The b-matching problem in distance-hereditary graphs and beyond. in D-T Lee, C-S Liao & W-L Hsu (eds), 29th International Symposium on Algorithms and Computation, ISAAC 2018. Leibniz International Proceedings in Informatics, LIPIcs, vol. 123, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 29th International Symposium on Algorithms and Computation, ISAAC 2018, Jiaoxi, Yilan, Taiwan, 12/16/18. https://doi.org/10.4230/LIPIcs.ISAAC.2018.30
Ducoffe G, Popa A. The b-matching problem in distance-hereditary graphs and beyond. In Lee D-T, Liao C-S, Hsu W-L, editors, 29th International Symposium on Algorithms and Computation, ISAAC 2018. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2018. (Leibniz International Proceedings in Informatics, LIPIcs). https://doi.org/10.4230/LIPIcs.ISAAC.2018.30
Ducoffe, Guillaume ; Popa, Alexandru. / The b-matching problem in distance-hereditary graphs and beyond. 29th International Symposium on Algorithms and Computation, ISAAC 2018. editor / Der-Tsai Lee ; Chung-Shou Liao ; Wen-Lian Hsu. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2018. (Leibniz International Proceedings in Informatics, LIPIcs).
@inproceedings{dce20d67eced499d84c788c669678f9f,
title = "The b-matching problem in distance-hereditary graphs and beyond",
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((klog 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.",
keywords = "B-matching, Distance-hereditary graphs, FPT in P, Maximum-cardinality matching, Split decomposition",
author = "Guillaume Ducoffe and Alexandru Popa",
year = "2018",
month = "12",
day = "1",
doi = "10.4230/LIPIcs.ISAAC.2018.30",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Der-Tsai Lee and Chung-Shou Liao and Wen-Lian Hsu",
booktitle = "29th International Symposium on Algorithms and Computation, ISAAC 2018",
address = "Germany",

}

TY - GEN

T1 - The b-matching problem in distance-hereditary graphs and beyond

AU - Ducoffe, Guillaume

AU - Popa, Alexandru

PY - 2018/12/1

Y1 - 2018/12/1

N2 - 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((klog 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.

AB - 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((klog 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.

KW - B-matching

KW - Distance-hereditary graphs

KW - FPT in P

KW - Maximum-cardinality matching

KW - Split decomposition

UR - http://www.scopus.com/inward/record.url?scp=85063666747&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85063666747&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ISAAC.2018.30

DO - 10.4230/LIPIcs.ISAAC.2018.30

M3 - Conference contribution

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 29th International Symposium on Algorithms and Computation, ISAAC 2018

A2 - Lee, Der-Tsai

A2 - Liao, Chung-Shou

A2 - Hsu, Wen-Lian

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

ER -