Abstract
A binary tanglegram is a drawing of a pair
S,T of rooted binary trees whose leaf sets
are in one-to-one correspondence; matching leaves
are connected by inter-tree edges. For
applications, for example, in phylogenetics, it is
essential that both trees are drawn without edge
crossings and that the inter-tree edges have as few
crossings as possible. It is known that finding a
tanglegram with the minimum number of crossings is
NP-hard and that the problem is fixed-parameter
tractable with respect to that number. We prove
that under the Unique Games Conjecture there is no
constant-factor approximation for binary trees. We
show that the problem is NP-hard even if both trees
are complete binary trees. For this case we give an
$O(n^3)$-time 2-approximation and a new, simple
fixed-parameter algorithm. We show that the
maximization version of the dual problem for binary
trees can be reduced to a version of MaxCut
for which the algorithm of Goemans and Williamson
yields a $0.878$-approximation.
Users
Please
log in to take part in the discussion (add own reviews or comments).