Finding if binary matrix exists given the row and column sums

Question

How to find out if it is possible to contruct a binary matrix with given row and column sums.

Input :

The first row of input contains two numbers 1≤m,n≤1000, the number of rows and columns of the matrix. The next row contains m numbers 0≤ri≤n – the sum of each row in the matrix. The third row contains n numbers 0≤cj≤m – the sum of each column in the matrix.

Output:

Output “YES” if there exists an m-by-n matrix A, with each element either being 0 or 1. Else "NO".

I tried reading about Tomography algorithms but could not figure out an answer as all the papers related to Tomography algorithm is very complicated.

Can someone please help me..

Answer 1

I've successfully implemented randomly generating such matrices for R using a modeling based on network flow. I intend to write up those ideas one day, but haven't found the time yet. Reasearching for that, I read in Randomization of Presence–absence Matrices: Comments and New Algorithms by Miklós and Podani:

The Havel-Hakimi theorem (Havel 1955, Hakimi 1962) states that there exists a matrix X_n,m of 0’s and 1’s with row totals a₀=(a₁, a₂,… , a_n) and column totals b₀=(b₁, b₂,… , b_m) such that b_i ≥ b_i+1 for every 0 < i < m if and only if another matrix X_n−1,m of 0’s and 1’s with row totals a₁=(a₂, a₃,… , a_n) and column totals b₁=(b₁−1, b₂−1,… ,b_a1−1, b_a1+1,… , b_m) also exists.

I guess that should be the best method to recursively decide your question.

Phrased in my own words: Choose any row, remove it from the list of totals. Call that removed number k. Also subtract one from the k columns with larges sums. You obtain a description of a smaller matrix, and recurse. If at any point you don't have k columns with non-zero sums, then no such matrix can exist. Otherwise you can recursively build a matching matrix using the reverse process: take the matrix returned by the recursive call, then add one more row with k ones, placed in the columns from whose counts you originally subtracted one.

Implementation

bool satisfiable(std::vector<int> a, std::vector<int> b) {
  while (!a.empty()) {
    std::sort(b.begin(), b.end(), std::greater<int>());
    int k = a.back();
    a.pop_back();
    if (k > b.size()) return false;
    if (k == 0) continue;
    if (b[k - 1] == 0) return false;
    for (int i = 0; i < k; i++)
      b[i]--;
  }
  for (std::vector<int>::iterator i = b.begin(); i != b.end(); i++)
    if (*i != 0)
      return false;
  return true;
}