For a weight function \(w:V_1\times V_2\rightarrow Z^+\)  the weight of \(M\)  is defined as \(w(M) := \sum _{(x, y)\in M} w(u, v)\) .
The problem of finding a maximum weight Tai mapping
is known to be NP-complete ([1]}) and MAX SNP-hard ([2]}).
Hence, different integer linear programming (ILP) based algorithms have been proposed to compute such a mapping ([3]}, [4]}, [5]}, [6]}).
A naive ILP formulation [5]} contains a constraint for each pair of edges \((x,x^{\prime }), (y, y^{\prime })\in V_1\times V_2\)  such (REF ) does not hold, giving rise to \(O(nm)\)  variables and \(O(n^2m^2)\)  constraints, where \(n\)  and \(m\)  are the number of nodes of the two input trees, and thus does not allow to practically solve even moderate-sized instances ([3]}, [5]}).
In [6]} the authors therefore divide the problem
into \(O(nm)\)  subproblems with \(O(n+m)\)  constraints each, by utilizing a dynamic programming approach from [11]}.
In [4]}, on the other hand, the authors introduced two classes of valid inequalities of the Tai mapping polytope, crossing edges clique constraints and semi-independent clique constraints, and use them as cutting planes in a branch-and-bound scheme. Their implementation achieved a 13-fold speed-up compared to the naive ILP in experiments on perturbed human single-cell data.
Here, we derive a class of valid inequalities that generalize both types of previously introduced clique constraints. We formalize them as
special classes of anti Tai mappings defined as follows.
