2026-08-06T10:18:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21002 2024-09-16T06:02:38Z ddc:004 open_access

On the Generalized Mean Densest Subgraph Problem: Complexity and Algorithms Chandrasekaran, Karthekeyan Chekuri, Chandra Torres, Manuel R. Zhu, Weihao Densest subgraph problem Hardness of approximation Approximation algorithms 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 [Veldt et al., 2021] 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 [Veldt et al., 2021]. 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 1/2-approximation algorithms for every p ∈ (-∞, 1). We complement the approximation algorithms by exhibiting non-trivial instances on which the algorithms simultaneously achieve an approximation factor of at most 1/2. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Karthekeyan Chandrasekaran and Chandra Chekuri and Manuel R. Torres and Weihao Zhu 2024 Is Part Of LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2024.9 urn:nbn:de:0030-drops-210025 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.9 eng https://creativecommons.org/licenses/by/4.0/legalcode