Document Open Access Logo

Weisfeiler-Leman Invariant Promise Valued CSPs

Authors Libor Barto , Silvia Butti

PDF
Thumbnail PDF

File

LIPIcs.CP.2022.4.pdf
  • Filesize: 0.84 MB
  • 17 pages

Document Identifiers

Author Details

Libor Barto
  • Department of Algebra, Faculty of Mathematics and Physics, Charles University, Prague, Czechia
Silvia Butti
  • Department of Information and Communication Technologies, Universitat Pompeu Fabra, Barcelona, Spain

Funding

  • Barto, Libor: Libor Barto has received funding from the European Research Council (ERC) under the European Unions Horizon 2020 research and innovation programme (Grant Agreement No. 771005, CoCoSym).
  • Butti, Silvia: Silvia Butti was supported by a MICCIN grant PID2019-109137GB-C22 and by a fellowship from "la Caixa" Foundation (ID 100010434). The fellowship code is LCF/BQ/DI18/11660056. This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 713673.

Acknowledgements

The authors are grateful to Victor Dalmau for his valuable comments.

Cite AsGet BibTex

Libor Barto and Silvia Butti. Weisfeiler-Leman Invariant Promise Valued CSPs. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 4:1-4:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.CP.2022.4

Abstract

In a recent line of work, Butti and Dalmau have shown that a fixed-template Constraint Satisfaction Problem is solvable by a certain natural linear programming relaxation (equivalent to the basic linear programming relaxation) if and only if it is solvable on a certain distributed network, and this happens if and only if its set of Yes instances is closed under Weisfeiler-Leman equivalence. We generalize this result to the much broader framework of fixed-template Promise Valued Constraint Satisfaction Problems. Moreover, we show that two commonly used linear programming relaxations are no longer equivalent in this broader framework.

Subject Classification

ACM Subject Classification
  • Theory of computation → Constraint and logic programming
Keywords
  • Promise Valued Constraint Satisfaction Problem
  • Linear programming relaxation
  • Distributed algorithms
  • Symmetric fractional polymorphisms
  • Color refinement algorithm

Metrics

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

Related Versions

References

  1. Libor Barto, Jakub Bulín, Andrei A. Krokhin, and Jakub Opršal. Algebraic approach to promise constraint satisfaction. J. ACM, 68(4):28:1-28:66, 2021. URL: https://doi.org/10.1145/3457606.
  2. Libor Barto, Andrei Krokhin, and Ross Willard. Polymorphisms, and How to Use Them. In Andrei Krokhin and Stanislav Živný, editors, The Constraint Satisfaction Problem: Complexity and Approximability, volume 7 of Dagstuhl Follow-Ups, pages 1-44. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2017. URL: https://doi.org/10.4230/DFU.Vol7.15301.1.
  3. A. A. Bulatov. A dichotomy theorem for nonuniform CSPs. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 319-330, October 2017. URL: https://doi.org/10.1109/FOCS.2017.37.
  4. Silvia Butti and Victor Dalmau. The complexity of the distributed constraint satisfaction problem. In Markus Bläser and Benjamin Monmege, editors, 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021, March 16-19, 2021, Saarbrücken, Germany (Virtual Conference), volume 187 of LIPIcs, pages 20:1-20:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.STACS.2021.20.
  5. Silvia Butti and Víctor Dalmau. Fractional Homomorphism, Weisfeiler-Leman Invariance, and the Sherali-Adams Hierarchy for the Constraint Satisfaction Problem. In Filippo Bonchi and Simon J. Puglisi, editors, 46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021, August 23-27, 2021, Tallinn, Estonia, volume 202 of LIPIcs, pages 27:1-27:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.MFCS.2021.27.
  6. Clément Carbonnel, Miguel Romero, and Stanislav Živný. The complexity of general-valued constraint satisfaction problems seen from the other side. SIAM Journal on Computing, 51(1):19-69, 2022. URL: https://doi.org/10.1137/19M1250121.
  7. Tomás Feder and Moshe Y Vardi. The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory. SIAM Journal on Computing, 28(1):57-104, 1998. Google Scholar
  8. Ferdinando Fioretto, Enrico Pontelli, and William Yeoh. Distributed constraint optimization problems and applications: A survey. J. Artif. Int. Res., 61(1):623-698, January 2018. Google Scholar
  9. Alexander Kazda. Minion homomorphisms give reductions between promise valued CSPs, 2021. In preparation. Google Scholar
  10. Vladimir Kolmogorov, Andrei A. Krokhin, and Michal Rolínek. The complexity of general-valued CSPs. SIAM J. Comput., 46(3):1087-1110, 2017. URL: https://doi.org/10.1137/16M1091836.
  11. Vladimir Kolmogorov, Johan Thapper, and Stanislav Živný. The power of linear programming for general-valued CSPs. SIAM J. Comput., 44(1):1-36, 2015. URL: https://doi.org/10.1137/130945648.
  12. Marcin Kozik. Solving CSPs Using Weak Local Consistency. SIAM Journal on Computing, 50(4):1263-1286, 2021. URL: https://doi.org/10.1137/18M117577X.
  13. Andrei Krokhin and Stanislav Živný. The Constraint Satisfaction Problem: Complexity and Approximability, volume 7. Schloss Dagstuhl, 2017. Google Scholar
  14. Andrei Krokhin and Stanislav Živný. The Complexity of Valued CSPs. In Andrei Krokhin and Stanislav Živný, editors, The Constraint Satisfaction Problem: Complexity and Approximability, volume 7 of Dagstuhl Follow-Ups, pages 233-266. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2017. URL: https://doi.org/10.4230/DFU.Vol7.15301.233.
  15. Gábor Kun. Constraints, MMSNP and expander relational structures. Comb., 33(3):335-347, 2013. URL: https://doi.org/10.1007/s00493-013-2405-4.
  16. Gabor Kun, Ryan O’Donnell, Suguru Tamaki, Yuichi Yoshida, and Yuan Zhou. Linear programming, width-1 CSPs, and robust satisfaction. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS ’12, pages 484-495, New York, NY, USA, 2012. Association for Computing Machinery. URL: https://doi.org/10.1145/2090236.2090274.
  17. AA Leman and B Weisfeiler. A reduction of a graph to a canonical form and an algebra arising during this reduction. Nauchno-Technicheskaya Informatsiya, 2(9):12-16, 1968. Google Scholar
  18. Motakuri V. Ramana, Edward R. Scheinerman, and Daniel Ullman. Fractional isomorphism of graphs. Discrete Mathematics, 132(1):247-265, 1994. URL: https://doi.org/10.1016/0012-365X(94)90241-0.
  19. Edward R Scheinerman and Daniel H Ullman. Fractional graph theory: a rational approach to the theory of graphs. Courier Corporation, 2011. Google Scholar
  20. Alexander Schrijver. Theory of Linear and Integer Programming. John Wiley & Sons, Inc., USA, 1986. Google Scholar
  21. Hanif D. Sherali and Warren P. Adams. A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Discret. Math., 3(3):411-430, 1990. URL: https://doi.org/10.1137/0403036.
  22. Johan Thapper and Stanislav Živný. The power of linear programming for valued CSPs. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 669-678. IEEE Computer Society, 2012. URL: https://doi.org/10.1109/FOCS.2012.25.
  23. Johan Thapper and Stanislav Živný. The complexity of finite-valued CSPs. J. ACM, 63(4):37:1-37:33, 2016. URL: https://doi.org/10.1145/2974019.
  24. Johan Thapper and Stanislav Živný. The Power of Sherali-Adams Relaxations for General-Valued CSPs. SIAM J. Comput., 46(4):1241-1279, 2017. URL: https://doi.org/10.1137/16M1079245.
  25. Caterina Viola and Stanislav Živný. The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains. ACM Trans. Algorithms, 17(3):21:1-21:23, 2021. URL: https://doi.org/10.1145/3458041.
  26. Makoto Yokoo, Toru Ishida, Edmund H Durfee, and Kazuhiro Kuwabara. Distributed constraint satisfaction for formalizing distributed problem solving. In [1992] Proceedings of the 12th International Conference on Distributed Computing Systems, pages 614-621. IEEE, 1992. Google Scholar
  27. Dmitriy Zhuk. A proof of the CSP dichotomy conjecture. J. ACM, 67(5):30:1-30:78, August 2020. URL: https://doi.org/10.1145/3402029.
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 Imprint Privacy Contact