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

CC BY-SA 3.0
2014-04-10T21:18:50.000Z
2014-04-10T21:18:50.000Z
Daniel Grier
<p>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$. </p>

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

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

CC BY-SA 3.0
2014-02-13T01:11:29.297Z
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.
Daniel Grier
CC BY-SA 3.0
2014-02-13T13:24:27.373Z
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.
Andras Farago
CC BY-SA 3.0
2014-02-12T23:43:11.950Z
2014-02-12T23:43:11.950Z
Andras Farago
<p>Consider the following problem:</p>

<p><strong>Input:</strong> (G1, G2) where G1 and G2 are undirected graphs</p>

<p><strong>Question:</strong>  Is the size of the max independent set of G1 at least as large as the size of the max independent set of G2?</p>

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

CC BY-SA 3.0
2014-02-12T22:19:44.710Z
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$).
Marzio De Biasi
<cc.complexity-theory>
Complexity of Comparative Independent Set Decision Problem
Daniel Grier
# Complexity of Comparative Independent Set Decision Problem

(Asked by: username_0 on 2014-02-12)

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.

**Tags:** cc.complexity-theory
> **Comments:**
> **username_1**: 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$).  

---

## 2 answers

### Answer by username_0 on 2014-04-10. Score: 2 | Accepted answer

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


---

### Answer by username_2 on 2014-02-12. Score: 1

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.

> **Comments:**
> **username_0**: 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.  
> **username_2**: 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.  

---

