<p><em>(from comments, per request)</em></p>

<p>Here is a sketch of a polynomial-time solution.</p>

<p>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).</p>

<p>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 <a href="http://en.wikipedia.org/wiki/Hall%27s_marriage_theorem">Hall's theorem</a> there are also $k$ disjoint $U$-saturating matchings.</p>

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

<hr>

<p>Some background:</p>

<p>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 <a href="http://en.wikipedia.org/wiki/Matching_%28graph_theory%29">matching</a> in the usual sense. For more information on (simple) $k$-matchings and algorithms for finding them, see, for example:</p>

<ul>
<li>Korte &amp; Vygen (2008): <em>Combinatorial Optimization—Theory and Algorithms</em>, 4th edition, Chapter 12.</li>
</ul>

CC BY-SA 3.0
2012-05-27T20:20:39.640Z
2012-05-27T20:20:39.640Z
Jukka Suomela
<blockquote>
  <p>Problem: $X$ <br>
  Instance: A $m\times n$ 0-1 Matrix $A$,  $k \in \mathbb{N}$. <br>
  Question: Does $A$ contain $k$ pairwise disjoint "column-paths"? <br></p>
</blockquote>

<p>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.</p>

<p>Example:</p>

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

<p>$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$.</p>

<p>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".</p>

<p>Any idea what kind of problem this is?</p>

CC BY-SA 3.0
2012-05-20T00:13:36.327Z
I think this might be more suitable for [cs.se] but I am not sure. Btw, please have a look at our [FAQ].
Kaveh
CC BY-SA 3.0
2012-05-20T00:21:14.617Z
@Kaveh: To me this looks like a good question for this site.
Jukka Suomela
CC BY-SA 3.0
2012-05-20T00:36:16.190Z
@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 [tag: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
CC BY-SA 3.0
2012-05-20T01:29:25.280Z
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
CC BY-SA 3.0
2012-05-20T11:32:48.997Z
@JukkaSuomela That looks like an answer because you classified it as a problem in P.
Joshua Herman
CC BY-SA 3.0
2012-05-20T12:21:20.677Z
@JoshuaHerman: Yes, but I am reluctant to post it as an answer, as the moderators do not seem to think that the question itself is appropriate here.
Jukka Suomela
CC BY-SA 3.0
2012-05-27T02:47:19.403Z
I'd say go for it, @JukkaSuomela
Suresh Venkat
<cc.complexity-theory><reference-request><np-hardness>
Do you know this problem of deciding whether a given 0-1 matrix contains k pairwise disjoint “column-paths”?
muede
# Do you know this problem of deciding whether a given 0-1 matrix contains k pairwise disjoint “column-paths”?

(Asked by: username_0 on 2012-05-19)

> 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?

**Tags:** cc.complexity-theory, reference-request, np-hardness

> **Comments:**
> **username_1**: I think this might be more suitable for [cs.se] but I am not sure. Btw, please have a look at our [FAQ].  
> **username_2**: @username_1: To me this looks like a good question for this site.  
> **username_1**: @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 [tag: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.  
> **username_2**: 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).  
> **username_3**: @JukkaSuomela That looks like an answer because you classified it as a problem in P.  
> **username_2**: @JoshuaHerman: Yes, but I am reluctant to post it as an answer, as the moderators do not seem to think that the question itself is appropriate here.  
> **username_4**: I'd say go for it, @JukkaSuomela  

---

## 1 answers

### Answer by username_2 on 2012-05-27. Score: 6

*(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](http://en.wikipedia.org/wiki/Hall%27s_marriage_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](http://en.wikipedia.org/wiki/Matching_%28graph_theory%29) 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.


---

