Maximum number of vertices such that no edge exists between any 2 vertices

Question

Given a graph $G$ and $n$ vertices and $k$ edges. Is there an algorithm that finds the maximum number of vertices such that no edge exists between any vertices in this set?

Answer 1

You can solve the maximum independent set problem via integer linear programming as follows. Let binary decision variable $x_i$ indicate whether node $i\in N$ is selected. The problem is to maximize $\sum_{i\in N} x_i$ subject to $$x_i + x_j \le 1 \quad \text{for all $(i,j)\in E$}.$$ These constraints enforce $(i,j)\in E \implies \lnot(x_i \land x_j)$. That is, if $(i,j)$ is an edge you cannot select both nodes $i$ and $j$.

In practice, integer linear programming is much more efficient than brute force.

Answer 2

Unfortunately, this is NP Hard problem. NP hard problem don't have any efficient polynomial time solution and can be only solved in exponential time. You have to check all possible subsets of vertices, to get maximum independent set. There are approximate algorithms for such problems, which gives close to ideal answer efficiently.