最大の合意サブツリー問題は、グラフ理論とコンピュータ科学におけるいくつかの密接に関連する問題のいずれかである。これらの問題のすべてにおいて、${\displaystyle n}$の葉をそれぞれ含む木の集合${\displaystyle T_{1},\ldots ,T_{m}}$が与えられる。これらの木の葉には、${\displaystyle |L|=n}$でいくつかのセット${\displaystyle L}$のラベルが与えられ、同じツリー内に同じラベルを共有する葉のペアはなく、同じツリー内で各リーフのラベルが区別されます。この問題では、${\displaystyle T_{1}\mid S,\ldots ,T_{m}\mid S}$の${\displaystyle L’}$の葉を含む最小スパン・サブツリーがラベルを保存しながら「同じ」であるように、最大​​のサブセット${\displaystyle L’\subset L}$を見つけることを望む。