The Densest k-Subhypergraph Problem

Introduction

Two of the most important outstanding problems in approximation algorithms are the approximability of the Densest $k$-Subgraph problem (D$k$S) and its minimization version, the Smallest $p$-Edge Subgraph problem (S$p$ES or min-D$k$S). In D$k$S we are given as input a graph $G=(V,E)$ and an integer $k$, and the goal is to find a subset $V^{\prime}\subseteq V$ with $|V^{\prime}|=k$ which maximizes the number of edges in the subgraph of $G$ induced by $V^{\prime}$. In the minimization version, S$p$ES, we are given a lower bound $p$ on the number of required edges and the goal is to find a set $V^{\prime}\subseteq V$ of minimum size so that the subgraph induced by $V^{\prime}$ has at least $p$ edges. These problems have proved to be extremely useful: for example, a variant of D$k$S was recently used to get a new cryptographic system . The same variant of the D$k$S problem was shown to be central in understanding financial derivatives . The best-known algorithms for many other problems involve using an algorithm for Densest $k$-Subgraph or S$p$ES as a black box (e.g. ).

Despite decades of work, very little is actually known about these problems. The first approximation ratio for D$k$S was $O(n^{2/5})$ and was devised in 1993. These days, 23 years later, the best known ratio for the Densest $k$-Subgraph is $O(n^{1/4+\epsilon})$ for arbitrarily small constant $\epsilon>0$ , and the best known approximation for S$p$ES is $O(n^{3-2\sqrt{2}+\epsilon})$ for arbitrarily small constant $\epsilon>0$ . Given the slow improvement over 23 years, it is widely believed that D$k$S and S$p$ES do not admit better than a polynomial approximation ratio. Furthermore, the existing approximation guarantees are tight assuming the recently conjectured hardness of finding a planted dense subgraph in a random graph (for certain parameters). However, there has been very little progress towards an actual proof of hardness of approximation. It is clear that they are both NP-hard, but that is all that is known under the assumption that $P\neq NP$. Under much stronger complexity assumptions it is known that they cannot be approximated better than some constant or any constant , but this is still a long way from the conjectured polynomial hardness.

Based on the believed hardness of D$k$S and S$p$ES, they have been used many times to give evidence for hardness of approximation. For example, consider the Steiner $k$-forest problem in which the input is an edge weighted graph, a collection of $q$ pairs $\{s_{i},t_{i}\}_{i=1}^{q}$, and a number $k<q$. The goal is to find a minimum cost subgraph that connects at least $k$ of the pairs. It is immediate to see that S$p$ES is a special case of the Steiner $k$-forest problemGiven an instance $(G=(V,E),p)$ of S$p$ES, create an instance of Steiner $k$-Forest on a star with $V$ as the leaves, uniform weights, a demand pair for each edge in $E$, and $k=p$., and hence it seems highly unlikely that the Steiner $k$-Forest problem admits a better than polynomial approximation ratios.

Given the interest in and importance of D$k$S and S$p$ES, it is somewhat surprising that there has been very little exploration of the equivalent problems in hypergraphs. A hypergraph is most simply understood as a collection $E$ of subsets over a universe $V$ of vertices, where each $e\in E$ is called a hyperedge (so graphs are the special case when each $e\in E$ has cardinality $2$). In general hypergraphs, the obvious extensions of D$k$S and S$p$ES are quite intuitive. In the Densest $k$-Subhypergraph (D$k$SH) problem we are given a hypergraph $(V,E)$ and a value $k$, and the goal is to find a set $W\subseteq V$ of size $k$ that contains the largest number of hyperedges from $E$. In the Minimum $p$-Union (M$p$U) problem we are given a hypergraph and a number $p$, and the goal is to choose $p$ of the hyperedges to minimize the size of their union.

Clearly these problems are at least as hard as the associated problems in graphs, but how much harder are they? Can we design nontrivial approximation algorithms? Can we extend the known algorithms for graphs to the hypergraph setting? Currently, essentially only lower bounds are known: Applebaum showed that they are both hard to approximate to within $n^{\epsilon}$ for some fixed $\epsilon>0$, assuming that a certain class of one-way functions exist. But it was left as an open problem to design any nontrivial upper bound (see footnote $5$ of ).

In this paper we provide the first nontrivial upper bounds for these problems. Let $n$ denote the number of vertices and $m$ denote the number of hyperedges in the input hypergraph. Our first result is an approximation for Minimum $p$-Union in general hypergraphs:

There is an $O(\sqrt{m})$-approximation for the Minimum $p$-Union problem.

We then switch our attention to the low rank case, since this is the setting closest to graphs. In particular, we focus on the $3$-uniform case, where all hyperedges have size at most $3$. In this setting it is relatively straightforward to design an $O(n)$-approximation for Densest $k$-Subhypergraph, although even this is not entirely trivial (the optimal solution could have size up to $k^{3}$ rather than $k^{2}$ as in graphs, which would make the trivial algorithm of choosing $k/3$ hyperedges only an $O(n^{2})$-approximation rather than an $O(n)$-approximation as in graphs). We show that by very carefully combining a set of algorithms and considering the cases where they are all jointly tight we can significantly improve this approximation, obtaining the following theorem:

For every constant $\epsilon>0$, there is an $O(n^{4(4-\sqrt{3})/13+\epsilon})\leq O(n^{0.697831+\epsilon})$-approximation for the Densest $k$-Subhypergraph problem on $3$-uniform hypergraphs.

Adapting these ideas to the minimization setting gives an improved bound for Minimum $p$-Union as well.

Densest $k$-Subhypergraph and Minimum $p$-Union can be solved in polynomial time on interval hypergraphs.

2 Related Work

As discussed, the motivation for these problems mostly comes from the associated graph problems, which have been extensively studied and yet are still poorly understood. The Densest $k$-Subgraph problem was introduced by Kortsarz and Peleg , who gave an $O(n^{2/5})$ ratio for the problem. Feige, Kortsarz and Peleg improved the ratio to $O(n^{1/3-\epsilon})$ for $\epsilon$ that is roughly $1/60$. The current best-known approximation for D$k$S is $O(n^{1/4+\epsilon})$ for arbitrarily small constant $\epsilon>0$, due to Bhaskara et al. . For many years the minimization version, S$p$ES, was not considered separately, and it was only relatively recently that the first separation was developed: building on the techniques of but optimizing them for the minimization version, Chlamtáč, Dinitz, and Krauthgamer gave an $O(n^{3-2\sqrt{2}+\epsilon})$-approximation for S$p$ES for arbitrarily small constant $\epsilon>0$.

While defined slightly differently, D$k$SH and M$p$U were introduced earlier by Applebaum in the context of cryptography: he showed that if certain one way functions exist (or that certain pseudorandom generators exist) then D$k$SH is hard to approximate within $n^{\epsilon}$ for some constant $\epsilon>0$. Based on this result, D$k$SH and M$p$U were used to prove hardness for other problems, such as the $k$-route cut problem . To the best of our knowledge, though, there has been no previous work on algorithms for these problems.

3 Organization

We begin in Section 2 with some preliminaries, showing the basic relationships between the problems. In Section 3 we give our $O(\sqrt{m})$-approximation for M$p$U in general hypergraphs. We then focus on small-rank hypergraphs, giving an $O(n^{4/5})$-approximation for D$k$SH on $3$-uniform hypergraphs in Section 4, which we then improve to roughly $O(n^{0.698})$ in Section 5. We follow this in Section 6 with our improved bound for M$p$U on $3$-uniform hypergraphs. Finally in Section 7 we show how to solve both problems exactly in polynomial time on interval hypergraphs. We conclude in Section 8 with some open questions for future work.

Preliminaries and Notation

A hypergraph $H=(V,E)$ consists of a set $V$ (the vertices) together with a collection $E\subseteq 2^{V}$ (the hyperedges), where each hyperedge is a subset of $V$. We will typically use $n=|V|$ and $m=|E|$ to denote the number of vertices and hyperedges respectively. The degree of a vertex in a hypergraph is the number of hyperedges which contain it. Given a subset $V^{\prime}\subseteq V$, the subhypergraph of $H$ induced by $V^{\prime}$ is $H[V^{\prime}]=(V^{\prime},E_{H})$ where $E_{H}=\{e\in E:e\subseteq V^{\prime}\}$. We say that $H$ is $\alpha$-uniform if $|e|=\alpha$ for all $e\in E$, and that the rank of $H$ is $\max_{e\in E}|e|$ (i.e. the smallest $\alpha$ such that all edges have cardinality at most $\alpha$). A hyperedge $e$ is covered by a set of vertices $V^{\prime}$ if $e\subseteq V^{\prime}$.

The main problems that we will consider are the following.

Given a hypergraph $H=(V,E)$ and an integer $k$, the Densest $k$-Subhypergraph problem (D$k$SH) is to find a set $V^{\prime}\subseteq V$, with $|V^{\prime}|=k$, such that the number of edges in $H[V^{\prime}]$ is maximized.

Given a hypergraph $H=(V,E)$ and an integer $p$, the Minimum $p$-Union problem (M$p$U) is to find a set $E^{\prime}\subseteq E$, with $|E^{\prime}|=p$, such that $|\cup_{e\in E^{\prime}}e|$ is minimized.

Note that on $2$-uniform hypergraphs, these two problems are the classic graph problems D$k$S and S$p$ES respectively.

A special class of hypergraphs that we will consider are interval hypergraphs, defined as follows.

We begin by proving some relatively straightforward relationships between the two problems. We first make the obvious observation that a solution for one problem implies a solution for the other.

If there exists a polynomial time algorithm that solves the Densest $k$-Subhypergraph problem for any $k$ on a hypergraph $H$, then there exists a polynomial time algorithm that solves the Minimum $p$-Union problem on the hypergraph $H$. Similarly, if there is an algorithm that solves M$p$U on $H$, then there is an algorithm that solves D$k$SH on $H$.

The relationship is not quite so simple when we are reduced to approximating the problems, but it is relatively straightforward to show that a relationship still exists. This is given by the following lemma, which will also prove to be useful later.

If there exists an algorithm which in a hypergraph $H$ containing a subhypergraph with $k$ vertices and $p$ hyperedges finds a subhypergraph $(V^{\prime},E^{\prime})$ with $|V^{\prime}|\leq fk$ and $|E^{\prime}|\geq|V^{\prime}|p/(kf)$, we can get an $O(f\log p)$-approximation for Min $p$-Union.

Since any $f$-approximation algorithm for Densest $k$-Subhypergraph satisfies the conditions of the lemma, as an immediate corollary we get the following:

If there is an $f$-approximation for Densest $k$-Subhypergraph, then there is an $O(f\log p)$-approximation for Minimum $p$-Union.

Let $(H=(V,E),p)$ be an instance of Minimum $p$-Union, and let $\mathcal{A}$ be an algorithm as described in the lemma. We assume without loss of generality that we know the number of nodes $k$ in the optimal solution (since we can just try all possibilities for $k$), and hence that there exists a set $V^{*}\subseteq V$ with $|V^{*}|=k$ such that $V^{*}$ covers at least $p$ hyperedges. Initialize $E^{\prime}=\emptyset$, and consider the following algorithm for Minimum $p$-Union that repeats the following until $|E^{\prime}|\geq p$.

Let $V^{\prime}=\mathcal{A}(H,k)$, and let $E^{\prime\prime}$ be the hyperedges of $H$ covered by $V^{\prime}$.

Let $E^{\prime}\leftarrow E^{\prime}\cup E^{\prime\prime}$.

Remove $E^{\prime\prime}$ from $H$ (remove only the edges, not the corresponding vertices).

Thus, as soon as the total number of vertices added exceeds $kf\ln p$ for the first time, the number of edges will exceed $p$. Since the last iteration adds at most $kf$ vertices, we are done. $\Box$

A standard argument also shows a (more lossy) reduction in the other direction.

If there is an $f$-approximation for Minimum $p$-Union on $\alpha$-uniform hypergraphs, then there is an $O(f^{\alpha})$-approximation for Densest $k$-Subhypergraph on $\alpha$-uniform hypergraphs (when $\alpha=O(1)$).

Minimum p𝑝p-Union in General Hypergraphs

Given a hypergraph $H=(V,E)$, in this section we work with the bipartite incidence graph $G=(E,V,F)$ of $H$, where $F=\{(e,v)\in E\times V\,:\,v\in e\}$. Solving M$p$U on $H$ corresponds to finding a subset $E^{\prime}\subseteq E$ of $p$ vertices in $G$ of minimum vertex expansion, i.e., $E^{\prime}$ such that $|\Gamma_{G}(E^{\prime})|$ is minimized.

Our algorithm requires a subroutine that returns a subset of vertices of minimum expansion (without the cardinality bound on the set). In other words, we need a polynomial-time algorithm Min-Exp(G) which returns a subset of $E$ so that

for every subset $E^{\prime}\subseteq E$.

Minimally expanding subsets of this kind have previously been used (e.g. in ) in communication settings where computation time is disregarded, but in our context we need a polynomial-time algorithm. In Appendices A and B we give two different algorithms for doing this. The first, in Appendix A, uses a reduction to network flows. The second, in Appendix B, is based on a straightforward adaptation of a linear programming approach for the graph case due to Charikar . In order to simplify the presentation, we will for the rest of the section assume that we have such an algorithm and will defer them to the appendices.

In the following, for subsets $E^{\prime}\subseteq E$ and $V^{\prime}\subseteq V$, we denote the induced subgraph of $G$ by vertex set $E^{\prime}\cup V^{\prime}$ by $G[E^{\prime},V^{\prime}]$.

In the first phase, our algorithm (Algorithm 1) iteratively adds vertices $E^{\prime\prime}$ to an initially empty set $E^{\prime}$ until $E^{\prime}$ exceeds the size $p-\sqrt{m}$. The set $E^{\prime\prime}$ is a minimally expanding subset in the induced subgraph $G[E\setminus E^{\prime},V]$. If $E^{\prime\prime}$ is large so that $|E^{\prime}\cup E^{\prime\prime}|>p$, then an arbitrary subset of $E^{\prime\prime}$ is added to $E^{\prime}$ so that $E^{\prime}$ has the desired size $p$. Then, in the second phase, we add the $k-|E^{\prime}|$ vertices of $E\setminus E^{\prime}$ of smallest degree to $E^{\prime}$ (ties broken arbitrarily), and the algorithm returns set $E^{\prime}$.

Algorithm 1 is a $(2\sqrt{m})$-approximation algorithm for M$p$U.

Let $OPT\subseteq E$ be an optimal solution and let $r=|\Gamma_{G}(OPT)|$. Let $E^{\prime}_{i}$ denote the set $E^{\prime}$ in the beginning of the $i$th iteration of the repeat loop. Suppose that the algorithm runs in $l$ rounds. Then, $E^{\prime}_{l+1}$ is the set $E^{\prime}$ after the last iteration of the loop, but before the nodes selected in Line 1 are added.

Consider an arbitrary iteration $i\leq l$ and let $E^{\prime\prime}\leftarrow\textsc{Min-Exp}(G[E\setminus E^{\prime}_{i},V])$ as in the algorithm. Note that by the condition of the loop, we have $|E_{i}^{\prime}|\leq p-\sqrt{m}$. Furthermore, we have

since $E^{\prime\prime}$ is a set of minimum expansion. Then,

Thus, we have $|\Gamma_{G}(E^{\prime}_{i+1})|\leq|\Gamma_{G}(E^{\prime}_{i})|+\frac{|E^{\prime\prime}|r}{\sqrt{m}}$ (note that this inequality also captures the case when only a subset of $E^{\prime\prime}$ is added to $E^{\prime}$ in Line 1). Now, note that the sets $E^{\prime\prime}$ of any two different iterations are disjoint and thus the sizes of the sets $E^{\prime\prime}$ of the different iterations sum up to at most $m$. We thus obtain the bound:

In phase two, we select at most $\sqrt{m}$ vertices $E^{\prime\prime}$ of minimum degree in $G[E\setminus E^{\prime},V]$. Clearly, the maximum degree of these vertices is at most $r$ (if it was larger, then $|\Gamma_{G}(OPT)|$ would be larger as well) and thus $|\Gamma_{G}(E^{\prime\prime})|\leq\sqrt{m}r$. The neighborhood of the returned set of our algorithm is hence at most $2\sqrt{m}r$ which gives an approximation factor of $2\sqrt{m}$. $\Box$

Densest k𝑘k-Subhypergraph in 333-uniform hypergraphs

In this section, we consider the Densest $k$-Subhypergraph problem in $3$-uniform hypergraphs. We develop an $O(n^{4/5})$-approximation algorithm here, and show in Section 5 how to improve the approximation factor to $O(n^{0.697831+\epsilon})$, for any $\epsilon>0$, by replacing one of our subroutines with an algorithm of Bhaskara et al. .

Throughout this section, let $H=(V,E)$ be the input $3$-uniform hypergraph. Let $K\subseteq V$ denote an optimal solution, i.e., a subset of vertices such that $H[K]$ is a densest $k$-subhypergraph. The average degree of $H[K]$ is denoted by $d=3|E(H[K])|/k$. We say that a hyperedge is optimal if it is contained in $H[K]$.

Let $K_{1}\subseteq V$ be a set of $k/3$ vertices of largest degree (ties broken arbitrarily), $\Delta$ the minimum degree of a node in $K_{1}$, and $H^{\prime}=H[V\setminus K_{1}]$. Note that the maximum degree in $H^{\prime}$ is $\Delta$.

Suppose first that at least half of the optimal hyperedges contain at least one vertex of $K_{1}$. Then the following lemma shows that we can easily achieve a much better approximation than we are aiming for:

Suppose that at least half of the optimal hyperedges contain a vertex of $K_{1}$. Then we can achieve an $O(n^{1/4+\varepsilon})$ approximation for any $\varepsilon>0$.

By our assumption, there is a set $P$ of optimal hyperedges of size at least $dk/6$ such that every edge in $P$ intersects $K_{1}$. Consider two cases.

Case 1: For at least half the edges $e\in P$, we have $|e\cap K_{1}|\geq 2$. Denote the set of these edges by $P^{\prime}$. For every vertex $u\in V$, let its $K_{1}$-weight be the number of pairs $\{v,x\}$ such $v,x\in K_{1}$ and $\{u,v,x\}$ is a hyperedge. Then by our assumption, the vertices in $K$ have average $K_{1}$-weight at least $|P^{\prime}|/k\geq d/12$. Choosing $2k/3$ vertices greedily (by maximum $K_{1}$-weight) gives (along with $K_{1}$) a $k$-subhypergraph with at least $dk/18$ hyperedges.

Case 2: $P^{\prime\prime}=P\setminus P^{\prime}$ contains at least half the hyperedges in $P$. Note that $|e\cap K_{1}|=1$ for every $e\in P^{\prime\prime}$. For every pair of vertices $u,v\in V\setminus K_{1}$, let its $K_{1}$-weight be the number of vertices $x\in K_{1}$ such that $\{u,v,x\}$ is a hyperedge, and let $G$ be the graph on vertices $V\setminus K_{1}$ with these edge weights. Then any $k^{\prime}$-subgraph of $G$ with total edge weight $w$ corresponds to a $(|K_{1}|+k^{\prime})$-subhypergraph of $H$ with at least $w$ hyperedges, and in particular, $G$ contains a $k$-subgraph with average weighted degree at least $2|P^{\prime\prime}|/k\geq d/6$, which can be easily pruned (randomly or greedily) down to a $2k/3$-subgraph with average weighted degree $\Omega(d)$. Thus we can run the Densest $k$-Subgraph approximation algorithm of Bhaskara et al. Strictly speaking, the algorithm in is defined for unweighted graphs, but one can easily adapt it by partitioning the edges into $O(\log n)$ sets with similar edge weights, and running the algorithm separately on every set of edges, thus losing only an additional $O(\log n)$ factor in the approximation., and find a $2k/3$-subgraph of $G$ with total weight at least $kd/n^{1/4+\varepsilon}$, which in turn gives a $(|K_{1}|+2k/3=)k$-subhypergraph of $H$ with a corresponding number of hyperedges. $\Box$

In the more difficult case, at least half of the optimal hyperedges are fully contained in $H^{\prime}$. Exploiting the fact that the maximum degree in $H^{\prime}$ is $\Delta$ and trading off multiple algorithms, we show in the following subsection how to obtain an $O(n^{\frac{4}{5}})$-approximation algorithm in this case.

We start with a greedy algorithm similar to the greedy algorithm commonly used for Densest $k$-Subgraph .

Algorithm 2 selects a subset $K_{2}$ of $k/3$ vertices $v$ with largest $K_{1}$-degree, i.e., the number of hyperedges incident to $v$ that contain at least one vertex of $K_{1}$. Then, a subset $K_{3}$ of $k/3$ vertices $w$ with largest $(K_{1},K_{2})$-degree is selected, where the $(K_{1},K_{2})$-degree of $w$ is the number of hyperedges containing $w$ of the form $\{w,x,y\}$ with $x\in K_{1}$ and $y\in K_{2}$. Note that the sets $K_{1},K_{2}$ and $K_{3}$ are not necessarily disjoint and the returned set may thus be smaller than $k$.

The following lemma gives a lower bound on the average degree guaranteed by this algorithm. It is a straightforward extension of similar algorithms for graphs.

Algorithm 2 returns a $k$-subhypergraph with average degree $\Omega(\Delta k^{2}/n^{2})$.

By choice of $K_{1}$ and definition of $\Delta$, every vertex in $K_{1}$ has degree at least $\Delta$, and so the total number of edges containing vertices in $K_{1}$ is at least $\Delta|K_{1}|/3=\Delta k/9$ (since we could potentially be double-counting or triple-counting some edges).

If we were to choose $n$ vertices for $K_{2}$, there would be at least $\Delta k/9$ edges containing both a vertex in $K_{1}$ and a vertex in $K_{2}$ (as noted above). Choosing $k/3$ vertices greedily out of $n$ yields a set $K_{2}$ such that there are at least $\Delta k/9\cdot(k/3)/n=\Delta k^{2}/(27n)$ such edges.

Finally, choosing the $k/3$ vertices with the largest contribution (out of $n$) for $K_{3}$ ensures that there will be at least $\Delta k^{2}/(27n)\cdot(k/3)/n=\Omega(\Delta k^{3}/n^{2})$ edges in $E\cap K_{1}\times K_{2}\times K_{3}$, giving average degree $\Omega(\Delta k^{2}/n^{2})$. $\Box$

We now offer a second algorithm, which acts on $H^{\prime}$ and is based on neighborhoods of vertices.

Algorithm 3 exploits the bound on the maximum degree in $H^{\prime}$ to find a dense hypergraph inside the neighborhood of any vertex of degree $\Omega(d)$ in $K$, by considering the neighborhood of a vertex as a graph. Pruning low-degree vertices in this graph (which would not contribute many hyperedges to $K$) helps reduce the size of the graph, and makes it easier to find a slightly denser subgraph. Since the vertices of $K$ and their degrees are not known, the algorithm tries all possible vertices.

If $H^{\prime}$ contains a $k$-subhypergraph with average degree $d^{\prime}=\Omega(d)$, then Algorithm 3 returns a $k$-subhypergraph with average degree $\Omega(d^{2}/(\Delta k))$.

Since at the end of the algorithm we take the densest induced subhypergraph of $H^{\prime}$ (among the various choices), it suffices to show that there is some choice of $v$ and $\hat{d}$ which gives this guarantee. So let $v$ be an arbitrary vertex in $K$ with degree (in $K$) at least $d^{\prime}$. We know that $G_{v}$ contains a subgraph with at most $k$ vertices and at least $d^{\prime}$ edges, so its average degree is at least $2d^{\prime}/k$. Setting $\hat{d}=d^{\prime}/(2k)$, we know that the pruning procedure can remove at most $k\cdot d^{\prime}/(2k)=d^{\prime}/2$ out of the $d^{\prime}$ edges in this subgraph, so the subgraph still retains at least $d^{\prime}/2$ edges. On the other hand, we know that $G_{v}$ has at most $\Delta$ edges (since we’ve assumed the maximum degree in $H^{\prime}$ is at most $\Delta$), and therefore, the same holds for the graph $G_{v}^{\hat{d}}$, in which the minimum degree is now at least $d^{\prime}/2k$. This means that $G_{v}^{\hat{d}}$ has at most $2\Delta/(d^{\prime}/2k)=O(\Delta k/d)$ vertices.

Since there exists a $k$-subgraph of $G_{v}^{\hat{d}}$ with $\Omega(d)$ edges, the greedy choice of $S_{v}^{\hat{d}}$ must give some set in which at least $\Omega(d)$ edges are incident. The greedy choice of $T_{v}^{\hat{d}}$ then reduces the lower bound on the number of edges by a $((k-1)/2)/|V(G_{v}^{\hat{d}})|=\Omega(d/\Delta)$ factor, giving us $\Omega(d^{2}/\Delta)$ edges. However, by the definition of $G_{v}$, together with $v$ these edges correspond to hyperedges in $H^{\prime}$. Thus, the algorithm returns a $k$-subhypergraph with $\Omega(d^{2}/\Delta)$ hyperedges, or average degree $d^{2}/(\Delta k)$. $\Box$

Combining the various algorithms we’ve seen with a trivial algorithm and choosing the best one gives us the following guarantee:

There is an $O(n^{4/5})$-approximation for Dense $k$-Subhypergraph in 3-uniform hypergraphs.

By Lemma 4.1, if at least half the optimal edges intersect $K_{1}$, then we can achieve a significantly better approximation (namely, $n^{1/4+\varepsilon}$). Thus, from now on let us assume this is not the case. That is, $H^{\prime}$ still contains a $k$-subhypergraph with average degree $\Omega(d)$. Again, recall that the maximum degree in $H^{\prime}$ is at most $\Delta$.

By Lemma 4.2, Algorithm 2 gives us a $k$-subhypergraph with average degree $d_{1}=\Omega(\Delta k^{2}/n^{2})$. On the other hand, applying Algorithm 3 to $H^{\prime}$ will give us a $k$-subhypergraph with average degree $d_{2}=\Omega(d^{2}/(\Delta k))$ by Lemma 4.3.

Finally, we could choose $k/3$ arbitrary edges in $H$ and the subhypergraph induced on the vertices they span, giving us average degree $d_{3}\geq 1$. Thus, the best of the three will give us a $k$-subhypergraph with average degree at least

Since we must have $k^{2}/d\geq 1$, the above gives an $O(n^{4/5})$ approximation. $\Box$

An improved approximation for 3-uniform Densest k𝑘k-Subhypergraph

In Section 4 we gave an $O(n^{4/5})$ approximation which combined a greedy algorithm with Algorithm 3, which looked for a dense subgraph inside a graph defined by the neighborhood of a vertex in $H$. To find this dense subgraph, we used a very simple greedy approach. However, we have at our disposal more sophisticated algorithms, such as that of Bhaskara et al. . One way to state the result in that paper (see Bhaskara’s PhD thesis for details on this version ) is as follows:

In any $n$-vertex graph $G$, for any $\alpha\in$, if $k=n^{\alpha}$, then Densest $k$-Subgraph in $G$ can be approximated within an $n^{\varepsilon}k^{1-\alpha}$ factor in time $n^{O(1/\varepsilon)}$ for any $\varepsilon>0$.

The $n^{1/4+\varepsilon}$ guarantee of follows since for any $\alpha\in$, we have $k^{1-\alpha}=n^{\alpha(1-\alpha)}\leq n^{1/4}$.

Using this guarantee instead of the simple greedy algorithm for D$k$S, we get the following improved algorithm for 3-uniform Densest $k$-Subhypergraph:

The approximation guarantee in this final algorithm is given by the following lemma:

Let $H^{\prime}$ be an $n$-vertex 3-uniform hypergraph with maximum degree $\leq\Delta$, containing a $k$-subhypergraph of average degree $d^{\prime}$, and let $\alpha,\beta$ be such that $k=n^{\alpha}$ and $\Delta k/d^{\prime}=n^{\beta}$. Then Algorithm 4 returns a $k$-subhypergraph of $H$ of average degree

As in the proof of Lemma 4.3, we can deduce that for at least some choice of $v$ and $\hat{d}$, the graph $G_{v}^{\hat{d}}$ has at most $\min\{n,O(\Delta k/d^{\prime})\}=O(n^{\min\{1,\beta\}})$ vertices and contains a $k$-subgraph with average degree $\Omega(d^{\prime}/k)$.

By Theorem 5.1, since $k=n^{\alpha}=\Omega(|V(G_{v}^{\hat{d}})|^{\alpha/\min\{1,\beta\}})$, the algorithm of will return a $(k-1)$-subgraph of $G_{v}^{\hat{d}}$ with average degree

As noted in the proof of Lemma 4.3, this corresponds to a $k$-subhypergraph of $H^{\prime}$ with the same guarantee. $\Box$

In the notation of Lemma 5.2 we have $\Delta/d^{\prime}=n^{\beta-\alpha}$ which implies that $\beta\geq\alpha$ (since $\Delta\geq d^{\prime}$).

Trading off the various algorithms we have seen, we can now prove the guarantee stated in Theorem 1.2

For every constant $\varepsilon>0$, there is an $O(n^{4(4-\sqrt{3})/13+\varepsilon})\leq O(n^{0.697831+\varepsilon})$-approximation for Densest $k$-Subhypergraph in $3$-uniform hypergraphs.

By Lemma 4.1, if at least half the optimal edges intersect $K_{1}$, then we can achieve a significantly better approximation (namely, $n^{1/4+\varepsilon}$). Thus, from now on let us assume this is not the case. That is, $H^{\prime}$ still contains a $k$-subhypergraph with average degree $\Omega(d)$. Again, recall that the maximum degree in $H^{\prime}$ is at most $\Delta$.

As before, let $\alpha,\beta$ be such that $k=n^{\alpha}$ and $\Delta k/d=n^{\beta}$. By Lemma 4.2, Algorithm 2 gives us a $k$-subhypergraph with average degree

On the other hand, by Lemma 5.2, Algorithm 4 to $H^{\prime}$ will give us a $k$-subhypergraph with average degree

Let us analyze the guarantee given by the best of Algorithm 2 and Algorithm 4. First, consider the case of $\beta>1$. In this case, taking the best of the two gives us approximation ratio at most $n^{\varepsilon+\min\{2-\alpha-\beta,\alpha(2-\alpha)\}}\leq n^{\varepsilon+\min\{1-\alpha,\alpha(2-\alpha)\}}$. It is easy to check that this minimum is maximized when $\alpha=(3-\sqrt{5})/2$ giving approximation ratio $n^{(\sqrt{5}-1)/2+\varepsilon}\leq n^{0.618034+\varepsilon}$, which is even better than our claim.

Now suppose $\beta\leq 1$. In this case, the approximation guarantee is $n^{\varepsilon+\min\{h_{1},h_{2}\}}$, where $h_{1}=2-\alpha-\beta$ and $h_{2}=\alpha(2-\alpha/\beta)$. If $\alpha\geq 2/3$, then it can be checked that we always have $h_{1}\leq h_{2}$ for any $\beta\in[\alpha,1]$, in which case we have approximation factor at most $n^{\varepsilon+2-2/3-2/3}=n^{2/3+\varepsilon}$, which is again better than our claim. On the other hand, if $\alpha\leq(3-\sqrt{5})/2$, then $h_{2}\leq h_{1}$ for any $\beta\leq 1$, and so for this range of $\alpha$ we get approximation factor at most $n^{\varepsilon+\alpha(2-\alpha)}\leq n^{(\sqrt{5}-1)/2}$, which as we’ve noted is also better than our claim. Finally, if $\alpha\in((3-\sqrt{5})/2,2/3)$ then a straightforward calculation shows that

and that the value of $\min\{h_{1},h_{2}\}$ is maximized at this threshold value of $\beta$. And so for $\alpha$ in this range we have $\min\{h_{1},h_{2}\}\leq 1+\alpha/2-\sqrt{1-3\alpha+13\alpha^{2}/4}$, which is maximized at $\alpha=\frac{18+2\sqrt{3}}{39}\approx 0.55$, giving approximation ratio $n^{\varepsilon+4(4-\sqrt{3})/13}$. $\Box$

Minimum p𝑝p-Union in 3-uniform hypergraphs

In this section we explore Minimum $p$-Union (the minimization version of Densest $k$-Subhypergraph), and give the following guarantee:

Note that this is significantly better than the $n^{0.69\ldots}$-approximation we would get by reducing the problem to Densest $k$-Subhypergraph via Theorem 2.6 and applying the approximation algorithm from Theorem 1.2.

In this problem, we are given a 3-uniform hypergraph $H=(V,E)$, and a parameter $p$, the number of hyperedges that we want to find. Let us assume that the optimal solution, $P\subseteq E$, has $k$ vertices (i.e. $|\cup_{e\in P}e|=k$). We do not know $k$, but the algorithm can try every possible value of $k=1,\ldots,n$, and output the best solution. Thus, we assume that $k$ is known, in which case the average degree in the optimum solution is $d=3p/k$.

Recall that it is not necessary to get $p$ edges in one shot. By Lemma 2.5, it is enough to find any subhypergraph of size at most $kn^{2/5}$ with average degree at least $\Omega(d/n^{2/5})$.

We follow along the lines of D$k$SH by choosing vertex set $K_{1}$ to be the $kn^{2/5}$ vertices of largest degree. The following lemma (corresponding to Lemma 4.1 for D$k$SH) shows that if at least half the edges in $P$ intersect $K_{1}$, then by Lemma 2.5 we are done.

Suppose that at least half of the optimal edges contain a vertex of $K_{1}$. Then we can find a subhypergraph with at most $O(kn^{2/5})$ vertices and average degree at least $\Omega(d/n^{2/5})$.

By our assumption, there is a set of optimal hyperedges $P^{\prime}\subset P$ of size at least $dk/6$ such that every edge in $P^{\prime}$ intersects $K_{1}$.

As in the proof of Lemma 4.1, if at least half the edges in $P^{\prime}$ intersect $K_{1}$ in more than one vertex, then we can easily recover a set of $k$ vertices which along with $K_{1}$ contain at least $\Omega(p)=\Omega(kd)$ hyperedges. Since $|K_{1}|=kn^{2/5}$, this subgraph has $O(kn^{2/5})$ vertices and average degree $\Omega(d/n^{2/5})$ as required.

Thus, we may assume that at least half the edges in $P^{\prime}$ intersect $K_{1}$ in exactly one vertex. Then again as in Lemma 4.1, we define a graph $G$ on vertices $V\setminus K_{1}$ where every pair of vertices $u,v\in V\setminus K_{1}$ is an edge with weight $|\{x\in K_{1}\mid(u,v,x)\in E\}|$. Once again, subgraphs of $G$ with total edge weight $w$ correspond to a subhypergraphs of $H$ with at least $w$ edges, and in particular, $G$ contains a $k$-subgraph with average weighted degree at least $\Omega(d)$. Thus running the S$p$ES approximation of (or more precisely, the weighted version ), gives a subgraph with at most $kf$ vertices and total edge weight at least $\Omega(kd)$ for some $f=n^{0.17+\varepsilon}$ (which is well below $n^{2/5}$). Once again, the corresponding subhypergraph has at most $|K_{1}|+kf=O(kn^{2/5})$ vertices, and so the average degree is at least $\Omega(d/n^{2/5})$ as required. $\Box$

Thus, we will assume from now on that at least half of the hyperedges in $P$ do not contain at least one vertex from $K_{1}$, i.e. that $H^{\prime}=H[V\setminus K_{1}]$ still contains at least half the hyperedges in $P$.

As with D$k$SH, we now proceed with a greedy algorithm. Starting with the same vertex set $K_{1}$ defined above, it follows from Lemma 4.2 that if we run Algorithm 2 on $H$ with parameter $n^{2/5}k$, then we get a subhypergraph on $O(kn^{2/5})$ vertices induced on sets $K_{1},K_{2},K_{3}$ such that if the minimum degree in $K_{1}$ (which bounds the maximum degree in $V\setminus K_{1}$) is $\Delta$, then the subhypergraph has average degree $\Omega(\Delta k^{2}n^{4/5}/n^{2})$. The total number of hyperedges in this subhypergraph is $\Omega(\Delta k^{3}n^{6/5}/n^{2})=\Omega(\Delta k^{3}/n^{4/5})$. If this is at least $p=dk/3$, then we are done. Thus, we will assume from now on that $\Delta k^{3}/n^{4/5}=O(dk)$, that is

We reuse Algorithm 3 on $H^{\prime}$, which gives us the following guarantee:

Applying Algorithm 3 to the above hypergraph $H^{\prime}$ with parameter

returns a subhypergraph with at most $kf$ vertices and average degree at least $d/f$ for some

As in the proof of Lemma 4.3, we can deduce that for at least some choice of $v$ and $\hat{d}$, the graph $G_{v}^{\hat{d}}$ has at most $O(\Delta k/d)$ vertices and has minimum degree at least $\Omega(d/k)$.

Note that we may not even have ${\hat{k}}$ vertices in $G^{\hat{d}}_{v}$. If we do have at least ${\hat{k}}$ vertices, then the greedy choice of $S^{\hat{d}}_{v}$ gives us $\Omega({\hat{k}}d/k)$ edges incident in the set (in fact, any choice of $\Omega({\hat{k}})$ vertices would do). The greedy choice of $T^{\hat{d}}_{v}$ then reduces the number of edges by (in the worst case) a ${\hat{k}}/(\Delta k/d)$-factor, giving us a total number of edges

Thus, in this case, we only need to bound the size of the subgraph. By (1), we can bound ${\hat{k}}$ as follows:

If we do not have ${\hat{k}}$ vertices in $G^{\hat{d}}_{v}$, then the algorithm simply returns $G^{\hat{d}}_{v}$ itself, which has at most $\hat{k}=O(k\cdot n^{2/5}/\sqrt{k})$ vertices and average degree at least $\Omega(d/k)$, as required.

As noted in the proof of Lemma 4.3, this corresponds to a subhypergraph of $H^{\prime}$ with the same guarantee. $\Box$

By Lemma 6.3 and Lemma 2.5, it suffices to show that $\max\{k,n^{2/5}/\sqrt{k}\}=O(n^{2/5})$. Since clearly $n^{2/5}/\sqrt{k}\leq n^{2/5}$, let us consider the parameter $k$. By definition of $d$ and $\Delta$, we clearly have $d\leq\Delta$, thus, by (1) we have

which implies $k=O(n^{2/5})$, and so the theorem follows. $\Box$

Interval Hypergraphs

We show now that D$k$S and M$p$U can be solved in polynomial time on interval hypergraphs. We only give an algorithm for M$p$U; a similar algorithm for D$k$S follows then from Observation 2.4.

Minimum $p$-Union is solvable in polynomial time on interval hypergraphs.

Let $b_{1},...,b_{m}$ be the largest elements in hyperedges $e_{1},...,e_{m}$ respectively, and assume that $b_{i}\leq b_{j}$ for any $i<j$. Similarly let $a_{1},...,a_{m}$ be the smallest elements in $e_{1},...,e_{m}$ respectively.

We present a dynamic programming algorithm which calculates for each $j\leq i$ the optimal solution to an instance of Minimum $p$-Union on the hyperedges $e_{1},...,e_{i}$ with $p=j$ under the constraint that $e_{i}$ belongs to the solution. Let $A[i,j]$ store the value of this optimal solution. Assume that the values of $A$ have been computed for all $i^{\prime},j^{\prime}$ with $j^{\prime}\leq i^{\prime}<i$. We show how to compute $A[i,j]$ for any $j\leq i$.

We partition the hyperedges $e_{1},...,e_{i}$ in three sets $A_{i},B_{i},C_{i}$ with $A_{i}$ containing all hyperedges disjoint from $e_{i}$, $B_{i}$ containing all hyperedges intersecting but not included in $e_{i}$, and $C_{i}$ containing $e_{i}$ and all hyperedges included in $e_{i}$ (see Fig. 1). Therefore we have:

$b_{i^{\prime}}<a_{i}$ for all $e_{i^{\prime}}\in A_{i}$,

$a_{i^{\prime}}<a_{i}\leq b_{i^{\prime}}$ for all $e_{i^{\prime}}\in B_{i}$, and

$a_{i}\leq a_{i^{\prime}}\leq b_{i^{\prime}}\leq b_{i}$ for all $e_{i^{\prime}}\in C_{i}$.

Clearly, for every $j\leq|C_{i}|$ we have $A[i,j]=|e_{i}|$ since by definition of $A$, $e_{i}$ is included in the solution, and adding any other $j-1$ sets from $C_{i}$ to the solution does not increase the size of the union. In the remainder of the proof, when we refer to an optimal solution corresponding to $A[i^{\prime},j^{\prime}]$ for some indices $i^{\prime}$ and $j^{\prime}$ we always mean a solution that uses the maximum number of sets in $C_{i^{\prime}}$.

For any $t\geq 0$ and $j=t+|C_{i}|$, the optimal solution contains exactly $t$ sets in $A_{i}\cup B_{i}$. Fix an optimal solution $OPT_{i}$ corresponding to $A[i,j]$ and let $e_{i^{*}}$ be the hyperedge with largest $b_{e_{i^{*}}}$ in $OPT_{i}$ that does not belong to $C_{i}$. We show that

Then, by considering every hyperedge with index $i^{\prime}<i$ as the possible $i^{*}$ in Eq. (2) and taking the minimum value, one can compute $A[i,j]$ in linear time.

To complete the proof, we argue why Equation 2 holds. First observe that a solution with value $A[i,j]$ exists. Indeed, by adding all elements of $C_{i}\setminus C_{i^{*}}$ to an optimal solution for $A[i^{*},j-|C_{i}\setminus C_{i^{*}}|]$ we obtain a solution for $A[i,j]$ covering exactly $|e_{i}\setminus e_{i^{*}}|$ additional elements. Next, assume that the value of $A[i,j]$ is less than that of Equation 2. Then we can obtain a solution for $A[i^{*},j-|C_{i}\setminus C_{i^{*}}|]$ by removing from $OPT_{i}$ all the elements in $|C_{i}\setminus C_{i^{*}}|$ to obtain a solution with value at most $A[i,j]-|e_{i}\setminus e_{i^{*}}|$, contradicting the fact that $A[i^{*},j-|C_{i}\setminus C_{i^{*}}|]$ is the value of an optimal solution. $\Box$