17
$\begingroup$

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 Turán 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.

$\endgroup$
  • 1
    $\begingroup$ interesting question ! $\endgroup$ – Suresh Venkat Sep 18 '10 at 20:38
  • $\begingroup$ Is p a real number between 0 and 1, or can p be a function of t? $\endgroup$ – Robin Kothari Sep 18 '10 at 20:47
  • $\begingroup$ @Robin: I haven't specified, both would be interesting. $\endgroup$ – András Salamon Sep 18 '10 at 20:50
  • 3
    $\begingroup$ If the proportion of edges is an upper bound (and not an exact count requirement or a lower bound), then for any constant $0<p<1$ this problem is NP-hard by reduction from CLIQUE: Add a sufficiently large set of isolated vertices. Is the requirement that the number edges be equal to the given expression? Or what glaringly obvious thing am I missing? :-) $\endgroup$ – gphilip Sep 19 '10 at 0:20
  • 1
    $\begingroup$ @gphilip: As you point out the reduction is immediate if the proportion is just an upper bound; this is why the question is phrased in terms of the exact proportion. $\endgroup$ – András Salamon Sep 19 '10 at 12:14
13
$\begingroup$

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 gphilip’s 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 k≥3 be an integer satisfying both k2≥1/p and (1−1/k)(1−2/k)>p. Given a graph G with n vertices and m edges along with a threshold value s, the reduction works as follows.

  1. 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.
  2. If n<s, we produce a fixed no-instance.
  3. If nsk, we add to G a (k−1)-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(nk−1) 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 (k−1)-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(nk−1) ≥ n(n−1). Since p ≥ 1/k2, we have pnk(nk−1) ≥ n(n−1/k) ≥ n(n−1). 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 (k−1)-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(k−1)(k−2) − pnk(nk−1) − 2 ≥ 0. Since p < (1−1/k)(1−2/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.

$\endgroup$
  • $\begingroup$ this is closest to the specific phrasing, so thanks for tackling it. Case 3 is closest to what I had in mind. However, I don't follow the calculation -- could you expand a little? $\endgroup$ – András Salamon Sep 19 '10 at 11:32
  • $\begingroup$ @András Salamon: Done. $\endgroup$ – Tsuyoshi Ito Sep 19 '10 at 12:25
15
$\begingroup$

If $p$ can be a function of $t$, then the problem can be intermediate. Set up $p$ so that the number of edges will be say $\log^4 t$. Then obviously $s$ can be at most $\log^2 t$ and hence there is a $t^{\log^2 t}$ algorithm for this problem, meaning that the problem (under standard assumptions, say SAT doesn't have subexponential algorithms) cannot be NP hard.

On the other hand, this problem is harder than the standard clique problem on $\log^2 t$ vertices (you can always place all the edges on those vertices and ignore the rest). And so again, under the same assumption the problem doesn't have a polynomial time algorithm.

If $p$ is a constant then it's always NP hard as gphilip said.

$\endgroup$

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.