1
$\begingroup$

Consider a m-by-n binary matrix A. Given only an m-dimensional vector of its row sums (R) and an n-dimensional vector of its column sums (C), is there an efficient (ie. polynomial time) algorithm that determines which elements of A must be 1 and which elements of A must be 0?

A trivial example: if R = {2,1,2} and C = {1,1,3}, then

$$ A = \begin{bmatrix} ? & ? & 1 \\ 0 & 0 & 1 \\ ? & ? & 1 \\ \end{bmatrix} $$

$\endgroup$
2
  • 2
    $\begingroup$ Yes: Sort vectors, put ones in left-up corner, unshuffle. Unknowns come from repetitions (and hence multiple ways of unshuffling). $\endgroup$ – Radu GRIGore Apr 26 '12 at 13:42
  • $\begingroup$ Could you elaborate? What's the mechanism for placing ones and for unshuffling? And what about zeros? $\endgroup$ – Special Touch Apr 26 '12 at 16:49
2
$\begingroup$

The answer is yes. The basic idea is to determine whether there is a matrix $A$ with $A_{i, j} = 0$ and one with $A_{i, j} = 1$. If both answers are yes, then $A_{i, j}$ cannot be determined. otherwise you will know what it is.

  1. Consider such a problem: Given $r$ (row sum) and $c$ (column sum), how to determine whether there is a solution or not?

This problem can be solved by network flow algorithm. Imagine a bipartite graph $G$ whose two disjoint vertex sets are $S$ and $T$. Each vertex in $S$ corresponds to a row in $A$ (so $|S| = n$), and each vertex in $T$ corresponds to a column in $A$ (so $|T| = m$). The network $N$ can be constructed as follows:

  • Add edge between source and each $s_i$ in $S$ with capacity $r_i$.
  • Add edge $E_{i, j}$ between each node $s_i$ in $S$ and $t_j$ in $T$ with capacity $1$.
  • Add edge between each $t_j$ in $T$ and sink with capacity $c_j$.

Find the maxflow in $N$. All edges form source are full iff there is a binary matrix A whose row sum is $r$ and column sum is $c$. And flow in $E_{i, j}$ equals to the value of $A_{i, j}$. It can be found in poly time.

  1. Consider how to find the answer when some $A_{i, j}$ is determined.

We can also construct a network $N$ as above and change the upper and lower bound of corresponding $E_{i, j}$. If you want to find whether there is solution with $A_{i, j} = v$, you can change the upper and lower bound to $v$. You should run this algorithm $2nm$ times to find whether each $A_{i, j}$ can be $0$ or $1$.

PS: The first problem can also be solved by a theorem called "Gale-Ryser Theorem". But I've no idea how to modify it to solve the second one.

$\endgroup$
1
  • 1
    $\begingroup$ Great explanation. This is a great starting point. Now I can focus on improving the time complexity. Thanks for your help. $\endgroup$ – Special Touch Apr 30 '12 at 5:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.