The use of a pruned modular decomposition for maximum matching algorithms on some graph classes

Guillaume Ducoffe, Alexandru Popa

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

3 Citations (Scopus)

Abstract

We address the following general question: given a graph class C on which we can solve Maximum Matching in (quasi) linear time, does the same hold true for the class of graphs that can be modularly decomposed into C? As a way to answer this question for distance-hereditary graphs and some other superclasses of cographs, we study the combined effect of modular decomposition with a pruning process over the quotient subgraphs. We remove sequentially from all such subgraphs their so-called one-vertex extensions (i.e., pendant, anti-pendant, twin, universal and isolated vertices). Doing so, we obtain a “pruned modular decomposition”, that can be computed in quasi linear time. Our main result is that if all the pruned quotient subgraphs have bounded order then a maximum matching can be computed in linear time. The latter result strictly extends a recent framework in (Coudert et al., SODA'18). Our work is the first to explain why the existence of some nice ordering over the modules of a graph, instead of just over its vertices, can help to speed up the computation of maximum matchings on some graph classes.

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

Decomposition

Keywords

  • FPT in P
  • Maximum matching
  • Modular decomposition
  • One-vertex extensions
  • P -structure
  • Pruned graphs

ASJC Scopus subject areas

  • Software

Cite this

Ducoffe, G., & Popa, A. (2018). The use of a pruned modular decomposition for maximum matching algorithms on some graph classes. 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.6

The use of a pruned modular decomposition for maximum matching algorithms on some graph classes. / 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 use of a pruned modular decomposition for maximum matching algorithms on some graph classes. 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.6
Ducoffe G, Popa A. The use of a pruned modular decomposition for maximum matching algorithms on some graph classes. 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.6
Ducoffe, Guillaume ; Popa, Alexandru. / The use of a pruned modular decomposition for maximum matching algorithms on some graph classes. 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{73911afd22c043f0bdea55c109383285,
title = "The use of a pruned modular decomposition for maximum matching algorithms on some graph classes",
abstract = "We address the following general question: given a graph class C on which we can solve Maximum Matching in (quasi) linear time, does the same hold true for the class of graphs that can be modularly decomposed into C? As a way to answer this question for distance-hereditary graphs and some other superclasses of cographs, we study the combined effect of modular decomposition with a pruning process over the quotient subgraphs. We remove sequentially from all such subgraphs their so-called one-vertex extensions (i.e., pendant, anti-pendant, twin, universal and isolated vertices). Doing so, we obtain a “pruned modular decomposition”, that can be computed in quasi linear time. Our main result is that if all the pruned quotient subgraphs have bounded order then a maximum matching can be computed in linear time. The latter result strictly extends a recent framework in (Coudert et al., SODA'18). Our work is the first to explain why the existence of some nice ordering over the modules of a graph, instead of just over its vertices, can help to speed up the computation of maximum matchings on some graph classes.",
keywords = "FPT in P, Maximum matching, Modular decomposition, One-vertex extensions, P -structure, Pruned graphs",
author = "Guillaume Ducoffe and Alexandru Popa",
year = "2018",
month = "12",
day = "1",
doi = "10.4230/LIPIcs.ISAAC.2018.6",
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 use of a pruned modular decomposition for maximum matching algorithms on some graph classes

AU - Ducoffe, Guillaume

AU - Popa, Alexandru

PY - 2018/12/1

Y1 - 2018/12/1

N2 - We address the following general question: given a graph class C on which we can solve Maximum Matching in (quasi) linear time, does the same hold true for the class of graphs that can be modularly decomposed into C? As a way to answer this question for distance-hereditary graphs and some other superclasses of cographs, we study the combined effect of modular decomposition with a pruning process over the quotient subgraphs. We remove sequentially from all such subgraphs their so-called one-vertex extensions (i.e., pendant, anti-pendant, twin, universal and isolated vertices). Doing so, we obtain a “pruned modular decomposition”, that can be computed in quasi linear time. Our main result is that if all the pruned quotient subgraphs have bounded order then a maximum matching can be computed in linear time. The latter result strictly extends a recent framework in (Coudert et al., SODA'18). Our work is the first to explain why the existence of some nice ordering over the modules of a graph, instead of just over its vertices, can help to speed up the computation of maximum matchings on some graph classes.

AB - We address the following general question: given a graph class C on which we can solve Maximum Matching in (quasi) linear time, does the same hold true for the class of graphs that can be modularly decomposed into C? As a way to answer this question for distance-hereditary graphs and some other superclasses of cographs, we study the combined effect of modular decomposition with a pruning process over the quotient subgraphs. We remove sequentially from all such subgraphs their so-called one-vertex extensions (i.e., pendant, anti-pendant, twin, universal and isolated vertices). Doing so, we obtain a “pruned modular decomposition”, that can be computed in quasi linear time. Our main result is that if all the pruned quotient subgraphs have bounded order then a maximum matching can be computed in linear time. The latter result strictly extends a recent framework in (Coudert et al., SODA'18). Our work is the first to explain why the existence of some nice ordering over the modules of a graph, instead of just over its vertices, can help to speed up the computation of maximum matchings on some graph classes.

KW - FPT in P

KW - Maximum matching

KW - Modular decomposition

KW - One-vertex extensions

KW - P -structure

KW - Pruned graphs

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

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

U2 - 10.4230/LIPIcs.ISAAC.2018.6

DO - 10.4230/LIPIcs.ISAAC.2018.6

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 -