Graph-Based Reformulation

For an \(N \times N\) matrix \(A\) whose elements are \(0\) or \(1\), consider a directed graph created from a complete bipartite graph with vertices \((R_1,\dots,R_N), (C_1,\dots,C_N)\) where edges are directed as follows:

• When \(A_{i,j}=1\), direct the edge from \(R_i\) to \(C_j\)
• When \(A_{i,j}=0\), direct the edge from \(C_j\) to \(R_i\)

Furthermore, we say two graphs are similar if for each vertex, the in-degrees and out-degrees are equal between the graphs. We say an edge in a graph is fixed if that edge exists (with the same direction) in all similar graphs.

There is a one-to-one correspondence between such directed \(K_{N,N}\) graphs and \(N \times N\) matrices with elements \(0\) or \(1\), and having a fixed element at row \(i\) column \(j\) is equivalent to having a fixed edge (in either direction) between \(R_i\) and \(C_j\). With this reformulation of the problem in terms of directed graphs, we proceed with our analysis on this graph.

Solution

Consider two similar graphs and examine what remains after removing all edges with the same direction. From the definition of similar graphs, the in-degree and out-degree of each vertex in the remaining graph are equal. This means the remaining graph consists of several cycles. Conversely, for any graph, if we reverse all edges in a cycle, we get a graph that is similar to the original.

Therefore, an edge is not fixed if and only if it is part of a cycle. We can solve the problem using dynamic programming to determine possible combinations of the following values in \(O(N^6)\) (if the constant factor is too large, you can also precompute all cases and hardcode the answers):

• Number of vertices from \((R_1,\dots,R_N)\) already assigned to strongly connected components
• Number of vertices from \((C_1,\dots,C_N)\) already assigned to strongly connected components
• Number of edges included in strongly connected components (i.e., not fixed)

Note that, due to the bipartiteness, when creating a strongly connected component, you need to select at least two vertices each from \((R_1,\dots,R_N)\) and \((C_1,\dots,C_N)\). Conversely, strong connectedness is always achievable if both sides have two or more vertices.

Sample Implementation in C++