Document Open Access Logo

Dense Graph Partitioning on Sparse and Dense Graphs

Authors Cristina Bazgan , Katrin Casel , Pierre Cazals

PDF
Thumbnail PDF

File

LIPIcs.SWAT.2022.13.pdf
  • Filesize: 0.79 MB
  • 15 pages

Document Identifiers

Author Details

Cristina Bazgan
  • Université Paris-Dauphine, PSL Research University, CNRS, UMR 7243, LAMSADE, 75016 Paris, France
Katrin Casel
  • Hasso Plattner Institut, Universität Potsdam, Germany
Pierre Cazals
  • Université Paris-Dauphine, PSL Research University, CNRS, UMR 7243, LAMSADE, 75016 Paris, France

Cite AsGet BibTex

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)
https://doi.org/10.4230/LIPIcs.SWAT.2022.13

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.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorial optimization
  • Mathematics of computing → Graph algorithms
  • Mathematics of computing → Approximation algorithms
Keywords
  • NP-hardness
  • approximation
  • density
  • graph partitioning
  • bipartite graphs
  • cubic graphs
  • dense graphs

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Sanjeev Arora, David R. Karger, and Marek Karpinski. Polynomial time approximation schemes for dense instances of np-hard problems. Journal of Computer and System Sciences, 58(1):193-210, 1999. Google Scholar
  2. Haris Aziz, Serge Gaspers, Joachim Gudmundsson, Julián Mestre, and Hanjo Taubig. Welfare maximization in fractional hedonic games. In Proceedings of the 24th International Joint Conference on Artificial Intelligence, IJCAI 2015, pages 468-474. AAAI Press, 2015. Google Scholar
  3. Piotr Berman and Marek Karpinski. On some tighter inapproximability results (extended abstract). In Jirí Wiedermann, Peter van Emde Boas, and Mogens Nielsen, editors, Proceedings of the 26th International Colloquium on Automata, Languages and Programming, ICALP 1999, volume 1644 of LNCS, pages 200-209. Springer, 1999. Google Scholar
  4. Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, and Aravindan Vijayaraghavan. Detecting high log-densities: an O(n^1/4) approximation for densest k-subgraph. In Leonard J. Schulman, editor, Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 201-210. ACM, 2010. Google Scholar
  5. Rowland Leonard Brooks. On colouring the nodes of a network. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 37:2, pages 194-197. Cambridge University Press, 1941. Google Scholar
  6. Aydin Buluç, Henning Meyerhenke, Ilya Safro, Peter Sanders, and Christian Schulz. Recent advances in graph partitioning. In Lasse Kliemann and Peter Sanders, editors, Algorithm Engineering - Selected Results and Surveys, volume 9220 of Lecture Notes in Computer Science, pages 117-158. Springer, 2016. Google Scholar
  7. Derek G. Corneil and Yehoshua Perl. Clustering and domination in perfect graphs. Discrete Applied Mathematics, 9(1):27-39, 1984. Google Scholar
  8. Julien Darlay, Nadia Brauner, and Julien Moncel. Dense and sparse graph partition. Discrete Applied Mathematics, 160(16-17):2389-2396, 2012. Google Scholar
  9. Uriel Feige, Guy Kortsarz, and David Peleg. The dense k-subgraph problem. Algorithmica, 29(3):410-421, 2001. Google Scholar
  10. Santo Fortunato. Community detection in graphs. Physics Reports, 486:75-174, 2010. Google Scholar
  11. M. R. Garey, D. S. Johnson, and L. Stockmeyer. Some simplified NP-complete graph problems. Theoretical Computer Science, 1(3):237-267, 1976. Google Scholar
  12. Andrew V. Goldberg. Finding a maximum density subgraph. University of California Berkeley, 1984. Google Scholar
  13. Teofilo F. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, 38:293-306, 1985. Google Scholar
  14. Subhash Khot. Ruling out PTAS for graph min-bisection, dense k-subgraph, and bipartite clique. SIAM J. Comput., 36(4):1025-1071, 2006. Google Scholar
  15. Samir Khuller and Barna Saha. On finding dense subgraphs. In Proceedings of 36th International Colloquium on Automata, Languages and Programming, ICALP 2009, Part I, volume 5555 of LNCS, pages 597-608, 2009. Google Scholar
  16. Andrea Munaro. On line graphs of subcubic triangle-free graphs. Discrete Mathematics, 340(6):1210-1226, 2017. Google Scholar
  17. Mark E. J. Newman. Detecting community structure in networks. The European Physical Journal B - Condensed Matter and Complex Systems, 38(2):321-330, 2004. Google Scholar
  18. Satu Elisa Schaeffer. Graph clustering. Computer Science Review, 1(1):27-64, 2007. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact