Do you know this problem of deciding whether a given 0-1 matrix contains k pairwise disjoint “column-paths”?
(from comments, per request)

Here is a sketch of a polynomial-time solution.

First, interpret matrix $A$ as a bipartite graph $G=(V \cup U,E)$, with $m$ nodes in part $V$ and $n$ nodes in part $U$, $n \le m$. Then column-paths are $U$-saturating matchings, i.e., matchings of size $n$ (each node of $U$ is incident to precisely one edge in the matching).

The union of $k$ such matchings is a simple $k$-matching of size $kn$ (each node of $U$ is "covered" precisely $k$ times). Conversely, if there is a simple $k$-matching of size $kn$, by Hall's theorem there are also $k$ disjoint $U$-saturating matchings.

Hence to solve the problem it is enough to find a maximum-size simple $k$-matching. This is possible in polynomial time.



Some background:

A simple $k$-matching is a subset $M \subseteq E$ such that each node is incident to at most $k$ edges in $M$. A simple $1$-matching is a matching in the usual sense. For more information on (simple) $k$-matchings and algorithms for finding them, see, for example:


Korte &amp; Vygen (2008): Combinatorial Optimization—Theory and Algorithms, 4th edition, Chapter 12.