6
$\begingroup$

The usual way of translating the maximum clique problem into a decision problem is to ask "does there exist a clique of size $\ge k$ in $G$?" Clearly this problem is in NP (and is NP-hard).

Another possible way of making it into a decision problem would be:

Instance: Graph $G=(V,E)$ and vertex $v\in V$.
Question: Does there exist a clique $C\subseteq V$ in $G$ that contains $v$ and is of maximum cardinality among cliques?

If P = NP, this problem is polynomial-time solvable. The problem is also contained in $\Sigma_2^p$ (does there exist a clique such that all other cliques are not bigger?). Has its precise complexity been studied?

(Very similar questions can of course also be asked about vertex cover, dominating set, independent set and the like).

$\endgroup$
5
$\begingroup$

I do not recall having seen this precise problem before, but it does have a Cook reduction (polynomial-time Turing reduction) to $k$-Clique:

Let $Y$ be an oracle for $k$-Clique. On input $(G,v)$:

  1. Determine the maximum clique size $\omega(G)$ via at most $log_{2}(n)$ calls to $Y$ using binary search.
  2. Create $G'$ by removing all vertices $u \neq v$ where $uv \notin E(G)$ (i.e. $V(G') = N[v]$).
  3. Determine $\omega(G')$ using $Y$ and binary search.
  4. If $\omega(G') = \omega(G)$ answer YES, otherwise answer NO.

This puts it in $\Delta_{2}^{P} = P^{NP} = P^{SAT}$, a refinement of your observation.

As there are $O(\log{}n)$ calls to the oracle, we can squash containment a little further; the problem is in $\Delta_{2}^{P}[O(\log{}n)] = P^{NP}[O(\log{}n)] = P^{SAT}[O(\log{}n)]$.

[Thanks here to Ricky Demer] If $P=NP$, then $P^{NP} = P^{P} = P$, so you are correct about the polynomial time solvability in this case (contrary to my original, now edited, musings).

So perhaps the problem is $P^{NP}[O(\log{}n)]$-complete, it shouldn't be (as Dominik observed in his answer) $P^{NP}$-complete. I have tried to use the results of Theorem 3.5 from Krentel's paper to construct a reduction, but unless $P^{NP}$ is low for itself (which I don't think it is, but don't know), this has been without luck. (If it is low for itself, then I have a marvellous proof, sadly there are no margins here to put it in.)

$\endgroup$
  • $\begingroup$ This is very interesting, thank you. There seem to be few $\Delta_2^p$-complete problems around, but I'll have a look into the richer $\text{FP}^{\text{NP}}$-complete function-problem landscape. $\endgroup$ – Dominik Peters Aug 24 '15 at 10:12
  • $\begingroup$ @DominikPeters, following your answer, and the paper you linked, I refined the observations a little. From Thm 3.5, there's a Church reduction using $P^{NP}$ oracles from the clique problem, but this doesn't really help unless, as I say in the answer, $P^{NP}$ is low for itself. $NP$ is low for $P^{NP}$, but that seems to be the limit I can find. $\endgroup$ – Luke Mathieson Aug 28 '15 at 6:55
  • $\begingroup$ I don't really understand this answer but it's probably offtopic, so I posted a new question: cs.stackexchange.com/questions/45635/… $\endgroup$ – Albert Hendriks Aug 28 '15 at 7:38
  • $\begingroup$ @Luke: Presumably since $NP \subseteq P^{NP}$, we have $\Sigma_2^p = NP^{NP} \subseteq (P^{NP})^{P^{NP}}$ so that we don't have $P^{NP} =(P^{NP})^{P^{NP}}$ unless the polynomial hierarchy collapses. Thanks for all your help! For the actual application I have in mind, I don't care too much where exactly between $NP$ and $P^{NP}[\log n]$ this problem lies, but I am still curious. $\endgroup$ – Dominik Peters Aug 28 '15 at 21:57
  • 1
    $\begingroup$ The problem is in fact complete for $P^{NP}[\log n]$, as can be seen by reducing from a similar problem about being a member of a min vertex cover, proved complete in this paper: sciencedirect.com/science/article/pii/S0304397505005785 $\endgroup$ – Dominik Peters Feb 27 '17 at 22:28
3
$\begingroup$

For what it's worth, here is a reduction showing NP-hardness. As regards $\Delta_2^p$-completeness, I'm not too optimistic, since one complete problem for this class is "given a formula, does its lexicographically maximal satisfying assignment set the last variable to true?" which seems harder than this problem.

We reduce from 3SAT. Let a formula $\phi'$ with $m-1$ clauses be given; add a fresh variable $x$ and add the one-literal clause $x$; this forces $x$ to be true. Thus we obtain a formula $\phi$ with $m$ clauses which is satisfiable if and only if $\phi'$ is.

Next we construct the graph $G$, which up to an extra component is identical to the graph used in Karp's original reduction showing that CLIQUE is NP-hard. Take a vertex $\ell$ for each literal occurrence in $\phi$. Include an edge between literal occurrences $\ell_1$ and $\ell_2$ if and only if (a) the occurrences are in different clauses, and (b) $\ell_1$ and $\ell_2$ are not contradictory (i.e. are negations of each other). Further, add a disjoint copy of the complete graph $K_m$ of $m$ vertices. This completes the description of $G$. As special vertex $v$ use the single literal occurrence of $x$.

Suppose the formula is satisfiable. Note first that there cannot be a clique among the literals of size larger than $m$ since every clique can contain at most 1 vertex per clause. Of course, among $K_m$, there is also no clique larger than $m$. Now take a satisfying assignment of $\phi$, and pick one true literal per clause. Since these literals cannot be contradictory, this forms a clique of size $m$, and includes the vertex $v$; it is of maximum cardinality $m$.

Suppose there is a maximum-cardinality clique in $G$ containing $v$. Then from the presence of $K_m$ in $G$, this clique must have size at least $m$. From what we said before, it can't have size larger than $m$, so it is of size exactly $m$. The clique thus chooses one literal per clause, and we can set them all true in a contradiction-free assignment. Hence $\phi$ is satisfiable.

$\endgroup$
  • $\begingroup$ Nice reduction! We might be able to put something together from that paper as well. $\endgroup$ – Luke Mathieson Aug 28 '15 at 6:00

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.