Suppose i have a graph $G=(V,E)$ with $|V|=n$. Furthermore suppose i give you a maximum independent set $\mathcal{I}$ in $G$. Now suppose i obtain a new graph $G'$ from $G$ by removing a single vertex $v \in \mathcal{I}$ from $V$. Now of course $\alpha(G') \in \{|\mathcal{I}|,|\mathcal{I}|-1\}$ but can we say more? Is it an NP-hard to find a maximum independent set in $G'$?
1
-
3$\begingroup$ Have you thought about joining an arbitrary graph $G$ to an independent set of size $k$ by adding in all the cross edges? That doesn't instantly tell you that it's NP-hard, but it seems like the right thing to look at $\endgroup$– Ben BarberCommented Jan 5, 2017 at 11:06
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Suppose that $G$ is obtained from the complete bipartite graph with parts of size $n/2$ by adding some edges in each part. Then a maximum independent set lies in one part or the other, so determining $\alpha(G')$ requires solving the maximum independent set problem in the part disjoint from $\mathcal{I}$. So this is definitely NP-complete.
$\begingroup$
$\endgroup$
Following the suggestion in Ben Barber's comment, any algorithm for solving your problem (of finding a maximum independent set in $G'$) can be used to find a maximum independent set in any finite graph.
Let G be a graph of order $n.$ For $0\le k\le n$ let $G_k$ be a graph of order $n+k$ obtained by adding to $G$ an independent set $\mathcal I_k$ of $k$ new vertices, and adding edges joining all the vertices in $\mathcal I_k$ to all the vertices of $G.$
Since $\mathcal I_n$ is a maximum independent set in $G_n,$ we can use your algorithm to find a maximum independent set in $G_{n-1}.$ If the maximum independent set that we find in $G_{n-1}$ is $\mathcal I_{n-1},$ we use the algorithm again to find a maximum independent set in $G_{n-2},$ and so on. Eventually we will find a maximum independent set of some $G_{k}$ which is contained in $V(G).$
