Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
1  
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
3  
I'd say go for it, @JukkaSuomela –  Suresh Venkat May 27 '12 at 2:47

1 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.
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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