P269: Enumeration of all minimal sets of at most $k$ rows the deletion of which leaves a PP matrix

P269: Enumeration of all minimal sets of at most $k$ rows the deletion of which leaves a PP matrix

Input:

A binary $n \times m$ matrix $B$ and a positive integer $k$, where $n > 4k$.

Output:

All minimal sets of at most $k$ rows the deletion of which leaves a PP matrix.

Complexity:

$O(3^k nm)$ time.

Comment:

A PP matrix is a perfect phylogeny matrix.

Reference:

[Damaschke2006] (Bibtex)