An agreement supertree of a collection of unrooted phylogenetic trees T ₁, T ₂,...,T _k with leaf sets is an unrooted tree T with leaf set such that each tree T _i is an induced subtree of T. In some cases, there may be no possible agreement supertrees of a set of trees, in other cases there may be exponentially many. We present polynomial time algorithms for computing an optimal agreement supertree, if one exists, of a bounded number of binary trees. The criteria of optimality can be one of four standard phylogenetic criteria: binary character compatibility; maximum summed quartet weight; ordinary least squares; and minimum evolution. The techniques can be used to search an exponentially large number of trees in polynomial time.