The Role of Regularity in (Hyper-)Clique Detection and Implications for Optimizing Boolean CSPs

The $k$-Clique problem is to decide if a $k$-partite graph $G=(V_1,\mathrm{\dots },V_k,E)$ contains a $k$-clique, i.e., $k$ nodes $v_1\in V_1,\mathrm{\dots },v_k\in V_k$ such that any pair $(v_i,v_j)$ forms an edge in $G$.¹¹1Often, the problem is stated for general instead of $k$-partite graphs. However, these formulations are well-known to be equivalent using color-coding techniques, and the restriction to $k$-partite instances often helps in designing reductions. While the trivial algorithm takes time $𝒪(n^k)$, Nešetřil and Poljak [29] devised an algorithm running in time $𝒪(n^{(\omega /3)k})$ where denotes the matrix multiplication exponent [3].²²2More precisely, the running time bound $𝒪(n^{(\omega /3)k})$ applies only when $k$ is divisible by $3$. For general $k$, the running time is $𝒪(n^{\omega (\lfloor k/3\rfloor ,\lceil k/3\rceil ,\lceil (k-1)/3\rceil )})$, where $\omega (a,b,c)$ is the exponent of rectangular matrix multiplication (i.e., $𝒪(n^{\omega (a,b,c)})$ is the running time of multiplying an $n^a\times n^b$ matrix by an $n^b\times n^c$ matrix). The $k$-Clique Hypothesis postulates that this algorithm is essentially optimal (see Section 2). As it generalizes the popular Triangle hypothesis (i.e., the special case $k=3$, stating that the complexity of Triangle Detection is $n^{\omega \pm o(1)}$), this hardness assumption entails fine-grained lower bounds for an extensive list of problems (see e.g. [31]), but also for some important lower bounds beyond the Triangle case [1, 14, 9].

The natural generalization to $h$-uniform hypergraphs, the $(k,h)$-Hyperclique problem, is to decide if a given $k$-partite $h$-uniform hypergraph $G=(V_1,\mathrm{\dots },V_k,E)$ contains a $k$-hyperclique, i.e., $k$ nodes $v_1\in V_1,\mathrm{\dots },v_k\in V_k$ such that all $h$-tuples $x_{i_1},\mathrm{\dots },x_{i_h}$ form a hyperedge in $G$. In contrast to the $k$-Clique problem in graphs (which coincides with $(k,2)$-Hyperclique), the $(k,h)$-Hyperclique problem for $h\ge 3$ is not known to admit any significant improvement over the brute-force search time $𝒪(n^k)$. This led to the ($h$-Uniform) $k$-Hyperclique Hypothesis postulating that time $n^{k-o(1)}$ is necessary in $h$-uniform hypergraphs [25]. Besides being a natural problem in itself, the relevance of the Hyperclique problem is also due to its close connection to the MAX-3-SAT problem [25] and due to a recent surge in strong (often matching) conditional lower bounds based on the Hyperclique conjecture [2, 25, 7, 13, 24, 4, 8, 18, 23, 20, 33].

The starting point of this paper is the following question: Do these hypotheses imply the same time bounds for clique detection in regular (hyper)graphs? While it is clear what we mean by regular graph, it is less clear how to define a regular $h$-uniform hypergraph. The perhaps simplest definition requires each node to be incident to the same number $r_1$ of hyperedges. However, this notion turns out to be insufficient for our main application. Instead, we consider a significantly stronger variant, in which every subset of vertices, each taken from a different part of the $k$-partition, is incident to the same number $r_{\mathrm{\ell }}$ of hyperedges (see Section 2 for details). This yields essentially the strongest form of regularity that we may wish for in a hypergraph. The existence of such structures is well-studied in combinatorial block design theory; e.g., $k$-partite $3$-uniform hypergraphs that are regular in our sense correspond precisely to group divisible designs with $k$ groups, see [15].

Our first main contribution is to establish equivalence of the 3-Uniform Hyperclique Hypothesis for general hypergraphs to its special case of regular $k$-partite hypergraphs in the above strong sense.

We are confident that this theorem will be useful in a black-box fashion for future hardness results based on the $k$-Clique or $k$-Hyperclique hypotheses. Moreover, we extend this equivalence also for counting $k$-hypercliques, see Section 3.

Let us discuss Theorem 1.1: While the statement might feel “obviously true”, to our surprise, proving it turns out to be anything but straightforward. Even for graphs ($h=2$), we are not aware of a previous proof of this fact. The parameterized reductions in [12, 28, 5, 17] are generally not efficient enough as they reduce arbitrary $n$-vertex graphs $G$ with maximum degree $\mathrm{\Delta }$ to regular graphs with $\mathrm{\Omega }(\mathrm{\Delta }n)$ vertices. As $\mathrm{\Delta }$ can be as large as $\mathrm{\Theta }(n)$, this blow-up is inadmissible for our fine-grained perspective (the resulting conditional lower bounds would have the exponent of $n$ halved).

Having said that, it is possible to regularize graphs by only adding $𝒪(n)$ additional nodes. Specifically, one approach is to increase the degree $\mathrm{deg}(v)$ of each node $v$ by $\mathrm{\Delta }-\mathrm{deg}(v)$. To this end we can add $𝒪(n)$ dummy nodes and add an appropriate number of edges between the original nodes and the freshly introduced dummy nodes (while ensuring not to create new $k$-cliques). Afterwards it still remains to regularize the new dummy nodes, which can for instance be solved by balancing the new edges appropriately. The details are tedious and not very insightful.

The real challenge arises for hypergraphs. Recall that the strong regularity guarantee for, say, 3-uniform hypergraphs, is that any pair of vertices (in different vertex parts) must be contained in the same number of hyperedges. Thus, in order to generalize the previous approach we would have to regularize not only the individual dummy nodes, but also all pairs of (original, dummy) and (dummy, dummy) nodes. For this reason we essentially make no progress by adding dummy nodes. Put differently, regularizing graphs is a local problem (in the sense that we could fix the regularity constraints for each node $v$ by adding some dummy nodes only concerned with $v$), whereas regularizing 3-uniform hypergraphs appears to be a more global problem (forcing us to simultaneously regularize all vertex-pairs while not introducing unintended $k$-cliques).

Due to this obstacle, we adopt a very different and conceptually cleaner approach. Let $G$ be a given $k$-partite $h$-uniform hypergraph. The new idea is to construct a regular $k$-partite $h$-uniform hypergraph $G^{\prime }$ from a graph product operation that we call the signed product of $G$ with a suitable signed hypergraph $T$. A signed hypergraph $T$ has positive and negative edges $E^{+}(T)$ and $E^{-}(T)$, respectively. We define the resulting graph $G^{\prime }$ as follows: Its vertex set is $V^{\prime }=V(G)\times V(T)$, and $(u_1,x_1),\mathrm{\dots },(u_h,x_h)\in V^{\prime }$ form a hyperedge in $G^{\prime }$ if and only if

1. 1.

   $\{u_1,\mathrm{\dots },u_h\}\in E(G)$ and $\{x_1,\mathrm{\dots },x_h\}\in E^{+}(T)$, or

2. 2.

   $\{u_1,\mathrm{\dots },u_h\}\notin E(G)$ and $\{x_1,\mathrm{\dots },x_h\}\in E^{-}(T)$.

We prove (Lemma 3.6) that $G^{\prime }$ yields an equivalent, but regular instance for $k$-clique if the following conditions hold:

1. (i)

   There is some $r\in \mathbb{N}$ such that for all nodes $x_1,\mathrm{\dots },x_{h-1}\in V(T)$ (taken from different parts in the $k$-partition of $T$), the set $\{x_1,\mathrm{\dots },x_{h-1}\}$ is contained in exactly $r$ positive and in exactly $r$ negative edges of $T$,

2. (ii)

   there is a $k$-hyperclique in $T$ involving only positive edges, and

3. (iii)

   there is no $k$-hyperclique in $T$ involving a negative edge.

We call a signed hypergraph satisfying these conditions a template graph. Our task is thus simplified to finding suitable template graphs, which only depend on $k$ and $h$, not on $n$.

In a second step, we then show how to construct such template graphs in Lemma 3.10. We employ a construction akin to Cayley graphs for some appropriate group $𝒢$ (concretely, we will pick $𝒢={(\mathbb{Z}/h\mathbb{Z})}^d$ for some appropriate dimension $d=d(k,h)$). That is, let the nodes of $T$ be $k$ independent copies of $𝒢$ denoted $T_1,\mathrm{\dots },T_k$. For each $h$-tuple of vertices, say, $x_1\in T_1,\mathrm{\dots },x_h\in T_h$, we let $\{x_1,\mathrm{\dots },x_h\}$ be a positive edge if and only if $x_1+\mathrm{\cdots }+x_h=a^{+}$ for some fixed group element $a^{+}\in 𝒢$, and we let $\{x_1,\mathrm{\dots },x_h\}$ be a negative edge if and only if $x_1+\mathrm{\cdots }+x_h=a^{-}$ for some other fixed group element $a^{-}\in 𝒢$. The advantage of this construction is that it is immediately clear that the resulting graph $T$ satisfies the regularity condition (i): For each $x_1\in T_1,\mathrm{\dots },x_{h-1}\in T_{h-1}$ there is a unique choice $x_h:=a^{+}-(x_1+\mathrm{\cdots }+x_{h-1})\in T_h$ such that $\{x_1,\mathrm{\dots },x_h\}$ is a positive hyperedge; the same applies to negative edges and all other combinations of parts $T_{i_1},\mathrm{\dots },T_{i_h}$. We will then pick the elements $a^{+}$ and $a^{-}$ in a specific way to guarantee the remaining conditions (ii) and (iii).

Below, in Sections 1.2 and 1.3, we discuss applications of Theorem 1.1.

The algorithmic part of the above theorem is a straightforward adaption of a similar reduction of Weighted Degree-2 CSP to $k$-clique detection given in [32, Section 6.5], see also [25, 6]. Our main technical contribution for Theorem 1.2 is to prove that this algorithmic technique is essentially the best possible, unless the 3-uniform hyperclique hypothesis can be refuted.

For ease of presentation, consider first a constraint family $ℱ$ containing a constraint function $f:{\{0,1\}}^3\to \{0,1\}$ that is symmetric and has $\mathrm{deg}(f)=3$. Let $\alpha ,\beta ,\gamma ,\delta$ be such that $f(x,y,z)=\alpha \cdot xyz+\beta \cdot (xy+yz+xz)+\gamma \cdot (x+y+z)+\delta$ and note that $\alpha \ne 0$. The main idea is the following: Given a $k$-partite regular 3-uniform hypergraph $G=(V_1\cup \mathrm{\cdots }\cup V_k,E)$ with $|V_i|=n$ for $i\in [k]$, we create a Boolean CSP by introducing, for each $\{a,b,c\}\in E(G)$, the constraint $f(x_a,x_b,x_c)$. Since $G$ is regular, there is some $\lambda$ such that any pair of nodes not from the same part is incident to precisely $\lambda$ edges. Thus, a weight-$k$ assignment respecting the $k$-partition, i.e., the 1-variables $x_{i_1},\mathrm{\dots },x_{i_j}$ satisfy $i_j\in V_j$, has an objective value of

The $\alpha$-term is the only term depending on the choice of the assignment, maximizing the objective (for $\alpha >0$, can be handled similarly) if and only if the assignment corresponds to a clique in $G$. For $\beta >0$, $k$-partite assignments are favorable over non-partite assignments. For $\beta \le 0$, we instead need to make sure that $k$-partite assignments are favorable, by carefully introducing dummy constraints. Finally, we show how to handle ${\text{maxCSP}}_k(ℱ)$ if $ℱ$ contains any (not necessarily symmetric) constraint function with degree at least 3.

An interesting follow-up question to our work is whether we can obtain a similar regularization reduction for the non-$k$-partite Hyperclique problem. This question is of lesser importance for the design of reductions as in most (though not all) contexts it is more convenient to work with the $k$-partite version. Interestingly, already constructing an interesting NO instance to the problem – i.e., a 3-uniform hypergraph $G=(V,E)$ that is dense (say, has at least $|E|\ge n^{3-o(1)}$ hyperedges), regular (i.e., each pair of distinct vertices $v_1,v_2\in V$ appears in the same number of hyperedges) and does not contain a 4-clique – appears very challenging. Even disregarding the 4-clique constraint, constructing (non-$k$-partite) regular hypergraphs falls into the domain of combinatorial block designs and is known to be notoriously difficult.

Let $\{i_1,\mathrm{\dots },i_{h+1}\}\in \left(\genfrac{}{}{0pt}{}{k}{h+1}\right)$, and assume for contradiction that there exists a clique of size $h+1$ consisting of vertices $v_1\in T_{i_1},\mathrm{\dots },v_{h+1}\in T_{i_{h+1}}$, such that (w.l.o.g.) $\{v_1,\mathrm{\dots },v_h\}\in E^{-}$. Let $S:=\{i_1,\mathrm{\dots },i_h\}$ and $x_i$ be the elements that corresponds to $v_i$. By construction of $T(h,k)$, this means that $x_1,\mathrm{\dots },x_h$ satisfy the equation $x_1+\mathrm{\cdots }+x_h=e_S$. Moreover, since $v_1,\mathrm{\dots },v_{h+1}$ form a clique, for any subset $S_j:=\{i_1,\mathrm{\dots },i_{j-1},i_{j+1},\mathrm{\dots }{i}_{h+1}\}$ with $S_j\ne S$, we have

As $S_j\ne S$, if we consider only the entry indexed by $S$, we get $x_1[S]+\mathrm{\cdots }+x_{j-1}[S]+x_{j+1}[S]+\mathrm{\cdots }+x_{h+1}[S]=0$. Over all possible values of $j$, we obtain the following equation system.

Summing up all the rows, we get that $h(x_1[S]+\mathrm{\cdots }+x_{h+1}[S])=1$. Recalling that $h=0$ in $\mathbb{Z}/h\mathbb{Z}$, we get that $0=1$, which is a contradiction. $◀$ We can finally observe that choosing a vertex $v_i\in T_i$ corresponding to the zero element $\overline{0}\in 𝒢$ for each $V_i$ yields a clique of size $k$ in $T(h,k)$. We state this as a separate observation.

This concludes the proof of Lemma 3.10. We are also ready to prove Theorems 3.1 and 3.2.

Given an arbitrary $h$-uniform hypergraph $G$, construct the signed hypergraph $T(h,k)$ as above. By Lemma 3.10, this is a template hypergraph. Let $G^{\prime }$ be the signed product of $G$ and $T(h,k)$. Then, by Lemma 3.6 $G^{\prime }$ has all the desired properties. $◀$

Assume that we can decide if an $(s,\lambda )$-regular $h$-uniform hypergraph contains a clique of size $k$ in time $f(k)𝒪(n^{g(k)})$, for computable functions $f,g$ and $g(k)\ge h$. Then, given an arbitrary $h$-uniform hypergraph $G$ consisting of $n$ vertices, by Theorem 3.1 we can construct an $(s,\lambda )$-regular $h$-uniform hypergraph $G^{\prime }$ in linear time, such that it contains a clique of size $k$ if and only if $G$ contains a clique of size $k$. Moreover, the number of vertices of $G^{\prime }$ is bounded by $f^{\prime }(k)n$ for some computable function $f^{\prime }$. We then run the fast algorithm to detect cliques of size $k$ in time $𝒪({(f^{\prime }(k)n)}^{g(k)})=f^{\prime \prime }(k)n^{g(k)})$ and report this as the solution to the original instance. Note that the other direction is trivial. $◀$ In fact, we can prove an even stronger result, showing that counting cliques of size $k$ in regular hypergraphs is as hard as counting cliques in general hypergraphs.

In order to prove this theorem, we extend Observation 3.11 to show that there is in fact a fixed number of cliques in our constructed template graph, only depending on $h$ and $k$. Recall that by $𝒢$ we denote the group ${\left(\mathbb{Z}/h\mathbb{Z}\right)}^{\left(\genfrac{}{}{0pt}{}{k}{h}\right)}$. We prove the next lemma in the full paper.

The proof of Theorem 3.15 now follows directly.

Our goal is to prove that if there exists a $k$-clique in the hypergraph $G$, then any weight-$k$ assignment $a$ that maximizes $\mathrm{\Phi }(a)$ sets the vertices in $G$ that correspond to this $k$-clique to $1$ and all other vertices to $0$. The strategy that we take to prove this is to first prove that any weight-$k$ assignment that maximizes $\mathrm{\Phi }(a)$ has to be $k$-partite. We then prove that among all the $k$-partite assignments, the one that maximizes the value of $\mathrm{\Phi }(a)$ corresponds to a $k$-clique in $G$ (i.e. either a $k$-clique, or an independent set in $G^{\prime }$, depending on sign of $\alpha$).

We sketch the proof here and refer the reader to the full paper for the detailed proof.

Using Observation 4.4, it holds that

Recall that in Equation 1 we have $f(x,y,z)=\alpha \cdot xyz+\beta (xy+xz+yz)+\gamma (x+y+z)+\delta$. Plugging this in above, we get