| Abstract: |
In a recent article, Nakhleh, Ringe and Warnow introduced perfect
phylogenetic networks---a model of language evolution where languages do not
evolve via clean speciation---and formulated a set of problems for their
accurate reconstruction. Their new methodology assumes networks, rather
than trees, as the correct model to capture the evolutionary history of
natural languages. They proved the NP-hardness of the problem of testing whether
a network is a perfect phylogenetic one for characters exhibiting at least three
states, leaving open the case of binary characters, and gave a straightforward
brute-force parameterized algorithm for the problem of running time O(3kn),
where k is the number of bidirectional edges in the network and n
is its size. In this paper, we first establish the NP-hardness of the binary
case of the problem. Then we provide a more efficient parameterized algorithm
for this case running in time O(2kn). The presented algorithm
is very simple, and utilizes some structural results and elegant operations
developed in this paper that can be useful on their own in the design of
heuristic algorithms for the problem. The analysis phase of the algorithm is
very elegant using amortized techniques to show that the upper bound on the
running time of the algorithm is much tighter than the upper bound obtained
under a conservative worst-case scenario assumption. Our results bear
significant impacts on reconstructing evolutionary histories of
languages--particularly from phonological and morphological character data, most
of which exhibit at most two states (i.e., are binary), as well as on the design
and analysis of parameterized algorithms. |