Beyond JWP: A tractable class of binary VCSPs via M-convex intersection

Conference item

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–Živný 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– Živný made a link between VCSP and discrete convex analysis, showing that a function satisfying the joint winner property can be transformed into a function represented as the sum of two Mconvex 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 VCSP instances can be solved in polynomial time via an M-convex intersection algorithm? We devise a polynomial time algorithm for testing the representability of a given binary VCSP instance as the sum of two M-convex functions, and obtaining a concrete form of the representation in the representable case. Our result presents a larger tractable class of binary VCSPs, which properly contains the JWP class.

Authors: Hirai, H; Iwamasa, Y; Murota, K; Zivny, S

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Leibniz Center for Informatics.
• Host title: 35th International Symposium on Theoretical Aspects of Computer Science
• Journal: 35th International Symposium on Theoretical Aspects of Computer Science
• Publication date: 2018-02-01
• Acceptance date: 2017-12-11
• DOI: 10.4230/LIPIcs.STACS.2018.39
• ISSN: 1868-8969
• Keywords: discrete convex analysis; M-convexity; valued constraint satisfaction problems