Boiling down to matching problem

This problem can be considered as the following graph-theory problem.
“We have a graph with \(2N\) vertices \(X_1,\ldots,X_N,Y_1,\ldots,Y_N\) and without edges. For each \((i,j)\) with \(1\leq i \leq N,\ 1 \leq j \leq M\), add an edge from \(X_i\) to \( Y_{A_{i,j}}\) (multiple edges allowed). Determine if this \((N+M)\)-vertex \(NM\)-edge bipartite graph can be decomposed into \(M\) perfect matchings; construct one if it is possible.”

In this formulation, vertex \(X_i\) corresponds to the \(i\)-th row in the original problem, and vertex \(Y_i\) to the number \(k\). A perfect matching expresses an assignment on a column in the original problem, and assigning the edge between \(X_i\) and \(Y_k\) to the \(j\)-th perfect matching means placing number \(k\) to the square at the \(i\)-th row and \(j\)-th column.

Proof that a perfect matching exists

If a perfect matching always exists regardless of \(M\) and \(A_{i,j}\), then one can always obtain \(M\) perfect matching by finding one by one. This follows by induction; once we obtain a perfect matching, we can remove the used edges from the graph to boil down to the same problem with \(M\) reduced by one.

The existence of a perfect matching follows from Hall’s theorem.

Hall’s theorem

We have a bipartite graph with parts \(\{X_1,\dots,X_N\}\) and \(\{Y_1,\ldots,Y_N\}\). Let \(S_i\) be the set of vertices directly connected to \(X_i\). This graph has a perfect matching if and only if \(|\cup_{i\in I}S_i|\geq |I|\) for all subset \(I\) of \(\{1,\ldots,N\}\).

We assert that the graph we are interested in satisfies the condition of Hall’s theorem.

Take any subset \(I\) of \(\{1,\ldots,N\}\). Then, the size of union as a multiset of \(S_i\) (as a multiset) is at most \(|I| M\). Here, since the multiset contains at most \(M\) identical elements, the size as a set is \(|I|\) or greater, which was what we wanted.

Finding a perfect matching

We have seen that Hall’s theorem ensure the existence of a perfect matching. A perfect matching of a bipartite graph can be actually constructed with a flow algorithm fast enough.

Add two vertices \(S\) and \(G\), add directed edges from \(S\) to each \(X_i\) and each \(Y_j\) to \(T\), and direct the existing edges from \(X_i\) to \(Y_j\). If the capacity of each edge is \(1\) and we know a flow from \(S\) to \(T\) of flow \(N\), the edges with a flow form a perfect matching.

The complexity is \(O(V^{0.5}E)\) in case of an \(V\)-vertex \(E\)-edge graph.

By repeatedly finding a perfect match and remove the used edges \(M\) times, we can decompose the graph into \(M\) perfect matchings. The complexity is \(O(\sum_{m\leq M} N^{0.5}(Nm))=O(N^{1.5}M^2)\), which is fast enough.

A faster solution

Decomposing graph into matchings can be considered as an edge-painting problem. It is known that an edge coloring of a regular bipartite graph can be found in an \(O(NM\log NM)\) time, and so can this problem.

For more details on the algorithm, please refer to the following article.

Artcile by 37zigen (Japanese)