Rotation distance is fixed-parameter tractable. (English) Zbl 1205.68531
Summary: Rotation distance between trees measures the number of simple operations it takes to transform one tree into another. There are no known polynomial-time algorithms for computing rotation distance. In the case of ordered rooted trees, we show that the rotation distance between two ordered trees is fixed-parameter tractable, in the parameter, \(k\), the rotation distance. The proof relies on the kernelization of the initial trees to trees with size bounded by \(5k\).
MSC:
| 68W40 | Analysis of algorithms |
Keywords:
rotation distance; analysis of algorithms; computational complexity; fixed parameter tractabilityReferences:
| [1] | Allen, Benjamin L.; Steel, Mike, Subtree transfer operations and their induced metrics on evolutionary trees, Annals of Combinatorics, 5, 1, 1-15 (2001) · Zbl 0978.05023 |
| [2] | Baril, Jean-Luc; Pallo, Jean-Marcel, Efficient lower and upper bounds of the diagonal-flip distance between triangulations, Information Processing Letters, 100, 4, 131-136 (2006) · Zbl 1185.68845 |
| [3] | Maria Luisa Bonet, Katherine St. John, On the complexity of uSPR distance, in: IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2008, in press; Maria Luisa Bonet, Katherine St. John, On the complexity of uSPR distance, in: IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2008, in press |
| [4] | Bonet, Maria Luisa; John, Katherine St.; Mahindru, Ruchi; Amenta, Nina, Approximating subtree distances between phylogenies, Journal of Computational Biology, 13, 8, 1419-1434 (2006), (electronic) |
| [5] | Bordewich, Magnus; Semple, Charles, On the computational complexity of the rooted subtree prune and regraft distance, Annals of Combinatorics, 8, 409-423 (2004) · Zbl 1059.05035 |
| [6] | Bordewich, Magnus; Semple, Charles, Computing the minimum number of hybridization events for a consistent evolutionary history, Discrete Applied Mathematics, 155, 8, 914-928 (2007) · Zbl 1111.92041 |
| [7] | Cleary, Sean, Restricted rotation distance between binary trees, Information Processing Letters, 84, 3, 333-338 (2002) · Zbl 1042.68036 |
| [8] | Cleary, Sean; Taback, Jennifer, Bounding restricted rotation distance, Information Processing Letters, 88, 5, 251-256 (2003) · Zbl 1178.68174 |
| [9] | Cleary, Sean; Taback, Jennifer, Bounding right-arm rotation distances, International Journal of Algebra and Computation, 17, 2, 369-399 (2007) · Zbl 1179.68105 |
| [10] | Culik, Karel; Wood, Derick, A note on some tree similarity measures, Information Processing Letters, 15, 1, 39-42 (1982) · Zbl 0489.68058 |
| [11] | Rodney G. Downey, Michael R. Fellows, Ulrike Stege, Computational tractability: the view from mars, in: Bulletin of the European Association of Theoretical Computer Science, 1999, pp. 73-97; Rodney G. Downey, Michael R. Fellows, Ulrike Stege, Computational tractability: the view from mars, in: Bulletin of the European Association of Theoretical Computer Science, 1999, pp. 73-97 · Zbl 0941.68577 |
| [12] | Fellows, Michael R., The lost continent of polynomial time: Preprocessing and kernelization, (Proceedings of the 2nd International Workshop on Parameterized and Exact Computation (IWPEC 2006). Proceedings of the 2nd International Workshop on Parameterized and Exact Computation (IWPEC 2006), Lecture Notes in Computer Science, vol. 4169 (2006), Springer) · Zbl 1154.68560 |
| [13] | Guo, Jiong; Niedermeier, Rolf, Invitation to data reduction and problem kernelization, ACM SIGACT NEWS, 38, 1, 31-45 (2007) |
| [14] | Knuth, Donald E., Sorting and Searching, The Art of Computer Programming, vol. 3 (1973), Addison-Wesley: Addison-Wesley Reading, Mass · Zbl 0302.68010 |
| [15] | Pallo, Jean, An efficient upper bound of the rotation distance of binary trees, Information Processing Letters, 73, 3-4, 87-92 (2000) · Zbl 1014.68112 |
| [16] | R. Rogers, On finding shortest paths in the rotation graph of binary trees, in: Proceedings of the Southeastern International Conference on Combinatorics, Graph Theory, and Computing, vol. 137, 1999, pp. 77-95; R. Rogers, On finding shortest paths in the rotation graph of binary trees, in: Proceedings of the Southeastern International Conference on Combinatorics, Graph Theory, and Computing, vol. 137, 1999, pp. 77-95 · Zbl 0968.05047 |
| [17] | Sleator, Daniel D.; Tarjan, Robert E.; Thurston, William P., Rotation distance, triangulations and hyperbolic geometry, Journal of the American Mathematical Society, 1, 3, 647-681 (1988) · Zbl 0653.51017 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
