On the Generalized Mean Densest Subgraph Problem: Complexity and Algorithms

Karthekeyan Chandrasekaran, Chandra Chekuri, Manuel R. Torres, Weihao Zhu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Dense subgraph discovery is an important problem in graph mining and network analysis with several applications. Two canonical polynomial-time solvable problems here are to find a maxcore (subgraph of maximum min degree) and to find a densest subgraph (subgraph of maximum average degree). Both of these problems can be solved in polynomial time. Veldt, Benson, and Kleinberg [47] introduced the generalized p-mean densest subgraph problem which captures the maxcore problem when p = −∞ and the densest subgraph problem when p = 1. They observed that for p ≥ 1, the objective function is supermodular and hence the problem can be solved in polynomial time. In this work, we focus on the p-mean densest subgraph problem for p ∈ (−∞, 1). We prove that for every p ∈ (−∞, 1), the problem is NP-hard, thus resolving an open question from [47]. We also show that for every p ∈ (0, 1), the weighted version of the problem is APX-hard. On the algorithmic front, we describe two simple 12 -approximation algorithms for every p ∈ (−∞, 1).

Original languageEnglish (US)
Title of host publicationApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2024
EditorsAmit Kumar, Noga Ron-Zewi
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959773485
DOIs
StatePublished - Sep 2024
Event27th International Conference on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2024 and the 28th International Conference on Randomization and Computation, RANDOM 2024 - London, United Kingdom
Duration: Aug 28 2024Aug 30 2024

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume317
ISSN (Print)1868-8969

Conference

Conference27th International Conference on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2024 and the 28th International Conference on Randomization and Computation, RANDOM 2024
Country/TerritoryUnited Kingdom
CityLondon
Period8/28/248/30/24

Keywords

  • Approximation algorithms
  • Densest subgraph problem
  • Hardness of approximation

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'On the Generalized Mean Densest Subgraph Problem: Complexity and Algorithms'. Together they form a unique fingerprint.

Cite this