9
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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$. $\endgroup$ – Andrew D. King Aug 9 '15 at 23:26
  • 4
    $\begingroup$ 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). $\endgroup$ – András Salamon Aug 10 '15 at 0:15
  • 5
    $\begingroup$ @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. $\endgroup$ – Saeed Aug 10 '15 at 7:12
  • 2
    $\begingroup$ 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})$. $\endgroup$ – Michael Wehar Aug 10 '15 at 11:41
  • 2
    $\begingroup$ 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. $\endgroup$ – Saeed Aug 10 '15 at 18:26
12
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.