The Maximum Isomorphic Agreement Subtree (MIT) problem is one of the simplest versions of the Maximum Interval Weight Agreement Subtree method (MIWT) which is used to compare phylo-genies. More precisely MIT allows to provide a subset of the species such that the exact distances between species in such subset is preserved among all evolutionary trees considered. In this paper, the approximation complexity of the MIT problem is investigated, showing that it cannot be approximated in polynomial time within factor log(delta) n for any delta > 0 unless NP subset of or equal to DTIME(2(poly log n)) for instances containing three trees. Moreover, we show that such result can be strengthened whenever in stances of the MIT problem can contain an arbitrary number of trees, since MIT shares the same approximation lower bound of MAX CLIQUE

Bonizzoni, P., DELLA VEDOVA, G., Mauri, G. (2000). Approximating the Maximum Isomorphic Agreement Subtree Is Hard. In Combinatorial Pattern Matching, 11th Annual Symposium (pp.119-128) [10.1007/3-540-45123-4_12].

Approximating the Maximum Isomorphic Agreement Subtree Is Hard

BONIZZONI, PAOLA;DELLA VEDOVA, GIANLUCA;MAURI, GIANCARLO
2000

Abstract

The Maximum Isomorphic Agreement Subtree (MIT) problem is one of the simplest versions of the Maximum Interval Weight Agreement Subtree method (MIWT) which is used to compare phylo-genies. More precisely MIT allows to provide a subset of the species such that the exact distances between species in such subset is preserved among all evolutionary trees considered. In this paper, the approximation complexity of the MIT problem is investigated, showing that it cannot be approximated in polynomial time within factor log(delta) n for any delta > 0 unless NP subset of or equal to DTIME(2(poly log n)) for instances containing three trees. Moreover, we show that such result can be strengthened whenever in stances of the MIT problem can contain an arbitrary number of trees, since MIT shares the same approximation lower bound of MAX CLIQUE
No
paper
Maximum Isomorphic Agreement Subtree
English
Annual Symposium on Combinatorial Pattern Matching (CPM 2000) JUN 21-23
3-540-67633-3
Bonizzoni, P., DELLA VEDOVA, G., Mauri, G. (2000). Approximating the Maximum Isomorphic Agreement Subtree Is Hard. In Combinatorial Pattern Matching, 11th Annual Symposium (pp.119-128) [10.1007/3-540-45123-4_12].
Bonizzoni, P; DELLA VEDOVA, G; Mauri, G
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/32168
Citazioni
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 4
Social impact