# Finding the Largest Partition of Non-Connected Nodes in a Graph in polynomial time

I have a graph, and I want to determine the largest possible set (or partition) of nodes such that no two nodes within this set have an edge between them. I am looking for an efficient algorithm to solve this problem.

For instance, given the following graph:

1:  2: [1, 3, 5, 6, 4] 3: [2, 4] 4: [3, 5, 6, 2] 5: [4, 2] 6: [4, 2] The largest partition of non-connected nodes would be {1, 3, 5, 6}.

My current approach is brute-force: I generate all combinations of nodes and then verify if any of the nodes within a combination share an edge. This method, however, is not efficient for larger graphs.

Graphically, I intuitively group unconnected nodes together, and as I add nodes to this group, I can easily identify the largest possible set of non-connected nodes. Is there a way to replicate this intuition algorithmically?

You can try the following greedy algorithm: pick the smallest degree neighbor into your solution, delete the neighborhood, and rinse and repeat. Of course this is not guaranteed to give a very good answer, but it does give a solution which is not more than a factor $$1/\Delta$$ smaller than the optimal, where $$\Delta$$ is the maximum degree of the input graph.
LP relaxation for I.S.: maximize $$\sum_{v \in V} x_v$$ constrained to $$x_u + x_v \leq 1$$ for every edge $$uv \in E$$, and $$0 \leq x_v \leq 1$$ for all $$v \in V$$. With randomized rounding, we take the variable $$x_v$$ as the probability of selecting $$v$$ to the solution. Finally clean up the solution by removing arbitrarily endpoints of edges in the solution.