2010-10-01

# Drawing (Complete) Binary Tanglegrams: Hardness, Approximation, Fixed-Parameter Tractability

## Publication

### Publication

*
Algorithmica
,
Volume onlin
*

A \emph{binary tanglegram} is a pair $<S,T>$ of 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 crossing and that the inter-tree edges have as few crossings as possible. It is known that finding a drawing 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 general binary trees. We show that the problem is hard even if both trees are complete binary trees. For this case we give an $O(n^3)$-time 2-approximation and a new and simple fixed-parameter algorithm. We show that the maximization version of the dual problem for general binary trees can be reduced to a version of \textsc{MaxCut} for which the algorithm of Goemans and Williamson yields a 0.878-approximation.

Additional Metadata | |
---|---|

, , | |

Springer | |

Algorithmica | |

Byrka, J., Buchin, K., Buchin, M., Nollenburg, M., Okamoto, Y., Silveira, R. I., & Wolff, A. (2010). Drawing (Complete) Binary Tanglegrams: Hardness, Approximation, Fixed-Parameter Tractability. Algorithmica, onlin. |

See Also |
---|