This is a computer science interview question I heard from a friend and we can't seem to figure it out. Basically, given a square matrix of 0s and 1s, you can remove any 1 one at a time, but only if at the current time there is another 1 in the same row or column as the 1 to be removed. What is an algorithm to calculate the maximum number of 1s that can be removed for any such matrix?
I suspect this has something to do with graph theory (treating the matrix as an adjacency matrix) or possibly linear algebra, but I'm not certain. Any advice is appreciated.
We did figure out the following: treating the matrix as a directed graph, where a 1 at (i,j) indicates an edge from i to j, then we can remove an edge from the graph iff after removing the edge there would still be an edge from i to another vertex OR there would still be a vertex from j to another vertex. So we want to remove the greatest number of edges (where we count a bidirectional edge as two different edges, one in each direction).
Let each matrix entry of value $1$ be a node in an undirected graph $G$, so that the number of nodes $|G|$ is the number of $1$s in the matrix. Two nodes are joined by an edge if the two $1$s they represent lie on the same column or the same row. Let $C$ be the number of connected components of $G$.
On one hand, since the last node to be removed in each connected component must have an adjacent $1$, at least one node in each component is not removable. Therefore the number of removable nodes is $\le |G|-C$.
On the other hand, since every connected component has a spanning tree, if we keep removing the leaf nodes in the spanning tree until only the root node remains, $|G|-C$ nodes will be removed from the graph.
Thus the maximum removable nodes is $|G|-C$.
As for how to decompose an undirected graph into connected component or how to find a spanning tree for each component, please consult any textbook on graph theory.