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 language | English |
|---|---|
| Title of host publication | 29th International Symposium on Algorithms and Computation, ISAAC 2018 |
| Editors | Der-Tsai Lee, Chung-Shou Liao, Wen-Lian Hsu |
| Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
| ISBN (Electronic) | 9783959770941 |
| DOIs | |
| Publication status | Published - Dec 1 2018 |
| Event | 29th International Symposium on Algorithms and Computation, ISAAC 2018 - Jiaoxi, Yilan, Taiwan Duration: Dec 16 2018 → Dec 19 2018 |
Publication series
| Name | Leibniz International Proceedings in Informatics, LIPIcs |
|---|---|
| Volume | 123 |
| ISSN (Print) | 1868-8969 |
Conference
| Conference | 29th International Symposium on Algorithms and Computation, ISAAC 2018 |
|---|---|
| Country | Taiwan |
| City | Jiaoxi, Yilan |
| Period | 12/16/18 → 12/19/18 |
Fingerprint
Keywords
- FPT in P
- Maximum matching
- Modular decomposition
- One-vertex extensions
- P -structure
- Pruned graphs
ASJC Scopus subject areas
- Software
Cite this
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 proceeding › Conference contribution
}
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
AN - SCOPUS:85063667696
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 -