Computer Science – Computational Geometry
Scientific paper
2008-06-05
Computer Science
Computational Geometry
Journal version
Scientific paper
A \emph{binary tanglegram} is a drawing of a pair 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.
Buchin Kevin
Buchin Maike
Byrka Jaroslaw
Nöllenburg Martin
Okamoto Yoshio
No associations
LandOfFree
Drawing (Complete) Binary Tanglegrams: Hardness, Approximation, Fixed-Parameter Tractability does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Drawing (Complete) Binary Tanglegrams: Hardness, Approximation, Fixed-Parameter Tractability, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Drawing (Complete) Binary Tanglegrams: Hardness, Approximation, Fixed-Parameter Tractability will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-127775