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