Complexity of Comparative Independent Set Decision Problem

Consider the following problem:

Input: (G1, G2) where G1 and G2 are undirected graphs

Question: Is the size of the max independent set of G1 at least as large as the size of the max independent set of G2?

This seems like a fairly natural question to ask, and yet I have been unable to find a complexity class for which this problem is complete. Does anyone know of such? As a starting point, it is readily seen that the problem is NP-hard and contained in P with access to an NP oracle with log many queries.

• It is also co-NP-hard, indeed given a graph $G_1$ and an integer $k$, using a dum $G_2$ with a max independent set of size $k$ (e.g. a path of length $2k$) you can build a many-one reduction from both the NPC problem "Does $G_1$ contain an independent set of size $\geq k$?" and its complement (swapping $G_1$ and $G_2$). Feb 12 '14 at 22:19

This problem is indeed complete for the class of polynomial time Turing machines with access to an NP oracle with log many queries (also known as $\Theta_2^p$). The result appears in a 2000 FST TCS paper by Spakowski and Vogel titled "$\Theta_2^p$-Completeness: A Classical Approach for New Results." The proof presented there and a proof that I arrived at independently both rely on the $\Theta_2^p$-completeness criterion of Wagner ("Bounded Query Classes" SIAM Journal on Computing archive Volume 19 Issue 5, Oct. 1990).

I seems, your problem is Turing-complete for the class ${\mathsf{P}}^{\mathsf{NP}[O(\log n])]}$. As mentioned in the question, you already know that it falls in this class. To show Turing-completeness, one can notice that taking an independent set of size $l$ for $G_1$ allows us to determine (using the task as an oracle) whether the max independent set in $G_2$ is $\leq l$. Repeating this with binary search for $1\leq l \leq n$, we can determine the $exact$ size of the max independent set in $G_2$.

Apply the above to the graph complements to determine the exact size of the max clique in $G_2$, rather than the independent set. Having determined the size of the max clique, we can decide whether it is divisible by a given number $k$. Then we can invoke the result that deciding whether the max clique size of a graph is divisible by a given number is complete for ${\mathsf{P}}^{\mathsf{NP}[O(\log n])]}$ (see Krentel, "The complexity of optimization problems," J. of Computer and System Sciences, 36(1988/3), pp. 490–509, Theorem 3.5)

While the referenced result of Krentel proves the many-one completeness of the problem in ${\mathsf{P}}^{\mathsf{NP}[O(\log n])]}$, the above reduction only shows Turing-completeness, since in the binary search we have to call the oracle several ($\log n$) times.

• Seems like the straightforward thing of just encoding all NP oracle queries into instances of this problem would be just as good. Also, since this argument can be repeated with any NPC language, it doesn't seem to reveal anything about the power of this language. Feb 13 '14 at 1:11
• You are right, I overlooked that the same argument could be made using, for example, the simpler Independent Set problem (or, for that matter, with any NPC problem). What would certainly be more interesting is to show that this Comparative Independent Set problem is many-one complete for the mentioned class. Feb 13 '14 at 13:24

Your problem is also many-one hard for implications between NP instances.

Reduce the right side of the implication to independent set in any convenient way, and reduce the left side of the implication to independent set in a way that ensures the graph cannot have an independent set larger than the target size. $\:$ (For example, reduce to CNF-SAT and then apply this reduction despite having a general CNF-SAT instance instead of necessarily a 3-SAT instance.) $\:$ Add a number of isolated vertices equal to the difference between the target sizes
to whichever instance's target size was smaller, and increase that instances target size by the
same number. $\:$ That obviously gives an equivalent instance, and makes the resulting target sizes equal. $\:$ If the target size is zero then return the empty instance of your problem,
else add [target size minus one] isolated vertices to the graph corresponding to the instance on
the right side of the implication and connect each of them to all of the vertices that were there
before this sentence, and return with G1 equal to that graph and G2 equal to the other graph.