10
$\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.

Improve this question
$\endgroup$
6
  • 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, 2015 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, 2015 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, 2015 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, 2015 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, 2015 at 18:26

1 Answer 1

Reset to default
14
$\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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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