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.IPEC.2018.9
URN: urn:nbn:de:0030-drops-102103
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10210/
Go to the corresponding LIPIcs Volume Portal

Meeks, Kitty ; Skerman, Fiona

The Parameterised Complexity of Computing the Maximum Modularity of a Graph

pdf-format:
LIPIcs-IPEC-2018-9.pdf (0.5 MB)

Abstract

The maximum modularity of a graph is a parameter widely used to describe the level of clustering or community structure in a network. Determining the maximum modularity of a graph is known to be NP-complete in general, and in practice a range of heuristics are used to construct partitions of the vertex-set which give lower bounds on the maximum modularity but without any guarantee on how close these bounds are to the true maximum. In this paper we investigate the parameterised complexity of determining the maximum modularity with respect to various standard structural parameterisations of the input graph G. We show that the problem belongs to FPT when parameterised by the size of a minimum vertex cover for G, and is solvable in polynomial time whenever the treewidth or max leaf number of G is bounded by some fixed constant; we also obtain an FPT algorithm, parameterised by treewidth, to compute any constant-factor approximation to the maximum modularity. On the other hand we show that the problem is W[1]-hard (and hence unlikely to admit an FPT algorithm) when parameterised simultaneously by pathwidth and the size of a minimum feedback vertex set.

BibTeX - Entry

@InProceedings{meeks_et_al:LIPIcs:2019:10210,
  author =	{Kitty Meeks and Fiona Skerman},
  title =	{{The Parameterised Complexity of Computing the Maximum Modularity of a Graph}},
  booktitle =	{13th International Symposium on Parameterized and Exact  Computation (IPEC 2018)},
  pages =	{9:1--9:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-084-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{115},
  editor =	{Christophe Paul and Michal Pilipczuk},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10210},
  URN =		{urn:nbn:de:0030-drops-102103},
  doi =		{10.4230/LIPIcs.IPEC.2018.9},
  annote =	{Keywords: modularity, community detection, integer quadratic programming, vertex cover, pathwidth}
}

Keywords: modularity, community detection, integer quadratic programming, vertex cover, pathwidth
Collection: 13th International Symposium on Parameterized and Exact Computation (IPEC 2018)
Issue Date: 2019
Date of publication: 05.02.2019

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