Do you know this problem of deciding whether a given 0-1 matrix contains k pairwise disjoint “column-paths”?

Question

Problem: $X$
Instance: A $m\times n$ 0-1 Matrix $A$, $k \in \mathbb{N}$.
Question: Does $A$ contain $k$ pairwise disjoint "column-paths"?

A column-path starts in the first column, ends in the last one and traverses only 1-entries. It may visit any row at most once. Any 1 may be visited once only, by any path.

Example:

$ A = \begin{pmatrix} a_{00} & a_{01} & a_{02} \\ a_{10} & a_{11} & a_{12} \\ a_{20} & a_{21} & a_{22} \\ a_{30} & a_{31} & a_{32} \\ \end{pmatrix} = \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \\ \end{pmatrix} $

$A$ contains the paths $(a_{10},a_{01},a_{22})$, $(a_{10},a_{01},a_{32})$, $(a_{10},a_{31},a_{22})$ and $(a_{20},a_{01},a_{32})$. Since there are (only) 2 disjoint paths, i.e. the last 2, $(A,2) \in X$.

It is easy to see, that this problem reduces to set packing. It does not work so easily the other way around, because the set packing instance may be too "restrictive".

Any idea what kind of problem this is?

Answer 1

(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 & Vygen (2008): Combinatorial Optimization—Theory and Algorithms, 4th edition, Chapter 12.