Dagstuhl Follow-Ups, Volume 7
Editors: Andrei Krokhin and Stanislav Zivny
Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Shuai Shao and Stanislav Živný. A Strongly Polynomial-Time Algorithm for Weighted General Factors with Three Feasible Degrees. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 57:1-57:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{shao_et_al:LIPIcs.ISAAC.2023.57, author = {Shao, Shuai and \v{Z}ivn\'{y}, Stanislav}, title = {{A Strongly Polynomial-Time Algorithm for Weighted General Factors with Three Feasible Degrees}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {57:1--57:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-289-1}, ISSN = {1868-8969}, year = {2023}, volume = {283}, editor = {Iwata, Satoru and Kakimura, Naonori}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.57}, URN = {urn:nbn:de:0030-drops-193597}, doi = {10.4230/LIPIcs.ISAAC.2023.57}, annote = {Keywords: matchings, factors, edge constraint satisfaction problems, terminal backup problem, delta matroids} }
Published in: Dagstuhl Reports, Volume 12, Issue 5 (2022)
Martin Grohe, Venkatesan Guruswami, Dániel Marx, and Stanislav Živný. The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 22201). In Dagstuhl Reports, Volume 12, Issue 5, pp. 112-130, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@Article{grohe_et_al:DagRep.12.5.112, author = {Grohe, Martin and Guruswami, Venkatesan and Marx, D\'{a}niel and \v{Z}ivn\'{y}, Stanislav}, title = {{The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 22201)}}, pages = {112--130}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2022}, volume = {12}, number = {5}, editor = {Grohe, Martin and Guruswami, Venkatesan and Marx, D\'{a}niel and \v{Z}ivn\'{y}, Stanislav}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.12.5.112}, URN = {urn:nbn:de:0030-drops-174453}, doi = {10.4230/DagRep.12.5.112}, annote = {Keywords: Constraint satisfaction problem (CSP); Computational complexity; Hardness of approximation; Universal algebra; Semidefinite programming} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Tamio-Vesa Nakajima and Stanislav Živný. Linearly Ordered Colourings of Hypergraphs. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 128:1-128:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{nakajima_et_al:LIPIcs.ICALP.2022.128, author = {Nakajima, Tamio-Vesa and \v{Z}ivn\'{y}, Stanislav}, title = {{Linearly Ordered Colourings of Hypergraphs}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {128:1--128:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.128}, URN = {urn:nbn:de:0030-drops-164692}, doi = {10.4230/LIPIcs.ICALP.2022.128}, annote = {Keywords: hypegraph colourings, promise constraint satisfaction, PCSP, polymorphisms, minions, algebraic approach} }
Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)
Benoît Larose, Petar Marković, Barnaby Martin, Daniël Paulusma, Siani Smith, and Stanislav Živný. QCSP on Reflexive Tournaments. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 58:1-58:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{larose_et_al:LIPIcs.ESA.2021.58, author = {Larose, Beno\^{i}t and Markovi\'{c}, Petar and Martin, Barnaby and Paulusma, Dani\"{e}l and Smith, Siani and \v{Z}ivn\'{y}, Stanislav}, title = {{QCSP on Reflexive Tournaments}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {58:1--58:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-204-4}, ISSN = {1868-8969}, year = {2021}, volume = {204}, editor = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.58}, URN = {urn:nbn:de:0030-drops-146392}, doi = {10.4230/LIPIcs.ESA.2021.58}, annote = {Keywords: computational complexity, algorithmic graph theory, quantified constraints, universal algebra, constraint satisfaction} }
Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)
Eden Pelleg and Stanislav Živný. Additive Sparsification of CSPs. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 75:1-75:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{pelleg_et_al:LIPIcs.ESA.2021.75, author = {Pelleg, Eden and \v{Z}ivn\'{y}, Stanislav}, title = {{Additive Sparsification of CSPs}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {75:1--75:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-204-4}, ISSN = {1868-8969}, year = {2021}, volume = {204}, editor = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.75}, URN = {urn:nbn:de:0030-drops-146562}, doi = {10.4230/LIPIcs.ESA.2021.75}, annote = {Keywords: additive sparsification, graphs, hypergraphs, minimum cuts} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Joshua Brakensiek, Venkatesan Guruswami, and Sai Sandeep. Conditional Dichotomy of Boolean Ordered Promise CSPs. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 37:1-37:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{brakensiek_et_al:LIPIcs.ICALP.2021.37, author = {Brakensiek, Joshua and Guruswami, Venkatesan and Sandeep, Sai}, title = {{Conditional Dichotomy of Boolean Ordered Promise CSPs}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {37:1--37:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.37}, URN = {urn:nbn:de:0030-drops-141060}, doi = {10.4230/LIPIcs.ICALP.2021.37}, annote = {Keywords: promise constraint satisfaction, Boolean ordered PCSP, Shapley value, rich 2-to-1 conjecture, random minor} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Alex Brandts and Stanislav Živný. Beyond PCSP(1-in-3, NAE). In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 121:1-121:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{brandts_et_al:LIPIcs.ICALP.2021.121, author = {Brandts, Alex and \v{Z}ivn\'{y}, Stanislav}, title = {{Beyond PCSP(1-in-3, NAE)}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {121:1--121:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.121}, URN = {urn:nbn:de:0030-drops-141902}, doi = {10.4230/LIPIcs.ICALP.2021.121}, annote = {Keywords: promise constraint satisfaction, PCSP, polymorphisms, algebraic approach} }
Published in: LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)
Marcin Wrochna. PACE Solver Description: Sallow: A Heuristic Algorithm for Treedepth Decompositions. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 36:1-36:4, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{wrochna:LIPIcs.IPEC.2020.36, author = {Wrochna, Marcin}, title = {{PACE Solver Description: Sallow: A Heuristic Algorithm for Treedepth Decompositions}}, booktitle = {15th International Symposium on Parameterized and Exact Computation (IPEC 2020)}, pages = {36:1--36:4}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-172-6}, ISSN = {1868-8969}, year = {2020}, volume = {180}, editor = {Cao, Yixin and Pilipczuk, Marcin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.36}, URN = {urn:nbn:de:0030-drops-133391}, doi = {10.4230/LIPIcs.IPEC.2020.36}, annote = {Keywords: treedepth, decomposition, heuristic, weak colouring numbers} }
Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Caterina Viola and Stanislav Živný. The Combined Basic LP and Affine IP Relaxation for Promise VCSPs on Infinite Domains. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 85:1-85:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{viola_et_al:LIPIcs.MFCS.2020.85, author = {Viola, Caterina and \v{Z}ivn\'{y}, Stanislav}, title = {{The Combined Basic LP and Affine IP Relaxation for Promise VCSPs on Infinite Domains}}, booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)}, pages = {85:1--85:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-159-7}, ISSN = {1868-8969}, year = {2020}, volume = {170}, editor = {Esparza, Javier and Kr\'{a}l', Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.85}, URN = {urn:nbn:de:0030-drops-127566}, doi = {10.4230/LIPIcs.MFCS.2020.85}, annote = {Keywords: promise constraint satisfaction, valued constraint satisfaction, convex relaxations, polymorphisms} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Alex Brandts, Marcin Wrochna, and Stanislav Živný. The Complexity of Promise SAT on Non-Boolean Domains. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 17:1-17:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{brandts_et_al:LIPIcs.ICALP.2020.17, author = {Brandts, Alex and Wrochna, Marcin and \v{Z}ivn\'{y}, Stanislav}, title = {{The Complexity of Promise SAT on Non-Boolean Domains}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {17:1--17:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-138-2}, ISSN = {1868-8969}, year = {2020}, volume = {168}, editor = {Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.17}, URN = {urn:nbn:de:0030-drops-124241}, doi = {10.4230/LIPIcs.ICALP.2020.17}, annote = {Keywords: promise constraint satisfaction, PCSP, polymorphisms, algebraic approach, label cover} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Andrei A. Bulatov and Stanislav Živný. Approximate Counting CSP Seen from the Other Side. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 60:1-60:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{bulatov_et_al:LIPIcs.MFCS.2019.60, author = {Bulatov, Andrei A. and \v{Z}ivn\'{y}, Stanislav}, title = {{Approximate Counting CSP Seen from the Other Side}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {60:1--60:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.60}, URN = {urn:nbn:de:0030-drops-110041}, doi = {10.4230/LIPIcs.MFCS.2019.60}, annote = {Keywords: constraint satisfaction, approximate counting, homomorphisms} }
Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Silvia Butti and Stanislav Živný. Sparsification of Binary CSPs. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 17:1-17:8, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{butti_et_al:LIPIcs.STACS.2019.17, author = {Butti, Silvia and \v{Z}ivn\'{y}, Stanislav}, title = {{Sparsification of Binary CSPs}}, booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)}, pages = {17:1--17:8}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-100-9}, ISSN = {1868-8969}, year = {2019}, volume = {126}, editor = {Niedermeier, Rolf and Paul, Christophe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.17}, URN = {urn:nbn:de:0030-drops-102564}, doi = {10.4230/LIPIcs.STACS.2019.17}, annote = {Keywords: constraint satisfaction problems, minimum cuts, sparsification} }
Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Gregor Matl and Stanislav Živný. Beyond Boolean Surjective VCSPs. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 52:1-52:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{matl_et_al:LIPIcs.STACS.2019.52, author = {Matl, Gregor and \v{Z}ivn\'{y}, Stanislav}, title = {{Beyond Boolean Surjective VCSPs}}, booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)}, pages = {52:1--52:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-100-9}, ISSN = {1868-8969}, year = {2019}, volume = {126}, editor = {Niedermeier, Rolf and Paul, Christophe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.52}, URN = {urn:nbn:de:0030-drops-102911}, doi = {10.4230/LIPIcs.STACS.2019.52}, annote = {Keywords: constraint satisfaction problems, valued constraint satisfaction, surjective constraint satisfaction, graph cuts} }
Published in: Dagstuhl Reports, Volume 8, Issue 6 (2019)
Martin Grohe, Venkatesan Guruswami, and Stanislav Zivny. The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 18231). In Dagstuhl Reports, Volume 8, Issue 6, pp. 1-18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@Article{grohe_et_al:DagRep.8.6.1, author = {Grohe, Martin and Guruswami, Venkatesan and Zivny, Stanislav}, title = {{The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 18231)}}, pages = {1--18}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2018}, volume = {8}, number = {6}, editor = {Grohe, Martin and Guruswami, Venkatesan and Zivny, Stanislav}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.8.6.1}, URN = {urn:nbn:de:0030-drops-100251}, doi = {10.4230/DagRep.8.6.1}, annote = {Keywords: Constraint satisfaction problem (CSP); Computational complexity; CSP dichotomy conjecture; Hardness of approximation; Unique games conjecture; Parameterised complexity; Descriptive complexity; Universal algebra; Logic; Semidefinite programming} }
Feedback for Dagstuhl Publishing