patternMinor
Complexity of "given a graph $G$ with vertex $v$, is there a maximum clique containing $v$"?
Viewed 0 times
containingmaximumgraphvertexwithcliquetheregivencomplexity
Problem
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).
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).
Solution
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)$:
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.)
Let $Y$ be an oracle for $k$-Clique. On input $(G,v)$:
- Determine the maximum clique size $\omega(G)$ via at most $log_{2}(n)$ calls to $Y$ using binary search.
- Create $G'$ by removing all vertices $u \neq v$ where $uv \notin E(G)$ (i.e. $V(G') = N[v]$).
- Determine $\omega(G')$ using $Y$ and binary search.
- 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.)
Context
StackExchange Computer Science Q#45499, answer score: 5
Revisions (0)
No revisions yet.