I am working with sparse matrices (not particularly huge, <100Mb) and I want to compute the largest independent set on the bipartite graph $(N,E)$ defined as follows: suppose the matrix is named $A$ and is of size $m \times n$.$m+n$ nodes ($1,\dots,m$ for the rows, $m+1,\dots,m+n$ for the columns)the edge $(i,j) \in E \iff a_{ij} \neq 0$An independent set is then a subset of rows and columns such that they do not intersect.The graph is clearly bipartite (edges are from the set $\{1,\dots,m\}$ to the set $\{m+1,\dots,m+n\}$), and therefore the computation of the largest independent set is definitely simpler than the general case (as suggested also in this other question). This computation is not entirely critical for my work (my thesis, actually) so I would like to use as much code from existing libraries as possible. I tried igraph, but they use a general algorithm for the largest independent set (which is terribly slow for even a matrix of 5MB), and I have yet to try and see if doing explicitly all the passages Maximum Matching > Minimum vertex cover > maximum independent set helps (it depends on their implementation).The fact that I have a bipartite graph definitely helps from the theoretical point of view, so bigger instances are solvable, but yet I have to find a nice library which might work well with big, sparse, bipartite graphs.Do you know any other existing libraries to do this kind of job?
Library for Maximum independent set on a sparse bipartite graph (from sparse matrix)
graph theory