Complexity of "given a graph $G$ with vertex $v$, is there a maximum clique containing $v$"?

Question

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).

Answer 1

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.)

Answer 2

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.