# Reduction from Independent Set with fixed vertex to Independent Set

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.

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.

• 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. – Aleix Marti Rodriguez Apr 5 at 23:46
• @AleixMartiRodriguez I edited my answer. – 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.

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