License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2018.39
URN: urn:nbn:de:0030-drops-85042
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8504/
Go to the corresponding LIPIcs Volume Portal

Hirai, Hiroshi ; Iwamasa, Yuni ; Murota, Kazuo ; Zivny, Stanislav

Beyond JWP: A Tractable Class of Binary VCSPs via M-Convex Intersection

pdf-format:
LIPIcs-STACS-2018-39.pdf (0.6 MB)

Abstract

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-Zivny 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-Zivny 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 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 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.

BibTeX - Entry

@InProceedings{hirai_et_al:LIPIcs:2018:8504,
  author =	{Hiroshi Hirai and Yuni Iwamasa and Kazuo Murota and Stanislav Zivny},
  title =	{{Beyond JWP: A Tractable Class of Binary VCSPs via M-Convex Intersection}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{39:1--39:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Rolf Niedermeier and Brigitte Vall{\'e}e},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8504},
  URN =		{urn:nbn:de:0030-drops-85042},
  doi =		{10.4230/LIPIcs.STACS.2018.39},
  annote =	{Keywords: valued constraint satisfaction problems, discrete convex analysis, M-convexity}
}

Keywords: valued constraint satisfaction problems, discrete convex analysis, M-convexity
Collection: 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
Issue Date: 2018
Date of publication: 27.02.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI