Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Shorelines of islands of tractability: Algorithms for parsimony and
  minimum perfect phylogeny haplotyping problems   The problem Parsimony Haplotyping (PH) asks for the smallest set of
haplotypes which can explain a given set of genotypes, and the problem Minimum
Perfect Phylogeny Haplotyping (MPPH) asks for the smallest such set which also
allows the haplotypes to be embedded in a perfect phylogeny, an evolutionary
tree with biologically-motivated restrictions. For PH, we extend recent work by
further mapping the interface between ``easy'' and ``hard'' instances, within
the framework of (k,l)-bounded instances where the number of 2's per column and
row of the input matrix is restricted. By exploring, in the same way, the
tractability frontier of MPPH we provide the first concrete, positive results
for this problem, and the algorithms underpinning these results offer new
insights about how MPPH might be further tackled in the future. In addition, we
construct for both PH and MPPH polynomial time approximation algorithms, based
on properties of the columns of the input matrix. We conclude with an overview
of intriguing open problems in PH and MPPH.

8
The categories of this paper are: hep-ex
14
The categories of this paper are: math-ph
7
The categories of this paper are: hep-th
12
The categories of this paper are: nucl-th
6
The categories of this paper are: astro-ph
37
The categories of this paper are: supr-con
19
The categories of this paper are: eess
33
The categories of this paper are: plasm-ph
20
The categories of this paper are: acc-phys
26
The categories of this paper are: bayes-an
24
The categories of this paper are: dg-ga
15
The categories of this paper are: nucl-ex
30
The categories of this paper are: q-alg
32
The categories of this paper are: atom-ph
35
The categories of this paper are: mtrl-th
22
The categories of this paper are: chao-dyn