Largest disconnected subset of undirected graph

Question

I have an undirected graph G of N vertices represented by an N x N symmetric adjacency matrix A. I want to find the largest subset S of G such that no two vertices in S share an edge. (I'm not sure what the word is for such a subgraph -- totally isolated?)

Here's an example with four vertices:

[[1 0 1 0]
 [0 1 0 0]
 [1 0 1 0]
 [0 0 0 1]]

Here there are two equally good answers: {2, 3, 4} or {1, 2, 4}.

This problem seems to me to be quite similar to linear sum assignment. In particular it reminds me of finding the minimum number of lines needed to cover the zeros in a matrix. Is there a way to formulate this problem as a linear assignment? Ideally I would like to be able to solve this efficiently in code using something like scipy.optimize.linear_sum_assignment.

Thanks!

Answer 1

This is called a maximum independent set. You can solve the problem via integer linear programming as follows. Let binary variable $x_i$ indicate whether node $i$ is selected. The problem is to maximize $\sum_i x_i$ subject to linear constraints $x_i+x_j\le 1$ for all edges $(i,j)$. Equivalently, the problem is to find a maximum clique in the graph complement.