5
$\begingroup$

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'$?

$\endgroup$
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 Barber
    Jan 5, 2017 at 11:06

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.