### 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

*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.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

*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

}

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 -