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

Question

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] 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?

Answer 1

No, the intuition doesn't really scale very well, especially not if you want the optimal solution.

The problem is known as Independent Set and is not only NP-complete, but even W[1]-complete.

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.

Another alternative is to use LP rounding for finding the smallest vertex cover. The complement of a vertex cover is an independent set. You can also experiment with using randomized rounding:

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.