Podsześcienny algorytm dla problemu nieważonej odległości edycyjnej pomiędzy nieukorzenionymi drzewami.

Problem odległości edycyjnej między drzewami to naturalne uogólnienie klasycznego problemu odległości edycyjnej między słowami. Mając dane dwa uporządkowane drzewa T i Q z etykietami na krawędziach, odległość edycyjna pomiędzy T a Q jest zdefiniowana jako minimalny sumaryczny koszt operacji, które przekształcają drzewo T w drzewo Q. W jednej operacji możemy skontraktować krawędź, rozdzielić wierzchołek na dwa lub zamienić etykietę na dowolnej krawędzi.Dla ważonej wersji problemu, w której koszt każdej operacji zależy od typu operacji i etykiety na zmienianej krawędzi, znane są algorytmy działające w czasie O(n^3) zarówno dla drzew ukorzenionych jak i dla drzew nieukorzenionych. Istnienie prawdziwie podsześciennego, to jest działającego w czasie O(n^{3-ϵ}) algorytmu jest mało prawdopodobne, ponieważ implikowałoby ono istnienie podsześciennego algorytmu dla problemu APSP. Jednakże Mao pokazał ostatnio, że jeśli założymy, że każda operacja ma koszt jednostkowy, to odległość edycyjna między dwoma ukorzenionymi drzewami może być obliczona w czasie O(n^{2.9546}).W tej pracy pokazujemy jak uogólnić algorytm Mao tak, żeby działał dla drzew nieukorzenionych. Daje nam to pierwszy podsześcienny algorytm dla problemu nieważonej odległości edycyjnej między dwoma nieukorzenionymi drzewami działający w czasie O(n^{(7ω + 15)/(2ω + 6)}) ≤ O(n^{2.9417}), gdzie ω ≤ 2.373 jest wykładnikiem w czasie mnożenia macierzy. Nasz algorytm opiera się na fakcie, że aby obliczyć odległość edycyjną między dwoma nieukorzenionymi drzewami, wystarczy obliczyć odległość edycyjną pomiędzy dowolnym ukorzenieniem pierwszego drzewa a wszystkimi ukorzenieniami drugiego drzewa.

The tree edit distance problem is a natural generalization of the classic string edit distance problem. Given two ordered, edge-labeled trees T and Q, the edit distance between T and Q is defined as the minimum total cost of operations that transform T into Q. In one operation, we can contract an edge, split a vertex into two or change the label of an edge.For the weighted version of the problem, where the cost of each operation depends on the type of the operation and the label on the edge involved, O(n^3) time algorithms are known for both rooted and unrooted trees. The existence of a truly subcubic O(n^{3-ϵ}) time algorithm is unlikely, as it would imply a truly subcubic algorithm for the APSP problem. However, recently Mao showed that if we assume that each operation has a unit cost, then the tree edit distance between two rooted trees can be computed in O(n^{2.9546}) time. In this paper, we show how to adapt Mao's algorithm to make it work for unrooted trees and we show an O(n^{(7ω + 15)/(2ω + 6)}) ≤ O(n^{2.9417}) time algorithm for the unweighted tree edit distance between two unrooted trees, where ω ≤ 2.373 is the matrix multiplication exponent. It is the first known subcubic algorithm for unrooted trees.The main idea behind our algorithm is the fact that to compute the tree edit distance between two unrooted trees, it is enough to compute the tree edit distance between an arbitrary rooting of the first tree and every rooting of the second tree.