TY - GEN
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:
Funding This work was supported by the Institutional research programme PN 1819 “Advanced IT resources to support digital transformation processes in the economy and society - RESINFO-TD” (2018), project PN 1819-01-01 “Modeling, simulation, optimization of complex systems and decision support in new areas of IT&C research”, funded by the Ministry of Research and Innovation, Romania.
Funding Information:
This work was supported by the Institutional research programme PN 1819 “Advanced IT resources to support digital transformation processes in the economy and society - RESINFO-TD” (2018), project PN 1819-01-01 “Modeling, simulation, optimization of complex systems and decision support in new areas of IT&C research”, funded by the Ministry of Research and Innovation, Romania.
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
SP - 6:1-6:13
BT - 29th International Symposium on Algorithms and Computation, ISAAC 2018
A2 - Liao, Chung-Shou
A2 - Lee, Der-Tsai
A2 - Hsu, Wen-Lian
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 29th International Symposium on Algorithms and Computation, ISAAC 2018
Y2 - 16 December 2018 through 19 December 2018
ER -