<p>It is not known if there is an <span class="math-container">$\varepsilon &gt; 0$</span>, <span class="math-container">$c &gt; 2$</span>, and <span class="math-container">$k &gt; c$</span> such that <span class="math-container">$(c,k)$</span> hyperclique is in <span class="math-container">$n^{k-\varepsilon}$</span> time. Note that the case of <span class="math-container">$k \leq c$</span> is trivial. For years I have communicated this problem to many people, and taught it in cs266 at Stanford, due to its connection to solving <span class="math-container">$k$</span>-Sat. (Several open problem sessions at workshops probably recorded this.)  Here are a few things I know:</p>

<p>I proved several years ago that solving <span class="math-container">$4-cycle$</span> on <span class="math-container">$n$</span> node graphs in <span class="math-container">$n^{2-\varepsilon}$</span> time implies <span class="math-container">$(3,4)$</span> hyperclique in <span class="math-container">$n^{4-\varepsilon}$</span> time. Haven't published it. </p>

<p><strong>UPDATE (Aug 2019)</strong> the aforementioned result and some generalizations now appear in the paper</p>

<p>Andrea Lincoln, Virginia Vassilevska Williams, R. Ryan Williams:
<a href="https://people.csail.mit.edu/rrw/SparseGraphsShort.pdf" rel="nofollow noreferrer">Tight Hardness for Shortest Cycles and Paths in Sparse Graphs</a>. SODA 2018: 1236-1252</p>

<p>If you can solve <span class="math-container">$(3,4)$</span> hyperclique as indicated above, then Max-3-Sat can be solved in strictly less than <span class="math-container">$2^n$</span> time. Similarly, solving <span class="math-container">$(k,k+1)$</span> hyperclique would yield a faster <span class="math-container">$k$</span>-Sat algorithm. So if you believe Strong ETH then there is an obvious limit here. The reduction is a natural generalization of the reduction from Max-2-Sat to triangle finding (<span class="math-container">$(2,3)$</span> clique) from ICALP'04 and my PhD thesis. </p>

<p>You can solve <span class="math-container">$(c,k)$</span> hyperclique in <span class="math-container">$n^k/(\log n)^{\Omega(k)}$</span> time by generalizing the paper <a href="http://theory.stanford.edu/~virgi/combclique-ipl-g.pdf" rel="nofollow noreferrer">Efficient Algorithms for Clique Problems</a>. </p>

CC BY-SA 3.0
2015-08-12T08:04:20.523Z
Thanks Ryan!  I appreciate your answer and sharing the paper on the clique problem.  :)
Michael Wehar
CC BY-SA 3.0
2015-09-01T04:22:33.367Z
Is 5-cycle any harder than 4-cycle?
Michael Wehar
CC BY-SA 3.0
2015-09-01T05:40:44.437Z
As far as we know, 3-cycle is harder. The odd case in general takes about O(n^{2.373}) time, the even case takes O(n^2) for fixed length cycles. See for example, Yuster and Zwick, Finding even cycles even faster.
Ryan Williams
CC BY-SA 3.0
2015-09-06T15:02:31.237Z
Oh, wow!  That's quite interesting.  Ok, thank you.  :)
Michael Wehar
CC BY-SA 4.0
2019-08-28T23:54:53.003Z
Cool!  Thanks for the updated reference.
Michael Wehar
CC BY-SA 4.0
2015-08-12T07:12:43.213Z
2019-08-27T06:53:10.290Z
2019-08-27T06:53:10.290Z
Ryan Williams
<p><strong>Classic Problem:</strong></p>

<p>Let a number $k$ be given.  The $k$-clique problem is as follows.</p>

<p>Given a graph $G$, does there exist a subset $S$ of $k$ vertices so that any two vertices of $S$ are adjacent?</p>

<p><strong>Hypergraph Problem:</strong></p>

<p>Let numbers $c$ and $k$ be given.  The $(c,k)$-hyperclique problem is as follows.</p>

<p>Given a $c$-uniform hypergraph $H$, does there exist a set $S$ of $k$ vertices so that any subset of $c$ vertices from $S$ forms a hyperedge.</p>

<p><strong>Questions:</strong></p>

<p>(1) What is the best known algorithm for solving $(c,k)$-hyperclique?</p>

<p>(2) What is its time complexity?</p>

<p>(3) Is there any connection between $(c,k)$-hyperclique and matrix multiplication?</p>

<p>For all I know, this might be a well studied problem.  Any references that investigate this problem are greatly appreciated.</p>

CC BY-SA 3.0
2015-08-09T23:26:52.360Z
May be worth pointing out the obvious: Since we understand the case $c=2$, the problem is NP-complete and not FPT in terms of $c$ (but is FPT in terms of $k$).  Further (still obvious), you could rephrase the problem as the selection of $k$ rows of the incidence matrix such that in the submatrix on these rows, $k\choose c$ columns have sum $c$.
Andrew D. King
CC BY-SA 3.0
2015-08-10T00:15:06.147Z
This is usually phrased in terms of finding a $k$-independent set in a $c$-uniform hypergraph.  See Yuster's 2006 paper http://research.haifa.ac.il/~raphy/papers/counthyper.pdf for some useful pointers (including links with matrix multiplication).
András Salamon
CC BY-SA 3.0
2015-08-10T07:12:57.113Z
@AndrewD.King, I don't understand what do you mean by "but is FPT in terms of k", k-clique is W[1]-hard in terms of k. And OP: K-Clique is already w[1]hard, but your question is not well research level question, as compares it with polynomial problems.
Saeed
CC BY-SA 3.0
2015-08-10T11:41:53.393Z
Thanks for the information.  I'm most interested in whether or not there is some $c>2$ and $k>2$ such that $(c,k)$-hyperclique is in $\mathrm{DTIME}(n^{k-\epsilon})$.  We know that for $k>2$, $k$-clique can be solved in $\mathrm{DTIME}(n^{k-\epsilon})$.
Michael Wehar
CC BY-SA 3.0
2015-08-10T18:26:55.283Z
So you know there is no n^o(k) for clique and by relation to matrix multipulation you don't mean a p reduction but only reducing running time, now it's more clear for me, I have no idea about it but maybe you need to include c into the exponent as well.
Saeed
CC BY-SA 3.0
2015-08-18T17:15:25.260Z
Saeed thank you for pointing out my silly mistake -- $n^k$ is not good enough.
Andrew D. King
<cc.complexity-theory><graph-theory><matrices><clique><fixed-parameter-tractable>
Complexity of k-clique for hypergraphs
Michael Wehar
# Complexity of k-clique for hypergraphs

(Asked by: username_0 on 2015-08-09)

**Classic Problem:**

Let a number $k$ be given. The $k$-clique problem is as follows.

Given a graph $G$, does there exist a subset $S$ of $k$ vertices so that any two vertices of $S$ are adjacent?

**Hypergraph Problem:**

Let numbers $c$ and $k$ be given. The $(c,k)$-hyperclique problem is as follows.

Given a $c$-uniform hypergraph $H$, does there exist a set $S$ of $k$ vertices so that any subset of $c$ vertices from $S$ forms a hyperedge.

**Questions:**

(1) What is the best known algorithm for solving $(c,k)$-hyperclique?

(2) What is its time complexity?

(3) Is there any connection between $(c,k)$-hyperclique and matrix multiplication?

For all I know, this might be a well studied problem. Any references that investigate this problem are greatly appreciated.

**Tags:** cc.complexity-theory, graph-theory, matrices, clique, fixed-parameter-tractable

> **Comments:**
> **username_1**: May be worth pointing out the obvious: Since we understand the case $c=2$, the problem is NP-complete and not FPT in terms of $c$ (but is FPT in terms of $k$).  Further (still obvious), you could rephrase the problem as the selection of $k$ rows of the incidence matrix such that in the submatrix on these rows, $k\choose c$ columns have sum $c$.  
> **username_2**: This is usually phrased in terms of finding a $k$-independent set in a $c$-uniform hypergraph.  See Yuster's 2006 paper http://research.haifa.ac.il/~raphy/papers/counthyper.pdf for some useful pointers (including links with matrix multiplication).  
> **username_3**: @AndrewD.King, I don't understand what do you mean by "but is FPT in terms of k", k-clique is W[1]-hard in terms of k. And OP: K-Clique is already w[1]hard, but your question is not well research level question, as compares it with polynomial problems.  
> **username_0**: Thanks for the information.  I'm most interested in whether or not there is some $c>2$ and $k>2$ such that $(c,k)$-hyperclique is in $\mathrm{DTIME}(n^{k-\epsilon})$.  We know that for $k>2$, $k$-clique can be solved in $\mathrm{DTIME}(n^{k-\epsilon})$.  
> **username_3**: So you know there is no n^o(k) for clique and by relation to matrix multipulation you don't mean a p reduction but only reducing running time, now it's more clear for me, I have no idea about it but maybe you need to include c into the exponent as well.  
> **username_1**: username_3 thank you for pointing out my silly mistake -- $n^k$ is not good enough.  

---

## 1 answers

### Answer by username_4 on 2015-08-12. Score: 14 | Accepted answer

It is not known if there is an $\varepsilon > 0$, $c > 2$, and $k > c$ such that $(c,k)$ hyperclique is in $n^{k-\varepsilon}$ time. Note that the case of $k \leq c$ is trivial. For years I have communicated this problem to many people, and taught it in cs266 at Stanford, due to its connection to solving $k$-Sat. (Several open problem sessions at workshops probably recorded this.) Here are a few things I know:

I proved several years ago that solving $4-cycle$ on $n$ node graphs in $n^{2-\varepsilon}$ time implies $(3,4)$ hyperclique in $n^{4-\varepsilon}$ time. Haven't published it.

**UPDATE (Aug 2019)** the aforementioned result and some generalizations now appear in the paper

Andrea Lincoln, Virginia Vassilevska Williams, R. username_4:
[Tight Hardness for Shortest Cycles and Paths in Sparse Graphs](https://people.csail.mit.edu/rrw/SparseGraphsShort.pdf). SODA 2018: 1236-1252

If you can solve $(3,4)$ hyperclique as indicated above, then Max-3-Sat can be solved in strictly less than $2^n$ time. Similarly, solving $(k,k+1)$ hyperclique would yield a faster $k$-Sat algorithm. So if you believe Strong ETH then there is an obvious limit here. The reduction is a natural generalization of the reduction from Max-2-Sat to triangle finding ($(2,3)$ clique) from ICALP'04 and my PhD thesis.

You can solve $(c,k)$ hyperclique in $n^k/(\log n)^{\Omega(k)}$ time by generalizing the paper [Efficient Algorithms for Clique Problems](http://theory.stanford.edu/~virgi/combclique-ipl-g.pdf).

> **Comments:**
> **username_0**: Thanks Ryan!  I appreciate your answer and sharing the paper on the clique problem.  :)  
> **username_0**: Is 5-cycle any harder than 4-cycle?  
> **username_4**: As far as we know, 3-cycle is harder. The odd case in general takes about O(n^{2.373}) time, the even case takes O(n^2) for fixed length cycles. See for example, Yuster and Zwick, Finding even cycles even faster.  
> **username_0**: Oh, wow!  That's quite interesting.  Ok, thank you.  :)  
> **username_0**: Cool!  Thanks for the updated reference.  

---

