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.ESA.2018.55
URN: urn:nbn:de:0030-drops-95187
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9518/
Go to the corresponding LIPIcs Volume Portal

Kratsch, Stefan ; Nelles, Florian

Efficient and Adaptive Parameterized Algorithms on Modular Decompositions

pdf-format:
LIPIcs-ESA-2018-55.pdf (0.5 MB)

Abstract

We study the influence of a graph parameter called modular-width on the time complexity for optimally solving well-known polynomial problems such as Maximum Matching, Triangle Counting, and Maximum s-t Vertex-Capacitated Flow. The modular-width of a graph depends on its (unique) modular decomposition tree, and can be computed in linear time O(n+m) for graphs with n vertices and m edges. Modular decompositions are an important tool for graph algorithms, e.g., for linear-time recognition of certain graph classes.
Throughout, we obtain efficient parameterized algorithms of running times O(f(mw)n+m), O(n+f(mw)m) , or O(f(mw)+n+m) for low polynomial functions f and graphs of modular-width mw. Our algorithm for Maximum Matching, running in time O(mw^2 log mw n+m), is both faster and simpler than the recent O(mw^4n+m) time algorithm of Coudert et al. (SODA 2018). For several other problems, e.g., Triangle Counting and Maximum b-Matching, we give adaptive algorithms, meaning that their running times match the best unparameterized algorithms for worst-case modular-width of mw=Theta(n) and they outperform them already for mw=o(n), until reaching linear time for mw=O(1).

BibTeX - Entry

@InProceedings{kratsch_et_al:LIPIcs:2018:9518,
  author =	{Stefan Kratsch and Florian Nelles},
  title =	{{Efficient and Adaptive Parameterized Algorithms on Modular Decompositions}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{55:1--55:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Yossi Azar and Hannah Bast and Grzegorz Herman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9518},
  URN =		{urn:nbn:de:0030-drops-95187},
  doi =		{10.4230/LIPIcs.ESA.2018.55},
  annote =	{Keywords: efficient parameterized algorithms, modular-width, adaptive algorithms}
}

Keywords: efficient parameterized algorithms, modular-width, adaptive algorithms
Collection: 26th Annual European Symposium on Algorithms (ESA 2018)
Issue Date: 2018
Date of publication: 14.08.2018

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