I was looking to solve this reduction, but I dont see how to construct the new graph. It seems very simple but I'm not capable of do it.

I give you the complete explanation about this reduction.

We consider a variant of the independent set problem which we shall call, Independent Set with a Fixed Node, in which the input contains additionally a vertex $u$ and it is required that the independent set contains $u$.


As I understand, your problem is a decision problem defined as such:

Independant set with fixed vertex (ISFV):

  • Input: a graph $G = (V, E)$, a vertex $u \in V$, an integer $k$.
  • Question: is there an independent set of size $k$ containing $u$?

Independent set (IS) is defined as:

  • Input: a graph $G = (V, E)$, an integer $k$.
  • Question: is there an independent set of size $k$?

Suppose you can solve ISFV. Then you can solve IS by running ISFV for each $u\in V$ and checking if the answer is yes for any $u\in V$. Since there are a polynomial number of vertices, the reduction is indeed polynomial.

Another way to do it is to construct the graph $G' = (V\cup\{u\}, E)$ (adding a vertex with no other edge), and check ISFV with $G'$, $u$ and $k + 1$, since the vertex $u$ can always be added to an independent set.

  • $\begingroup$ Yeah u are right, but the solution has to be without post processing. I need to find a way to solve the reduction creating a new graph and return the answer of the oracle using this same new graph. $\endgroup$ – Aleix Marti Rodriguez Apr 5 at 23:46
  • $\begingroup$ @AleixMartiRodriguez I edited my answer. $\endgroup$ – Nathaniel Apr 5 at 23:53

Suppose that we are given a graph $G$ and want to know whether it has an independent set of size $k$ containing $u$. Such an independent set cannot contain any neighbor of $u$, and so it is not hard to check that $G$ contains such an independent set iff the graph obtained by removing $u$ and all of its neighbors contains an independent set of size $k-1$.

We can also reduce in the other direction by adding a dummy vertex which is disconnected from the rest of the graph.

  • $\begingroup$ When you say, adding a dummy vertex, has to be the same vertex u, or could be any other named vertex? $\endgroup$ – Aleix Marti Rodriguez Apr 6 at 15:03
  • $\begingroup$ Whatever is needed for the proof to go through. $\endgroup$ – Yuval Filmus Apr 6 at 15:03

Your Answer

