DROPS

Document

DOI: 10.4230/LIPIcs.SWAT.2022.13

Dense Graph Partitioning on Sparse and Dense Graphs

Authors: Cristina Bazgan, Katrin Casel, and Pierre Cazals

Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)

Abstract

We consider the problem of partitioning a graph into a non-fixed number of non-overlapping subgraphs of maximum density. The density of a partition is the sum of the densities of the subgraphs, where the density of a subgraph is half its average degree, that is, the ratio of its number of edges and its number of vertices. This problem, called Dense Graph Partition, is known to be NP-hard on general graphs and polynomial-time solvable on trees, and polynomial-time 2-approximable. In this paper we study the restriction of Dense Graph Partition to particular sparse and dense graph classes. In particular, we prove that it is NP-hard on dense bipartite graphs as well as on cubic graphs. On dense graphs on n vertices, it is polynomial-time solvable on graphs with minimum degree n-3 and NP-hard on (n-4)-regular graphs. We prove that it is polynomial-time 4/3-approximable on cubic graphs and admits an efficient polynomial-time approximation scheme on graphs of minimum degree n-t for any constant t ≥ 4.

Cite as

Cristina Bazgan, Katrin Casel, and Pierre Cazals. Dense Graph Partitioning on Sparse and Dense Graphs. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 13:1-13:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bazgan_et_al:LIPIcs.SWAT.2022.13,
  author =	{Bazgan, Cristina and Casel, Katrin and Cazals, Pierre},
  title =	{{Dense Graph Partitioning on Sparse and Dense Graphs}},
  booktitle =	{18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
  pages =	{13:1--13:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-236-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{227},
  editor =	{Czumaj, Artur and Xin, Qin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.13},
  URN =		{urn:nbn:de:0030-drops-161732},
  doi =		{10.4230/LIPIcs.SWAT.2022.13},
  annote =	{Keywords: NP-hardness, approximation, density, graph partitioning, bipartite graphs, cubic graphs, dense graphs}
}

Search Results

Documents authored by Cazals, Pierre

Dense Graph Partitioning on Sparse and Dense Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message