TY - JOUR

T1 - The use of a pruned modular decomposition for MAXIMUM MATCHING algorithms on some graph classes

AU - Ducoffe, Guillaume

AU - Popa, Alexandru

N1 - Funding Information:
We wish to thank the anonymous referees for their careful reading of the first version of this manuscript, and their useful comments. The article has enjoyed the support of the Romanian Young Academy , Stiftung Mercator and the Alexander von Humboldt Foundation .

PY - 2021/3/11

Y1 - 2021/3/11

N2 - Consider the following general question: if we can solve MAXIMUM MATCHING in (quasi) linear time on a graph class C, does the same hold true for the class of graphs that can be modularly decomposed into C ? What makes the latter question difficult is that the MAXIMUM MATCHING problem is not preserved by quotient, thereby making difficult to exploit the structural properties of the quotient subgraphs of the modular decomposition. So far, we are only aware of a recent framework in (Coudert et al., SODA’18) that only applies when the quotient subgraphs have bounded order and/or under additional assumptions on the nontrivial modules in the graph. As an attempt 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. Specifically, 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 the framework of Coudert et al. Our work is the first to use some ordering over the modules of a graph, instead of just over its vertices, in order to speed up the computation of maximum matchings on some graph classes.

AB - Consider the following general question: if we can solve MAXIMUM MATCHING in (quasi) linear time on a graph class C, does the same hold true for the class of graphs that can be modularly decomposed into C ? What makes the latter question difficult is that the MAXIMUM MATCHING problem is not preserved by quotient, thereby making difficult to exploit the structural properties of the quotient subgraphs of the modular decomposition. So far, we are only aware of a recent framework in (Coudert et al., SODA’18) that only applies when the quotient subgraphs have bounded order and/or under additional assumptions on the nontrivial modules in the graph. As an attempt 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. Specifically, 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 the framework of Coudert et al. Our work is the first to use some ordering over the modules of a graph, instead of just over its vertices, in order 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=85098121008&partnerID=8YFLogxK

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

U2 - 10.1016/j.dam.2020.12.018

DO - 10.1016/j.dam.2020.12.018

M3 - Article

AN - SCOPUS:85098121008

VL - 291

SP - 201

EP - 222

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

ER -