A More Complicated Hardness Proof for Finding Densest Subgraphs in Bounded Degree Graphs

2013/06/27 by Manuel Sorge, Sorge, Manuel
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Theory and Algorithms #cs.CC #cs.DM #math.CO

paper · pdf · doi:10.48550/arxiv.1306.6598

arxiv created 2013/06/27 · openalex publication_date 2013/06/27 · arxiv updated 2013/06/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider the Densest-Subgraph problem, where a graph and an integer k is given and we search for a subgraph on exactly k vertices that induces the maximum number of edges. We prove that this problem is NP-hard even when the input graph has maximum degree three.

Related

• Finding large and small dense subgraphs
• On solving the densest k-subgraph problem on large graphs
• The Dense k Subgraph problem
• Almost-Polynomial Ratio ETH-Hardness of Approximating Densest k-Subgraph
• On the Generalized Mean Densest Subgraph Problem: Complexity and Algorithms