1
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
  • $\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
0
$\begingroup$

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.

$\endgroup$
2
  • $\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

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.