Document Open Access Logo

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

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

PDF
Thumbnail PDF

File

LIPIcs.STACS.2018.39.pdf
  • Filesize: 0.59 MB
  • 14 pages

Document Identifiers

Author Details

Hiroshi Hirai
Yuni Iwamasa
Kazuo Murota
Stanislav Zivny

Cite As Get BibTex

Hiroshi Hirai, Yuni Iwamasa, Kazuo Murota, and Stanislav Zivny. Beyond JWP: A Tractable Class of Binary VCSPs via M-Convex Intersection. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 39:1-39:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.STACS.2018.39

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.

Subject Classification

Keywords
  • valued constraint satisfaction problems
  • discrete convex analysis
  • M-convexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. A. A. Bulatov. A dichotomy theorem for nonuniform CSPs. In Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS'17), pages 319-330, 2017. Google Scholar
  2. M. C. Cooper and S. Živný. Hybrid tractability of valued constraint problems. Artificial Intelligence, 175:1555-1569, 2011. Google Scholar
  3. M. C. Cooper and S. Živný. Tractable triangles and cross-free convexity in discrete optimisation. Journal of Artificial Intelligence Research, 44:455-490, 2012. Google Scholar
  4. M. C. Cooper and S. Živný. Hybrid tractable classes of constraint problems, volume 7 of Dagstuhl Follow-Ups Series, chapter 4, pages 113-135. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. Google Scholar
  5. A. W. M. Dress and W. Wenzel. Valuated matroids: A new look at the greedy algorithm. Applied Mathematics Letters, 3(2):33-35, 1990. Google Scholar
  6. A. W. M. Dress and W. Wenzel. Valuated matroids. Advances in Mathematics, 93:214-250, 1992. Google Scholar
  7. G. Gottlob, G. Greco, and F. Scarcello. Tractable optimization problems through hypergraph-based structural restrictions. In Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP'09, Part II), pages 16-30, 2009. Google Scholar
  8. H. Hirai. A geometric study of the split decomposition. Discrete and Computational Geometry, 36:331-361, 2006. Google Scholar
  9. H. Hirai. Discrete convexity and polynomial solvability in minimum 0-extension problems. Mathematical Programming, Series A, 155:1-55, 2016. Google Scholar
  10. H. Hirai, Y. Iwamasa, K. Murota, and S. Živný. A tractable class of binary VCSPs via M-convex intersection. In preparation. Google Scholar
  11. Y. Iwamasa, K. Murota, and S. Živný. Discrete convexity in joint winner property. To appear in Discrete Optimization. Google Scholar
  12. V. Kolmogorov, A. Krokhin, and M. Rolínek. The complexity of general-valued CSPs. SIAM Journal on Computing, 46(3):1087-1110, 2017. Google Scholar
  13. V. Kolmogorov, J. Thapper, and S. Živný. The power of linear programming for general-valued CSPs. SIAM Journal on Computing, 44(1):1-36, 2015. Google Scholar
  14. B. Korte and J. Vygen. Combinatorial Optimization: Theory and Algorithms. Springer, Heidelberg, 5th edition, 2010. Google Scholar
  15. K. Murota. Convexity and Steinitz’s exchange property. Advances in Mathematics, 124:272-311, 1996. Google Scholar
  16. K. Murota. Valuated matroid intersection, I: optimality criteria. SIAM Journal on Discrete Mathematics, 9:545-561, 1996. Google Scholar
  17. K. Murota. Valuated matroid intersection, II: algorithms. SIAM Journal on Discrete Mathematics, 9:562-576, 1996. Google Scholar
  18. K. Murota. Discrete convex analysis. Mathematical Programming, 83:313-371, 1998. Google Scholar
  19. K. Murota. Matrices and Matroids for Systems Analysis. Springer, Heidelberg, 2000. Google Scholar
  20. K. Murota. Discrete Convex Analysis. SIAM, Philadelphia, 2003. Google Scholar
  21. K. Murota. Recent developments in discrete convex analysis. In W. Cook, L. Lovász, and J. Vygen, editors, Research Trends in Combinatorial Optimization, chapter 11, pages 219-260. Springer, Heidelberg, 2009. Google Scholar
  22. K. Murota. Discrete convex analysis: A tool for economics and game theory. Journal of Mechanism and Institution Design, 1(1):151-273, 2016. Google Scholar
  23. A. Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. Springer, Heidelberg, 2003. Google Scholar
  24. S. Živný. The Complexity of Valued Constraint Satisfaction Problems. Springer, Heidelberg, 2012. Google Scholar
  25. D. Zhuk. A proof of CSP dichotomy conjecture. In Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS'17), pages 331-342, 2017. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact