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

  • $\begingroup$ Wasnt this asked before? i remember seeing something like that not a long time ago. You should check that out, it might have the answer you are looking for! $\endgroup$ – nir shahar May 31 '20 at 11:57
  • $\begingroup$ No it wasnt. i looked for it all over google and this site and haven't found anything that helps me $\endgroup$ – nickname May 31 '20 at 11:58
  • $\begingroup$ cs.stackexchange.com/questions/126446/exact2is-question here is a similar question, although there is no answer for it $\endgroup$ – nir shahar May 31 '20 at 11:59
  • $\begingroup$ I saw it,but its not the same as i asked $\endgroup$ – nickname May 31 '20 at 11:59
  • $\begingroup$ It looks like "Exact2IS ={G has exactly 2 independent sets}" should have been "Exact2IS ={G has exactly 2 independent sets of size k}, given some fixed k". Otherwise, we can consider independent sets of size 1. $\endgroup$ – John L. Jun 1 '20 at 12:20

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.

  • $\begingroup$ Thanks ,ill try :) $\endgroup$ – nickname May 31 '20 at 12:50

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!

  • $\begingroup$ But i dont have a control over which independent set the algorithm finds.here i can find some independent set in O(1) qnd also check if there is one $\endgroup$ – nickname May 31 '20 at 12:21
  • $\begingroup$ I mean that if i run the algorithm that finds IS twice it might find the same IS..and i f ill do as i said it ill just check if there are at least 2 and not exactly 2 $\endgroup$ – nickname May 31 '20 at 12:23
  • $\begingroup$ Take a look at Yuval's answer. Its just better than my solution $\endgroup$ – nir shahar May 31 '20 at 12:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.