%0 Journal Article %1 bbbnosw-dcbth-12 %A Buchin, Kevin %A Buchin, Maike %A Byrka, Jaroslaw %A Nöllenburg, Martin %A Okamoto, Yoshio %A Silveira, Rodrigo I. %A Wolff, Alexander %D 2012 %J Algorithmica %K NP-hardness approximation_algorithm binary_tanglegrams fixed-parameter_tractability gd-info1 graph_drawing myown %N 1--2 %P 309--332 %R 10.1007/s00453-010-9456-3 %T Drawing (Complete) Binary Tanglegrams: Hardness, Approximation, Fixed-Parameter Tractability %V 62 %X 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.

@article{bbbnosw-dcbth-12, abstract = {A \emph{binary tanglegram} is a drawing of a pair \ttree{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. \par 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 \textsc{MaxCut} for which the algorithm of Goemans and Williamson yields a $0.878$-approximation.}, added-at = {2024-02-18T09:53:56.000+0100}, arxiv = {http://arxiv.org/abs/0806.0920}, author = {Buchin, Kevin and Buchin, Maike and Byrka, Jaroslaw and N\"ollenburg, Martin and Okamoto, Yoshio and Silveira, Rodrigo I. and Wolff, Alexander}, biburl = {https://www.bibsonomy.org/bibtex/2790ba3e44de947044ca570be288437c8/awolff}, doi = {10.1007/s00453-010-9456-3}, interhash = {fddc301a40472d551cdc26af416276dd}, intrahash = {790ba3e44de947044ca570be288437c8}, journal = {Algorithmica}, keywords = {NP-hardness approximation_algorithm binary_tanglegrams fixed-parameter_tractability gd-info1 graph_drawing myown}, number = {1--2}, pages = {309--332}, pdf = {http://www1.pub.informatik.uni-wuerzburg.de/pub/wolff/pub/bbbnosw-dcbth-12.pdf}, slides = {http://www1.pub.informatik.uni-wuerzburg.de/pub/wolff/slides/bbbnosw-dcbth-09-slides.ppt}, timestamp = {2024-02-18T12:36:59.000+0100}, title = {Drawing (Complete) Binary Tanglegrams: Hardness, Approximation, Fixed-Parameter Tractability}, volume = 62, year = 2012 }