2026-08-12T06:26:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9954 2024-03-06T10:45:11Z ddc:004 open_access

The Use of a Pruned Modular Decomposition for Maximum Matching Algorithms on Some Graph Classes Ducoffe, Guillaume Popa, Alexandru maximum matching FPT in P modular decomposition pruned graphs one-vertex extensions P_4-structure 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Guillaume Ducoffe and Alexandru Popa 2018 Is Part Of LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2018.6 urn:nbn:de:0030-drops-99549 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.6 eng https://creativecommons.org/licenses/by/3.0/legalcode