Drawing (complete) binary tanglegrams: hardness, approximation, fixed-parameter tractability

K. Buchin, M. Buchin, J. Byrka, M. Nöllenburg, Y. Okamoto, R.I. Silveira, A. Wolff

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

13 Citaten (Scopus)
234 Downloads (Pure)

Samenvatting

A 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. Keywords: Binary tanglegram – Crossing minimization – NP-hardness – Approximation algorithm – Fixed-parameter tractability
Originele taal-2Engels
Pagina's (van-tot)309-332
TijdschriftAlgorithmica
Volume62
Nummer van het tijdschrift1-2
DOI's
StatusGepubliceerd - 2012

Vingerafdruk Duik in de onderzoeksthema's van 'Drawing (complete) binary tanglegrams: hardness, approximation, fixed-parameter tractability'. Samen vormen ze een unieke vingerafdruk.

Citeer dit