Improved approximation algorithm for the Dense-3-Subhypergraph Problem

Abstract

The study of Dense-$3$-Subhypergraph problem was initiated in Chlamt{á}c et al. [Approx'16]. The input is a universe $U$ and collection $\mathcal{S}$ of subsets of $U$, each of size $3$, and a number $k$. The goal is to choose a set $W$ of $k$ elements from the universe, and maximize the number of sets, $S\in \mathcal{S}$ so that $S\subseteq W$. The members in $U$ are called {\em vertices} and the sets of $\mathcal{S}$ are called the {\em hyperedges}. This is the simplest extension into hyperedges of the case of sets of size $2$ which is the well known Dense $k$-subgraph problem. The best known ratio for the Dense-$3$-Subhypergraph is $O(n^{\mathrm{0.69783..}})$ by Chlamt{á}c et al. We improve this ratio to $n^{\mathrm{0.61802..}}$. More importantly, we give a new algorithm that approximates Dense-$3$-Subhypergraph within a ratio of $\tilde{O}(n/k)$, which improves the ratio of $O(n^2/k^2)$ of Chlamt{á}c et al. We prove that under the {\em log density conjecture} (see Bhaskara et al. [STOC'10]) the ratio cannot be better than $\Omega (\sqrt{n})$ and demonstrate some cases in which this optimum can be attained.

Claim 4.6 does not hold for the algorithm; we erroneously claimed that we could nullify kD'_i edges in the ith step of the algorithm

Cited by in corpus (1)

• Information Limits for Detecting a Subhypergraph