Ducoffe, Guillaume ;
Popa, Alexandru
The Use of a Pruned Modular Decomposition for Maximum Matching Algorithms on Some Graph Classes
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 distancehereditary 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 socalled onevertex extensions (i.e., pendant, antipendant, 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.
BibTeX  Entry
@InProceedings{ducoffe_et_al:LIPIcs:2018:9954,
author = {Guillaume Ducoffe and Alexandru Popa},
title = {{The Use of a Pruned Modular Decomposition for Maximum Matching Algorithms on Some Graph Classes}},
booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)},
pages = {6:16:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770941},
ISSN = {18688969},
year = {2018},
volume = {123},
editor = {WenLian Hsu and DerTsai Lee and ChungShou Liao},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9954},
URN = {urn:nbn:de:0030drops99549},
doi = {10.4230/LIPIcs.ISAAC.2018.6},
annote = {Keywords: maximum matching, FPT in P, modular decomposition, pruned graphs, onevertex extensions, P_4structure}
}
06.12.2018
Keywords: 

maximum matching, FPT in P, modular decomposition, pruned graphs, onevertex extensions, P_4structure 
Seminar: 

29th International Symposium on Algorithms and Computation (ISAAC 2018)

Issue date: 

2018 
Date of publication: 

06.12.2018 