Good morning,
I am really lost in this exercise. I know what they are asking for, but I cannot get a way to solve it or to find a proper defition for each case in order to prove the reduction. Here's the statement.
Consider the following variations of INDEPENDENT SET:
$A$:
input: an encoding $\lfloor{G, k, u}\rfloor$, where $G = (V, E)$ is a graph, $k\in \mathbb{N}$ and $u \in V$.
question: does $G$ have an independent set $X$ of size $k$ such that $u \in X$?
$C:$
input: an encoding $\lfloor{G, k}\rfloor$ of a graph $G$ and a natural number $k \ge 1$.
question: does $G$ have two distinct independent sets of size $k$?
a) Show that $A \le_{P}$ INDEPENDENT SET.
b) Show that INDEPENDENT SET $\le_{P} A$.
c) Show that INDEPENDENT SET $\le_{P} C$.
Need to say: If $G = (V, E)$ is a graph and $X \subseteq V$, we say that $X$ is an INDEPENDENT SET if no edge of $G$ connects two vertices of $X$.
Thank you all!