License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2018.6
URN: urn:nbn:de:0030-drops-99549
URL: https://drops.dagstuhl.de/opus/volltexte/2018/9954/
Go to the corresponding LIPIcs Volume Portal

Ducoffe, Guillaume ; Popa, Alexandru

The Use of a Pruned Modular Decomposition for Maximum Matching Algorithms on Some Graph Classes

pdf-format:
LIPIcs-ISAAC-2018-6.pdf (0.5 MB)

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.

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:1--6:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Wen-Lian Hsu and Der-Tsai Lee and Chung-Shou Liao},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9954},
  URN =		{urn:nbn:de:0030-drops-99549},
  doi =		{10.4230/LIPIcs.ISAAC.2018.6},
  annote =	{Keywords: maximum matching, FPT in P, modular decomposition, pruned graphs, one-vertex extensions, P_4-structure}
}

Keywords: maximum matching, FPT in P, modular decomposition, pruned graphs, one-vertex extensions, P_4-structure
Collection: 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Issue Date: 2018
Date of publication: 06.12.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI