The Densest $k$-Subhypergraph Problem

Eden Chlamtác, Michael Dinitz, Christian Konrad, Guy Kortsarz, George Rabanca

Research output: Contribution to journalArticle (Academic Journal)peer-review

119 Downloads (Pure)

Abstract

The densest $k$-subgraph (D$k$S) problem and its corresponding minimization problem smallest $p$-edge subgraph (S$p$ES) have come to play a central role in approximation algorithms. This is due both to their practical importance and to 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 admit a subpolynomial approximation ratio (although the best-known hardness results do not rule this out). In this paper we generalize both D$k$S and S$p$ES from graphs to hypergraphs. We consider the densest $k$-subhypergraph (D$k$SH) problem (given a hypergraph $(V, E)$, find a subset $W\subseteq V$ of $k$ vertices so as to maximize the number of hyperedges contained in $W$), and define the minimum $p$-union (M$p$U) 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 nongraph setting. For this case we provide an $O(n^{4(4-\sqrt{3})/13 + \epsilon}) < O(n^{0.697831+\epsilon})$-approximation (for arbitrary constant $\epsilon > 0$) for D$k$SH and an $\tilde{O}(n^{2/5})$-approximation for M$p$U. We also give an $O(\sqrt{m})$-approximation for M$p$U 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.
Original languageEnglish
Pages (from-to)1458-1477
Number of pages20
JournalSIAM Journal on Discrete Mathematics
Volume32
Issue number2
Early online date28 Jun 2018
DOIs
Publication statusPublished - 2018

Fingerprint

Dive into the research topics of 'The Densest $k$-Subhypergraph Problem'. Together they form a unique fingerprint.

Cite this