title: Characterizing compatibility and agreement of unrooted trees via cuts in graphs.
abstract: BACKGROUND
  Deciding whether there is a single tree -a supertree- that summarizes the evolutionary information in a collection of unrooted trees is a fundamental problem in phylogenetics. We consider two versions of this question: agreement and compatibility. In the first, the supertree is required to reflect precisely the relationships among the species exhibited by the input trees. In the second, the supertree can be more refined than the input trees. Testing for compatibility is an NP-complete problem; however, the problem is solvable in polynomial time when the number of input trees is fixed. Testing for agreement is also NP-complete, but it is not known whether it is fixed-parameter tractable. Compatibility can be characterized in terms of the existence of a specific kind of triangulation in a structure known as the display graph. Alternatively, it can be characterized as a chordal graph sandwich problem in a structure known as the edge label intersection graph. No characterization of agreement was known.
  
  
  RESULTS
  We present a simple and natural characterization of compatibility in terms of minimal cuts in the display graph, which is closely related to compatibility of splits. We then derive a characterization for agreement.
  
  
  CONCLUSIONS
  Explicit characterizations of tree compatibility and agreement are essential to finding practical algorithms for these problems. The simplicity of the characterizations presented here could help to achieve this goal.
authors.affiliation: Department of Computer Science, Iowa State University, Ames, Iowa, USA.
authors.forename: Sudheer
authors.initials: S
authors.lastname: Vakati
authors.affiliation: Department of Computer Science, Iowa State University, Ames, Iowa, USA.
authors.forename: David
authors.initials: D
authors.lastname: Fernández-Baca
keywords: Agreement; Chordal graphs; Compatibility; Cuts in graphs; Phylogenies; Supertrees
references.citation: J Comput Biol. 2010 Mar;17(3):383-99
references.pmid: 20377452