see [1]}. It is known that STAB\((G)\) =QSTAB\((G)\)  if and only if the graph \(G\)  is perfect, in which case linear optimization problems over STAB\((G)\)  can be solved in polynomial time [1]}. As the problem of finding a maximum-weight Tai mapping is NP-hard [3]}, it follows that, unless P=NP, the graph \(G\)  defined above is not perfect and furthermore that STAB\((G)\subset \) QSTAB\((G)\) . Heuristically, one can still use the clique constraints in (REF ) in a cutting plane algorithm for solving an integer program for the maximum-weight Tai mapping problem, if it is possible to efficiently solve the corresponding separation problem, which amounts to finding a maximum-weight anti Tai mapping. While it is not known whether such a separation problem is polynomially solvable in general, we manage to answer this question in the affirmative when one of the two trees is a path.
Specifically, we construct a dynamic program to compute the maximum-weight anti Tai mapping for the case where one tree is a path in time \(O(|V_1||V_2|)\) . Furthermore, we define
a semi-independent antimatching (si-antimatching) as a restricted class of an anti Tai mapping and use this to provide a polynomially computable lower bound on the maximum-weight anti Tai mapping in the case of two trees. More precisely,
let \(x\sim x^{\prime }\)  denote that \(x\)  and \(x^{\prime }\)  are on the same root-to-leaf path (“comparable”), i.e. \(x\sim x^{\prime }\)  if \(x\le x^{\prime }\)  or \(x^{\prime }\le x\) .
Otherwise, we say that \(x\)  and \(x^{\prime }\)  are incomparable. A mapping \(M\subseteq V_1\times V_2\)  is a si-antimatching if for any distinct
\((x,y), (x^{\prime }, y^{\prime })\in M\) :
\((x \sim x^{\prime }) \iff (y \lnot \sim y^{\prime })\) 
