  The minimisation problem of a sum of unary and pairwise functions of discrete
variables is a general NP-hard problem with wide applications such as computing
MAP configurations in Markov Random Fields (MRF), minimising Gibbs energy, or
solving binary Valued Constraint Satisfaction Problems (VCSPs).
  We study the computational complexity of classes of discrete optimisation
problems given by allowing only certain types of costs in every triangle of
variable-value assignments to three distinct variables. We show that for
several computational problems, the only non- trivial tractable classes are the
well known maximum matching problem and the recently discovered joint-winner
property. Our results, apart from giving complete classifications in the
studied cases, provide guidance in the search for hybrid tractable classes;
that is, classes of problems that are not captured by restrictions on the
functions (such as submodularity) or the structure of the problem graph (such
as bounded treewidth).
  Furthermore, we introduce a class of problems with convex cardinality
functions on cross-free sets of assignments. We prove that while imposing only
one of the two conditions renders the problem NP-hard, the conjunction of the
two gives rise to a novel tractable class satisfying the cross-free convexity
property, which generalises the joint-winner property to problems of unbounded
arity.
