Mezei, Balázs F.; Wrochna, Marcin; Živný, Stanislav PTAS for sparse general-valued CSPs. (English) Zbl 07753165 ACM Trans. Algorithms 19, No. 2, Article No. 14, 31 p. (2023). MSC: 68-XX PDFBibTeX XMLCite \textit{B. F. Mezei} et al., ACM Trans. Algorithms 19, No. 2, Article No. 14, 31 p. (2023; Zbl 07753165) Full Text: DOI arXiv
Krokhin, Andrei; Opršal, Jakub; Wrochna, Marcin; Živný, Stanislav Topology and adjunction in promise constraint satisfaction. (English) Zbl 07672224 SIAM J. Comput. 52, No. 1, 38-79 (2023). MSC: 68Q17 68Q25 68R05 05C15 PDFBibTeX XMLCite \textit{A. Krokhin} et al., SIAM J. Comput. 52, No. 1, 38--79 (2023; Zbl 07672224) Full Text: DOI arXiv
Ciardo, Lorenzo; Živný, Stanislav CLAP: a new algorithm for promise CSPs. (English) Zbl 07672223 SIAM J. Comput. 52, No. 1, 1-37 (2023). MSC: 68Q25 68R01 90C05 PDFBibTeX XMLCite \textit{L. Ciardo} and \textit{S. Živný}, SIAM J. Comput. 52, No. 1, 1--37 (2023; Zbl 07672223) Full Text: DOI arXiv
Brandts, Alex; Živný, Stanislav Beyond PCSP (1-in-3, NAE). (English) Zbl 07629147 Inf. Comput. 289, Part A, Article ID 104954, 14 p. (2022). MSC: 68Qxx PDFBibTeX XMLCite \textit{A. Brandts} and \textit{S. Živný}, Inf. Comput. 289, Part A, Article ID 104954, 14 p. (2022; Zbl 07629147) Full Text: DOI
Carbonnel, Clément; Romero, Miguel; Živný, Stanislav The complexity of general-valued constraint satisfaction problems seen from the other side. (English) Zbl 07470541 SIAM J. Comput. 51, No. 1, 19-69 (2022). MSC: 68Q25 68R01 03B70 90C05 PDFBibTeX XMLCite \textit{C. Carbonnel} et al., SIAM J. Comput. 51, No. 1, 19--69 (2022; Zbl 07470541) Full Text: DOI arXiv
Focke, Jacob; Goldberg, Leslie Ann; Roth, Marc; Živný, Stanislav Counting homomorphisms to \(K_4\)-minor-free graphs, modulo 2. (English) Zbl 07436465 SIAM J. Discrete Math. 35, No. 4, 2749-2814 (2021). MSC: 68R10 05C60 68Q17 68Q25 PDFBibTeX XMLCite \textit{J. Focke} et al., SIAM J. Discrete Math. 35, No. 4, 2749--2814 (2021; Zbl 07436465) Full Text: DOI arXiv
Groot Koerkamp, Ragnar; Živný, Stanislav On rainbow-free colourings of uniform hypergraphs. (English) Zbl 1517.05127 Theor. Comput. Sci. 885, 69-76 (2021). MSC: 05C65 05C15 05C80 PDFBibTeX XMLCite \textit{R. Groot Koerkamp} and \textit{S. Živný}, Theor. Comput. Sci. 885, 69--76 (2021; Zbl 1517.05127) Full Text: DOI arXiv
Matl, Gregor; Živný, Stanislav Using a Min-Cut generalisation to go beyond Boolean surjective VCSPs. (English) Zbl 1494.68202 Algorithmica 82, No. 12, 3492-3520 (2020). MSC: 68R10 68R07 PDFBibTeX XMLCite \textit{G. Matl} and \textit{S. Živný}, Algorithmica 82, No. 12, 3492--3520 (2020; Zbl 1494.68202) Full Text: DOI arXiv
Bulatov, Andrei A.; Živný, Stanislav Approximate counting CSP seen from the other side. (English) Zbl 1499.68238 Rossmanith, Peter (ed.) et al., 44th international symposium on mathematical foundations of computer science, MFCS 2019, Aachen, Germany, August 26–30, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 138, Article 60, 14 p. (2019). MSC: 68R07 08A70 68Q25 68Q27 PDFBibTeX XMLCite \textit{A. A. Bulatov} and \textit{S. Živný}, LIPIcs -- Leibniz Int. Proc. Inform. 138, Article 60, 14 p. (2019; Zbl 1499.68238) Full Text: DOI arXiv
Matl, Gregor; Živný, Stanislav Beyond Boolean surjective VCSPs. (English) Zbl 07559161 Niedermeier, Rolf (ed.) et al., 36th international symposium on theoretical aspects of computer science, STACS 2019, March 13–16, 2019, Berlin, Germany. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 126, Article 52, 15 p. (2019). MSC: 68Qxx PDFBibTeX XMLCite \textit{G. Matl} and \textit{S. Živný}, LIPIcs -- Leibniz Int. Proc. Inform. 126, Article 52, 15 p. (2019; Zbl 07559161) Full Text: DOI
Focke, Jacob; Goldberg, Leslie Ann; Živný, Stanislav The complexity of counting surjective homomorphisms and compactions. (English) Zbl 1429.05143 SIAM J. Discrete Math. 33, No. 2, 1006-1043 (2019). MSC: 05C60 05C30 PDFBibTeX XMLCite \textit{J. Focke} et al., SIAM J. Discrete Math. 33, No. 2, 1006--1043 (2019; Zbl 1429.05143) Full Text: DOI
Cohen, David A.; Cooper, Martin C.; Jeavons, Peter G.; Živný, Stanislav Binary constraint satisfaction problems defined by excluded topological minors. (English) Zbl 1408.68130 Inf. Comput. 264, 12-31 (2019). MSC: 68T20 05C83 68Q25 PDFBibTeX XMLCite \textit{D. A. Cohen} et al., Inf. Comput. 264, 12--31 (2019; Zbl 1408.68130) Full Text: DOI arXiv Link
Krokhin, Andrei; Zivny, Stanislav The complexity of valued CSPs. (English) Zbl 1482.68165 Krokhin, Andrei (ed.) et al., The constraint satisfaction problem: complexity and approximability, Dagstuhl seminar 15301, July 2015. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. Dagstuhl Follow-Ups 7, 233-266 (2017). MSC: 68R07 68Q25 68Q27 90C27 PDFBibTeX XMLCite \textit{A. Krokhin} and \textit{S. Zivny}, Dagstuhl Follow-Ups 7, 233--266 (2017; Zbl 1482.68165) Full Text: DOI
Cooper, Martin C.; Zivny, Stanislav Hybrid tractable classes of constraint problems. (English) Zbl 1482.68107 Krokhin, Andrei (ed.) et al., The constraint satisfaction problem: complexity and approximability, Dagstuhl seminar 15301, July 2015. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. Dagstuhl Follow-Ups 7, 113-135 (2017). MSC: 68Q25 68R05 90C27 PDFBibTeX XMLCite \textit{M. C. Cooper} and \textit{S. Zivny}, Dagstuhl Follow-Ups 7, 113--135 (2017; Zbl 1482.68107) Full Text: DOI
Cohen, David A.; Cooper, Martin C.; Jeavons, Peter G.; Krokhin, Andrei; Powell, Robert; Živný, Stanislav Binarisation for valued constraint satisfaction problems. (English) Zbl 1477.68121 SIAM J. Discrete Math. 31, No. 4, 2279-2300 (2017). MSC: 68Q25 08A70 68Q17 PDFBibTeX XMLCite \textit{D. A. Cohen} et al., SIAM J. Discrete Math. 31, No. 4, 2279--2300 (2017; Zbl 1477.68121) Full Text: DOI arXiv
Fulla, Peter; Živný, Stanislav On planar valued CSPs. (English) Zbl 1370.68125 J. Comput. Syst. Sci. 87, 104-118 (2017). MSC: 68Q25 68R10 PDFBibTeX XMLCite \textit{P. Fulla} and \textit{S. Živný}, J. Comput. Syst. Sci. 87, 104--118 (2017; Zbl 1370.68125) Full Text: DOI arXiv
Thapper, Johan; Živný, Stanislav Necessary conditions for tractability of valued CSPs. (English) Zbl 1347.08009 SIAM J. Discrete Math. 29, No. 4, 2361-2384 (2015). MSC: 08A70 68Q25 68Q17 PDFBibTeX XMLCite \textit{J. Thapper} and \textit{S. Živný}, SIAM J. Discrete Math. 29, No. 4, 2361--2384 (2015; Zbl 1347.08009) Full Text: DOI arXiv
Fulla, Peter; Živný, Stanislav A Galois connection for valued constraint languages of infinite size. (English) Zbl 1440.68115 Halldórsson, Magnús M. (ed.) et al., Automata, languages, and programming. 42nd international colloquium, ICALP 2015, Kyoto, Japan, July 6–10, 2015. Proceedings. Part I. Berlin: Springer. Lect. Notes Comput. Sci. 9134, 517-528 (2015). MSC: 68Q25 06A15 08A40 08A70 PDFBibTeX XMLCite \textit{P. Fulla} and \textit{S. Živný}, Lect. Notes Comput. Sci. 9134, 517--528 (2015; Zbl 1440.68115) Full Text: DOI
Kolmogorov, Vladimir; Thapper, Johan; Živný, Stanislav The power of linear programming for general-valued CSPs. (English) Zbl 1456.68059 SIAM J. Comput. 44, No. 1, 1-36 (2015). MSC: 68Q25 68Q17 68R07 90C05 90C27 PDFBibTeX XMLCite \textit{V. Kolmogorov} et al., SIAM J. Comput. 44, No. 1, 1--36 (2015; Zbl 1456.68059) Full Text: DOI arXiv
Kolmogorov, Vladimir; Živný, Stanislav The complexity of conservative valued CSPs. (English) Zbl 1423.68215 Rabani, Yuval (ed.), Proceedings of the 23rd annual ACM-SIAM symposium on discrete algorithms, SODA 2012, Kyoto, Japan, January 17–19, 2012. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 750-759 (2012). MSC: 68Q25 90C27 PDFBibTeX XMLCite \textit{V. Kolmogorov} and \textit{S. Živný}, in: Proceedings of the 23rd annual ACM-SIAM symposium on discrete algorithms, SODA 2012, Kyoto, Japan, January 17--19, 2012. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 750--759 (2012; Zbl 1423.68215) Full Text: Link