# Complexity of k-clique for hypergraphs

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.

• 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 Aug 9 '15 at 23:26
• This is usually phrased in terms of finding a $k$-independent set in a $c$-uniform hypergraph. See Yuster's 2006 paper research.haifa.ac.il/~raphy/papers/counthyper.pdf for some useful pointers (including links with matrix multiplication). – András Salamon Aug 10 '15 at 0:15
• @AndrewD.King, I don't understand what do you mean by "but is FPT in terms of k", k-clique is W-hard in terms of k. And OP: K-Clique is already whard, but your question is not well research level question, as compares it with polynomial problems. – Saeed Aug 10 '15 at 7:12
• 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 Aug 10 '15 at 11:41
• 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 Aug 10 '15 at 18:26

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. Ryan Williams: Tight Hardness for Shortest Cycles and Paths in Sparse Graphs. 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.

• Thanks Ryan! I appreciate your answer and sharing the paper on the clique problem. :) – Michael Wehar Aug 12 '15 at 8:04
• Is 5-cycle any harder than 4-cycle? – Michael Wehar Sep 1 '15 at 4:22
• 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 Sep 1 '15 at 5:40
• Oh, wow! That's quite interesting. Ok, thank you. :) – Michael Wehar Sep 6 '15 at 15:02
• Cool! Thanks for the updated reference. – Michael Wehar Aug 28 at 23:54