Solving Exact2IS using IS

Question

i encountered the following problem:

Exact2IS ={G has exactly 2 independent sets}

Assuming that given a graph G i can find an independent set how can i check if G has exactly 2 independent sets.

(i can check if a graph contains independent set in O(1) and also find some independent set in O(1))

I was thinking on find some independent set(if there is any) of size k and then remove one vertex from the set and check if the graph still has independent set of size k -after i check i return the vertex to the graph exactly as it was.

The problem my idea check only if a graph G contains at least 2 independent sets and not exactly.

Anyone have an idea how can i check if a graph has exactly 2 independent sets(in polynomial time and given the fact that find and check if there is independent set is O(1))?

Any clues or ideas will be appreciated :) Thanks

Answer 1

First of all, if you can determine whether a graph $G$ contains an independent set of size $k$, then you can also find such a set efficiently. This is known as "search-to-decision reduction". Here is the basic idea. Choose an arbitrary vertex $v$, and remove it. If the graph still has an independent set of size $k$, then keep going. Otherwise, all independent sets of size $k$ contain $v$. Accordingly, remove $v$ and all its neighbors, and find an independent set of size $k-1$ in the remaining graph. In this way, you can recover an independent set of size $k$.

Second, how to check whether a graph contains at least two independent sets of size $k$, assuming $k \geq 2$. First, you determine whether in contains at least one. Suppose that it does, say $I$. If $J$ is any other independent set, then $I \setminus J$ and $J \setminus I$ are both nonempty (since $|I| = |J|$). In particular, if $x \in I \setminus J$ and $y$ is any other vertex in $I$, then even after adding the edge $(x,y)$, the set $J$ will constitute an independent set.

This leads to the following algorithm: for each pair of vertices $x,y \in I$, check whether $G + (x,y)$ contains an independent set of size $k$. If so, this independent set is necessarily different from $I$. Conversely, if an independent set of size $k$ different than $I$ exists, then necessarily it will be an independent set in $G + (x,y)$ for some $x,y \in I$.

Third, how to check whether a graph contains exactly two independent sets of size $k$. This is the same as checking whether a graph contains at least three independent sets. I think that at this point, it's better if you try to generalize the above argument from two to three independent sets. You might get stuck, but you won't know until you try.

Answer 2

If you are allowed to find an IS of size $k$ in $\mathcal O(1)$, then what you have written is almost the solution. just twice find an IS of size $k$, and after that check to see if there still is another one.

But usually, for oracle machines, you are not allowed to find an (in this example) IS within $\mathcal O(1)$ time, and you are only allowed to check if one exists within $\mathcal O(1)$.

I hope this helps!