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?


1 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.


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.