Document Open Access Logo

Hybrid VCSPs with Crisp and Valued Conservative Templates

Author Rustem Takhanov

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2017.65.pdf
  • Filesize: 474 kB
  • 13 pages

Document Identifiers

Author Details

Rustem Takhanov

Cite As Get BibTex

Rustem Takhanov. Hybrid VCSPs with Crisp and Valued Conservative Templates. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 65:1-65:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ISAAC.2017.65

Abstract

A constraint satisfaction problem (CSP) is a problem of computing a homomorphism R -> G between two relational structures, e.g. between two directed graphs.
Analyzing its complexity has been a very fruitful research direction, especially for fixed template CSPs (or, non-uniform CSPs), denoted CSP(G),
in which the right side structure G is fixed and the left side structure R is unconstrained. 

Recently, the hybrid setting, written CSP_H(G), where both sides are restricted simultaneously, attracted some attention.
It assumes that R is taken from a class of relational structures H (called the structural restriction) that additionally is closed under inverse homomorphisms. The last property allows to exploit an algebraic machinery that has been developed for fixed template CSPs. The key concept that connects hybrid CSPs with fixed-template CSPs is the so called lifted language. Namely, this is a constraint language G_R that can be constructed from an input R. The tractability of the language G_R for any input R from H is a necessary condition for the tractability of the hybrid problem.

In the first part we investigate templates G for which the latter condition is not only necessary, but also is sufficient. We call such templates G widely tractable. For this purpose, we construct from G a new finite relational structure G' and define a maximal structural restriction H_0 as a class of structures homomorphic to G'.
For the so called strongly BJK templates that probably captures all templates, we prove that wide tractability is equivalent to the tractability of CSP_{H_0}(G).
Our proof is based on the key observation that R is homomorphic to G' if and only if the core of G_R is preserved by a Siggers polymorphism.
Analogous result is shown for conservative valued CSPs.

Subject Classification

Keywords
  • constraint satisfaction problem
  • polymorphisms
  • algebraic approach
  • lifted language
  • hybrid CSPs
  • closed under inverse homomorphisms

Metrics

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

References

  1. L. Barto and M. Kozik. New conditions for Taylor varieties and CSP. In Proceedings of the 25th Annual IEEE Symposium on Logic in Computer Science, LICS 2010, 11-14 July 2010, Edinburgh, United Kingdom, pages 100-109, 2010. Google Scholar
  2. Manuel Bodirsky and Víctor Dalmau. Datalog and constraint satisfaction with infinite templates. In Proceedings of the 23rd Annual Conference on Theoretical Aspects of Computer Science, STACS'06, pages 646-659, Berlin, Heidelberg, 2006. Springer-Verlag. Google Scholar
  3. A. Bulatov. A dichotomy theorem for constraint satisfaction problems on a 3-element set. Journal of the ACM, 53(1):66-120, 2006. Google Scholar
  4. A. Bulatov. Complexity of conservative constraint satisfaction problems. ACM Transactions on Computational Logic, 12(4), 2011. Article 24. Google Scholar
  5. A. Bulatov, A. Krokhin, and A. Jeavons. Classifying the Complexity of Constraints using Finite Algebras. SIAM Journal on Computing, 34(3):720-742, 2005. Google Scholar
  6. Andrei A. Bulatov. A dichotomy theorem for nonuniform csps. CoRR, abs/1703.03021, 2017. URL: http://arxiv.org/abs/1703.03021.
  7. J. Bulín, D. Delic, M. Jackson, and T. Niven. On the reduction of the CSP dichotomy conjecture to digraphs. In Christian Schulte, editor, CP, volume 8124 of Lecture Notes in Computer Science, pages 184-199. Springer, 2013. Google Scholar
  8. Stephen A. Cook. The complexity of theorem-proving procedures. In Proceedings of the Third Annual ACM Symposium on Theory of Computing, STOC '71, pages 151-158, New York, NY, USA, 1971. ACM. Google Scholar
  9. Martin C. Cooper and Stanislav Živný. Hybrid tractability of valued constraint problems. Artificial Intelligence, 175(9-10):1555-1569, 2011. Google Scholar
  10. Jia Deng, Nan Ding, Yangqing Jia, Andrea Frome, Kevin Murphy, Samy Bengio, Yuan Li, Hartmut Neven, and Hartwig Adam. Large-scale object classification using label relation graphs. In Computer Vision - ECCV 2014 - 13th European Conference, Zurich, Switzerland, September 6-12, 2014, Proceedings, Part I, pages 48-64, 2014. Google Scholar
  11. 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
  12. Martin J. Green and David A. Cohen. Domain permutation reduction for constraint satisfaction problems. Artificial Intelligence, 172(8):1094 - 1118, 2008. Google Scholar
  13. Gregory Gutin, Arash Rafiey, Anders Yeo, and Michael Tso. Level of repair analysis and minimum cost homomorphisms of graphs. Discrete Applied Mathematics, 154(6):881-889, 2006. Google Scholar
  14. Pavol Hell and Jaroslav Nešetřil. On the complexity of h-coloring. Journal of Combinatorial Theory, Series B, 48(1):92 - 110, 1990. Google Scholar
  15. P. Jeavons, A. Krokhin, and S. Živný. The complexity of valued constraint satisfaction. Bulletin of the EATCS, 113:21-55, 2014. Google Scholar
  16. Peter Jeavons. On the algebraic structure of combinatorial problems. Theor. Comput. Sci., 200(1-2):185-204, June 1998. Google Scholar
  17. Philippe Jégou. Decomposition of domains based on the micro-structure of finite constraint-satisfaction problems. In Richard Fikes and Wendy G. Lehnert, editors, AAAI, pages 731-736. AAAI Press / The MIT Press, 1993. Google Scholar
  18. Keith Kearnes, Petar Marković, and Ralph McKenzie. Optimal strong Mal'cev conditions for omitting type 1 in locally finite varieties. Algebra Univers., 72(1):91-100, 2014. Google Scholar
  19. Sanjeev Khanna, Nathan Linial, and Shmuel Safra. On the hardness of approximating the chromatic number. Combinatorica, 20(3):393-415, 2000. Google Scholar
  20. V. Kolmogorov and S. Živný. The complexity of conservative valued CSPs. Journal of the ACM, 60(2), 2013. Article 10. Google Scholar
  21. Vladimir Kolmogorov, Michal Rolinek, and Rustem Takhanov. Effectiveness of structural restrictions for hybrid csps. In Proceedings of 26th International Symposium, (ISAAC 2015), pages 566-577. Springer Berlin Heidelberg, 2015. Google Scholar
  22. Vladimir Kolmogorov and Ramin Zabih. What energy functions can be minimized via graph cuts? In Proceedings of the 7th European Conference on Computer Vision-Part III, ECCV '02, pages 65-81, London, UK, UK, 2002. Springer-Verlag. Google Scholar
  23. M. Maróti and R. McKenzie. Existence theorems for weakly symmetric operations. Algebra universalis, 59(3-4):463-489, October 2008. Google Scholar
  24. Arash Rafiey, Jeff Kinne, and Tomás Feder. Dichotomy for digraph homomorphism problems. CoRR, abs/1701.02409, 2017. URL: http://arxiv.org/abs/1701.02409.
  25. T. J. Schaefer. The Complexity of Satisfiability Problems. In Proceedings of the 10th Annual ACM Symposium on Theory of Computing (STOC'78), pages 216-226. ACM, 1978. Google Scholar
  26. M. H. Siggers. A strong Mal'cev condition for locally finite varieties omitting the unary type. Algebra universalis, 64(1-2):15-20, October 2010. Google Scholar
  27. Jacobus Stephanus Swarts. The complexity of digraph homomorphisms: Local tournaments, injective homomorphisms and polymorphisms. PhD thesis, University of Victoria, Canada, 2008. Google Scholar
  28. Rustem S. Takhanov. A dichotomy theorem for the general minimum cost homomorphism problem. In In Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS), pages 657-668, 2010. Google Scholar
  29. Johan Thapper and Stanislav Zivny. Sherali-adams relaxations for valued csps. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, pages 1058-1069, 2015. Google Scholar
  30. Dmitriy Zhuk. The proof of CSP dichotomy conjecture. CoRR, abs/1704.01914, 2017. URL: http://arxiv.org/abs/1704.01914.
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