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

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?

• I think this might be more suitable for Computer Science but I am not sure. Btw, please have a look at our FAQ. – Kaveh May 20 '12 at 0:13
• @Kaveh: To me this looks like a good question for this site. – Jukka Suomela May 20 '12 at 0:21
• @Jukka, the problem I see is that it is stated in a way that doesn't look research level, at least some motivation is needed. If it is an application-of-theory question then it should be stated so and improve to satisfy the requirement: motivation, background, and what has been tried by the author. – Kaveh May 20 '12 at 0:36
• Anyway, here is a sketch of a polynomial-time solution: 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$. The union of $k$ such matchings is a $k$-matching of size $kn$ (each node of $U$ is "covered" precisely $k$ times). Conversely, if there is a $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 $k$-matching (possible in poly-time). – Jukka Suomela May 20 '12 at 1:29
• I'd say go for it, @JukkaSuomela – Suresh Venkat May 27 '12 at 2:47

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.