The Dense k Subgraph problem

2009/12/29 by Doron Goldstein, Goldstein, Doron, Michael Langberg +1 · 1 citation
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences

paper · pdf · doi:10.48550/arxiv.0912.5327

openalex publication_date 2009/12/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Given a graph G = (V,E) and a parameter k, we consider the problem of finding a subset U in V of size k that maximizes the number of induced edges (DkS). We improve upon the previously best known approximation ratio for DkS, a ratio that has not seen any progress during the last decade. Specifically, we improve the approximation ratio from n^0.32258 to n^0.3159. The improved ratio is obtained by studying a variant to the DkS problem in which one considers the problem of finding a subset U in V of size at most k that maximizes the number of induced edges. Finally, we study the DkS variant in which one considers the problem of finding a subset U in V of size at least k that maximizes the number of induced edges.

Citations

• Finding large and small dense subgraphs

Cited by

• Inapproximability of Maximum Biclique Problems, Minimum k-Cut and\n Densest At-Least-k-Subgraph from the Small Set Expansion Hypothesis

Related

• Planted Models for the Densest k-Subgraph Problem
• Finding large and small dense subgraphs
• Computing Densest k-Subgraph with Structural Parameters
• Detecting High Log-Densities -- an O(n¹/4) Approximation for Densest k-Subgraph
• Almost-Polynomial Ratio ETH-Hardness of Approximating Densest\n k-Subgraph