# The Densest k-Subhypergraph Problem

arXiv: https://arxiv.org/abs/1605.04284 · HTML: https://mlsanity.com/paper/1605.04284/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 May 2016.

## Built on by (most cited first, 10 of 10)

- [Approximating Fair Clustering with Cascaded Norm Objectives](https://mlsanity.com/paper/2111.04804/) (2021)
- [A Survey on the Densest Subgraph Problem and Its Variants](https://mlsanity.com/paper/2303.14467/) (2023)
- [Detection of Dense Subhypergraphs by Low-Degree Polynomials](https://mlsanity.com/paper/2304.08135/) (2023)
- [Sharp detection boundaries on testing dense subhypergraph](https://mlsanity.com/paper/2101.04584/) (2021)
- [Heterogeneous Dense Subhypergraph Detection](https://mlsanity.com/paper/2104.04047/) (2021)
- [Information Limits for Detecting a Subhypergraph](https://mlsanity.com/paper/2105.02259/) (2021)
- [Efficient Online Learning for Dynamic k-Clustering](https://mlsanity.com/paper/2106.04336/) (2021)
- [Approximation algorithms for confidence bands for time series](https://mlsanity.com/paper/2112.06225/) (2021)
- [Compact Conformal Subgraphs](https://mlsanity.com/paper/2602.07530/) (2026)
- [Network-Based Interventions for HIV Prevention via Cascade-Aware Suppression of Transmission](https://mlsanity.com/paper/2605.20218/) (2026)

## Abstract (arXiv)

The Densest k-Subgraph (DkS) problem, and its corresponding minimization problem Smallest p-Edge Subgraph (SpES), have come to play a central role in approximation algorithms. This is due both to their practical importance, and their usefulness as a tool for solving and establishing approximation bounds for other problems. These two problems are not well understood, and it is widely believed that they do not an admit a subpolynomial approximation ratio (although the best known hardness results do not rule this out). In this paper we generalize both DkS and SpES from graphs to hypergraphs. We consider the Densest k-Subhypergraph problem (given a hypergraph (V, E), find a subset Wsubseteq V of k vertices so as to maximize the number of hyperedges contained in W) and define the Minimum p-Union problem (given a hypergraph, choose p of the hyperedges so as to minimize the number of vertices in their union). We focus in particular on the case where all hyperedges have size 3, as this is the simplest non-graph setting. For this case we provide an O(n^4(4-√3)/13 + ε) ≤ O(n0.697831+ε)-approximation (for arbitrary constant ε > 0) for Densest k-Subhypergraph and an tilde O(n2/5)-approximation for Minimum p-Union. We also give an O(√m)-approximation for Minimum p-Union in general hypergraphs. Finally, we examine the interesting special case of interval hypergraphs (instances where the vertices are a subset of the natural numbers and the hyperedges are intervals of the line) and prove that both problems admit an exact polynomial time solution on these instances.