  A binary VCSP is a general framework for the minimization problem of a
function represented as the sum of unary and binary cost functions. An
important line of VCSP research is to investigate what functions can be solved
in polynomial time. Cooper and \v{Z}ivn\'{y} classified the tractability of
binary VCSP instances according to the concept of "triangle," and showed that
the only interesting tractable case is the one induced by the joint winner
property (JWP). Recently, Iwamasa, Murota, and \v{Z}ivn\'{y} made a link
between VCSP and discrete convex analysis, showing that a function satisfying
the JWP can be transformed into a function represented as the sum of two
quadratic M-convex functions, which can be minimized in polynomial time via an
M-convex intersection algorithm if the value oracle of each M-convex function
is given. In this paper, we give an algorithmic answer to a natural question:
What binary finite-valued CSP instances can be represented as the sum of two
quadratic M-convex functions and can be solved in polynomial time via an
M-convex intersection algorithm? We solve this problem by devising a
polynomial-time algorithm for obtaining a concrete form of the representation
in the representable case. Our result presents a larger tractable class of
binary finite-valued CSPs, which properly contains the JWP class.

Discrete Mathematics;Combinatorics