Theoretical Computer Science
- cc.complexity-theory np parameterized-complexity clique
- Updated Sat, 25 Jun 2022 19:40:55 GMT
-
Hardness of parameterized CLIQUE?
Let $0\le p\le 1$ and consider the decision problem
CLIQUE$_p$
Input: integer $s$, graph $G$ with $t$ vertices and $\lceil p\binom{t}{2} \rceil$ edges
Question: does $G$ contain a clique on at least $s$ vertices?
An instance of CLIQUE$_p$ contains a proportion $p$ out of all possible edges. Clearly CLIQUE$_p$ is easy for some values of $p$. CLIQUE$_0$ contains only completely disconnected graphs, and CLIQUE$_1$ contains complete graphs. In either case, CLIQUE$_p$ can be decided in linear time. On the other hand, for values of $p$ close to $1/2$, CLIQUE$_p$ is NP-hard by a reduction from CLIQUE itself: essentially, it is enough to take the disjoint union with the Turn graph $T(t,s-1)$.
My question:
Is CLIQUE$_p$ either in PTIME or NP-complete for every value of $p$? Or are there values of $p$ for which CLIQUE$_p$ has intermediate complexity (if P NP)?
This question arose from a related question for hypergraphs, but it seems interesting in its own right.
Solution
I assume that the number $\left\lceil p \binom{t}{2} \right\rceil$ in the definition of the problem CLIQUEp is exactly equal to the number of edges in the graph, unlike gphilips comment to the question.
The problem CLIQUEp is NP-complete for any rational constant 0<p<1 by a reduction from the usual CLIQUE problem. (The assumption that p is rational is only required so that $\lceil pN \rceil$ can be computed from N in time polynomial in N.)
Let k3 be an integer satisfying both k21/p and (11/k)(12/k)>p. Given a graph G with n vertices and m edges along with a threshold value s, the reduction works as follows.
- If s<k, we solve the CLIQUE problem in time O(ns) time. If there is a clique of size at least s, we produce a fixed yes-instance. Otherwise, we produce a fixed no-instance.
- If n<s, we produce a fixed no-instance.
- If nsk, we add to G a (k1)-partite graph where each set consists of n vertices which has exactly $\left\lceil p \binom{nk}{2} \right\rceil - m$ edges, and produce this graph.
Note that the case 1 takes O(nk1) time, which is polynomial in n for every p. The case 3 is possible because if nsk, then $\left\lceil p \binom{nk}{2} \right\rceil - m$ is nonnegative and at most the number of edges in the complete (k1)-partite graph Kn,,n as shown in the following two claims.
Claim 1. $\left\lceil p \binom{nk}{2} \right\rceil - m \ge 0$.
Proof. Since $m \le \binom{n}{2}$, it suffices if we prove $p \binom{nk}{2} \ge \binom{n}{2}$, or equivalently pnk(nk1) n(n1). Since p 1/k2, we have pnk(nk1) n(n1/k) n(n1). QED.
Claim 2. $\left\lceil p \binom{nk}{2} \right\rceil - m \lt n^2 \binom{k-1}{2}$. (Note that the right-hand side is the number of edges in the complete (k1)-partite graph Kn,,n.)
Proof. Since $\lceil x \rceil \lt x+1$ and m 0, it suffices if we prove $p \binom{nk}{2} + 1 \le n^2 \binom{k-1}{2}$, or equivalently n2(k1)(k2) pnk(nk1) 2 0. Since p < (11/k)(12/k), we have $$n^2(k-1)(k-2) - pnk(nk-1) - 2$$ $$\ge n^2(k-1)(k-2) - n \left( n-\frac{1}{k} \right) (k-1)(k-2) - 2$$ $$= \frac{n}{k} (k-1)(k-2) - 2 \ge (k-1)(k-2) - 2 \ge 0.$$ QED.
Edit: The reduction in Revision 1 had an error; it sometimes required a graph with negative number of edges (when p was small). This error is fixed now.