<p>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.</p>

<p>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.</p>

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

CC BY-SA 2.5
2010-09-19T00:31:54.863Z
2010-09-19T00:31:54.863Z
Boaz Barak
<p>I assume that the number $\left\lceil p \binom{t}{2} \right\rceil$ in the definition of the problem CLIQUE<sub><em>p</em></sub> is exactly equal to the number of edges in the graph, unlike gphilip’s comment to the question.</p>

<p>The problem CLIQUE<sub><em>p</em></sub> is NP-complete for any rational constant 0&lt;<em>p</em>&lt;1 by a reduction from the usual CLIQUE problem.  (The assumption that <em>p</em> is rational is only required so that $\lceil pN \rceil$ can be computed from <em>N</em> in time polynomial in <em>N</em>.)</p>

<p>Let <em>k</em>≥3 be an integer satisfying both <em>k</em><sup>2</sup>≥1/<em>p</em> and (1−1/<em>k</em>)(1−2/<em>k</em>)&gt;<em>p</em>.  Given a graph <em>G</em> with <em>n</em> vertices and <em>m</em> edges along with a threshold value <em>s</em>, the reduction works as follows.</p>

<ol>
<li>If <em>s</em>&lt;<em>k</em>, we solve the CLIQUE problem in time O(<em>n</em><sup><em>s</em></sup>) time.  If there is a clique of size at least <em>s</em>, we produce a fixed yes-instance.  Otherwise, we produce a fixed no-instance.</li>
<li>If <em>n</em>&lt;<i>s</i>, we produce a fixed no-instance.</li>
<li>If <em>n</em>≥<i>s</i>≥<i>k</i>, we add to <em>G</em> a (<em>k</em>−1)-partite graph where each set consists of <em>n</em> vertices which has exactly $\left\lceil p \binom{nk}{2} \right\rceil - m$ edges, and produce this graph.</li>
</ol>

<p>Note that the case 1 takes O(<em>n</em><sup><em>k</em>−1</sup>) time, which is polynomial in <em>n</em> for every <em>p</em>.  The case 3 is possible because if <em>n</em>≥<i>s</i>≥<i>k</i>, then $\left\lceil p \binom{nk}{2} \right\rceil - m$ is nonnegative and at most the number of edges in the complete (<em>k</em>−1)-partite graph K<sub><em>n</em>,…,<em>n</em></sub> as shown in the following two claims.</p>

<p><strong>Claim 1</strong>.  $\left\lceil p \binom{nk}{2} \right\rceil - m \ge 0$.</p>

<p><strong>Proof</strong>.  Since $m \le \binom{n}{2}$, it suffices if we prove $p \binom{nk}{2} \ge \binom{n}{2}$, or equivalently <i>pnk</i>(<i>nk</i>−1) ≥ <i>n</i>(<i>n</i>−1).  Since <i>p</i> ≥ 1/<i>k</i><sup>2</sup>, we have <i>pnk</i>(<i>nk</i>−1) ≥ <i>n</i>(<i>n</i>−1/<i>k</i>) ≥ <i>n</i>(<i>n</i>−1).  <strong>QED</strong>.</p>

<p><strong>Claim 2</strong>.  $\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 K<sub><i>n</i>,…,<i>n</i></sub>.)</p>

<p><strong>Proof</strong>.  Since $\lceil x \rceil \lt x+1$ and <em>m</em> ≥ 0, it suffices if we prove $p \binom{nk}{2} + 1 \le n^2 \binom{k-1}{2}$, or equivalently <i>n</i><sup>2</sup>(<i>k</i>−1)(<i>k</i>−2) − <i>pnk</i>(<i>nk</i>−1) − 2 ≥ 0.  Since <i>p</i> &lt; (1−1/<i>k</i>)(1−2/<i>k</i>), 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.$$
<strong>QED</strong>.</p>

<p><em>Edit</em>: The reduction in Revision 1 had an error; it sometimes required a graph with negative number of edges (when <em>p</em> was small).  This error is fixed now.</p>

CC BY-SA 2.5
2010-09-19T11:32:57.450Z
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?
András Salamon
CC BY-SA 2.5
2010-09-19T12:25:25.807Z
@András Salamon: Done.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-19T02:54:58.993Z
2010-09-20T00:48:34.430Z
2010-09-20T00:48:34.430Z
Tsuyoshi Ito
<p>Let $0\le p\le 1$ and consider the decision problem</p>

<blockquote>
  <p>CLIQUE$_p$<br>
  <em>Input:</em> integer $s$, graph $G$ with $t$ vertices and $\lceil p\binom{t}{2} \rceil$ edges<br>
  <em>Question:</em> does $G$ contain a clique on at least $s$ vertices?</p>
</blockquote>

<p>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 <a href="http://en.wikipedia.org/wiki/Tur%C3%A1n_graph">Turán graph</a> $T(t,s-1)$.</p>

<p>My question:</p>

<blockquote>
  <p>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)?</p>
</blockquote>

<p>This question arose from a related question for hypergraphs, but it seems interesting in its own right.</p>

CC BY-SA 3.0
2012-08-23T16:36:41.997Z
for an example of a proof of this for the special case you mention, p=1/2, called the "central slice", shown NP complete, see P.E. Dunne. The complexity of central slice functions. Theoretical Computer Science (44) 1986 pp 247-257. the author shows a similar result for SAT.
vzn
CC BY-SA 3.0
2013-09-25T03:44:03.780Z
note also this is exactly the [Erdos-Renyi random graph model](http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model).
vzn
CC BY-SA 2.5
2010-09-18T20:38:37.780Z
interesting question !
Suresh Venkat
CC BY-SA 2.5
2010-09-18T20:47:02.430Z
Is p a real number between 0 and 1, or can p be a function of t?
Robin Kothari
CC BY-SA 2.5
2010-09-18T20:50:55.500Z
@Robin: I haven't specified, both would be interesting.
András Salamon
CC BY-SA 2.5
2010-09-19T00:20:46.260Z
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? :-)
gphilip
CC BY-SA 2.5
2010-09-19T00:25:17.633Z
Off topic: Could someone with enough reputation add a pointer to http://fpt.wikidot.com/ in the tag wiki for the parameterized-complexity tag here : http://cstheory.stackexchange.com/tags/parameterized-complexity/info ?
gphilip
CC BY-SA 2.5
2010-09-19T04:46:40.843Z
done. check the tag wiki.
Suresh Venkat
CC BY-SA 2.5
2010-09-19T12:14:46.887Z
@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.
András Salamon
<cc.complexity-theory><np><parameterized-complexity><clique>
Hardness of parameterized CLIQUE?
András Salamon
# Hardness of parameterized CLIQUE?

(Asked by: username_0 on 2010-09-18)

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](http://en.wikipedia.org/wiki/Tur%C3%A1n_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.

**Tags:** cc.complexity-theory, np, parameterized-complexity, clique
> **Comments:**
> **username_2**: interesting question !  
> **username_3**: Is p a real number between 0 and 1, or can p be a function of t?  
> **username_0**: @Robin: I haven't specified, both would be interesting.  
> **username_4**: 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? :-)  
> **username_4**: Off topic: Could someone with enough reputation add a pointer to http://fpt.wikidot.com/ in the tag wiki for the parameterized-complexity tag here : http://cstheory.stackexchange.com/tags/parameterized-complexity/info ?  
> **username_2**: done. check the tag wiki.  
> **username_0**: @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.  
> **username_1**: for an example of a proof of this for the special case you mention, p=1/2, called the "central slice", shown NP complete, see P.E. Dunne. The complexity of central slice functions. Theoretical Computer Science (44) 1986 pp 247-257. the author shows a similar result for SAT.  
> **username_1**: note also this is exactly the [Erdos-Renyi random graph model](http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model).  

---

## 2 answers

### Answer by username_6 on 2010-09-19. Score: 14 | Accepted answer

I assume that the number $\left\lceil p \binom{t}{2} \right\rceil$ in the definition of the problem CLIQUE*p* is exactly equal to the number of edges in the graph, unlike gphilip’s comment to the question.

The problem CLIQUE*p* 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 *k*2≥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(*n**s*) 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 *n*≥*s*≥*k*, 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(*n**k*−1) time, which is polynomial in *n* for every *p*. The case 3 is possible because if *n*≥*s*≥*k*, 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 K*n*,…,*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/*k*2, 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 K*n*,…,*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 *n*2(*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.

> **Comments:**
> **username_0**: 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?  
> **username_6**: @András Salamon: Done.  

---

### Answer by username_5 on 2010-09-19. Score: 15

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.


---

