TY - GEN
T1 - On the Generalized Mean Densest Subgraph Problem
T2 - 27th International Conference on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2024 and the 28th International Conference on Randomization and Computation, RANDOM 2024
AU - Chandrasekaran, Karthekeyan
AU - Chekuri, Chandra
AU - Torres, Manuel R.
AU - Zhu, Weihao
N1 - Publisher Copyright:
© Karthekeyan Chandrasekaran, Chandra Chekuri, Manuel R. Torres, and Weihao Zhu.
PY - 2024/9
Y1 - 2024/9
N2 - 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).
AB - 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).
KW - Approximation algorithms
KW - Densest subgraph problem
KW - Hardness of approximation
UR - http://www.scopus.com/inward/record.url?scp=85204477372&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85204477372&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.APPROX/RANDOM.2024.9
DO - 10.4230/LIPIcs.APPROX/RANDOM.2024.9
M3 - Conference contribution
AN - SCOPUS:85204477372
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2024
A2 - Kumar, Amit
A2 - Ron-Zewi, Noga
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Y2 - 28 August 2024 through 30 August 2024
ER -