21 Search Results for "Opršal, Jakub"

Document
DOI: 10.4230/LIPIcs.LICS.2026.54
A Categorical Perspective on Constraint Satisfaction: The Wonderland of Adjunctions

Authors: Maximilian Hadek, Tomáš Jakl, and Jakub Opršal

Published in: LIPIcs, Volume 380, 41st Annual Symposium on Logic in Computer Science (LICS 2026)

Abstract
The so-called algebraic approach to the constraint satisfaction problem (CSP) has been a prevalent method of the study of complexity of these problems since early 2000’s. The core of this approach is the notion of polymorphisms which determine the complexity of the problem (up to log-space reductions). In the past few years, a new, more general version of the CSP emerged, the promise constraint satisfaction problem (PCSP), and the notion of polymorphisms and most of the core theses of the algebraic approach were generalised to the promise setting. Nevertheless, recent work also suggests that insights from other fields are immensely useful in the study of PCSPs including algebraic topology. In this paper, we provide an entry point for category-theorists into the study of complexity of CSPs and PCSPs. We show that many standard CSP notions have clear and well-known categorical counterparts. For example, the algebraic structure of polymorphisms can be described as a set-functor defined as a right Kan extension. We provide purely categorical proofs of core results of the algebraic approach including a proof that the complexity only depends on the polymorphisms. Our new proofs are substantially shorter and, from the categorical perspective, cleaner than previous proofs of the same results. Moreover, as expected, they are applicable more widely. We believe that, in particular in the case of PCSPs, category theory brings insights that can help solve some of the current challenges of the field.
Cite as

Maximilian Hadek, Tomáš Jakl, and Jakub Opršal. A Categorical Perspective on Constraint Satisfaction: The Wonderland of Adjunctions. In 41st Annual Symposium on Logic in Computer Science (LICS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 380, pp. 54:1-54:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{hadek_et_al:LIPIcs.LICS.2026.54,
  author =	{Hadek, Maximilian and Jakl, Tom\'{a}\v{s} and Opr\v{s}al, Jakub},
  title =	{{A Categorical Perspective on Constraint Satisfaction: The Wonderland of Adjunctions}},
  booktitle =	{41st Annual Symposium on Logic in Computer Science (LICS 2026)},
  pages =	{54:1--54:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-434-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{380},
  editor =	{Faggian, Claudia 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.LICS.2026.54},
  URN =		{urn:nbn:de:0030-drops-268415},
  doi =		{10.4230/LIPIcs.LICS.2026.54},
  annote =	{Keywords: constraint satisfaction problem, categorical models and logics}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2026.184
Approximating 1-In-3 SAT by Linearly Ordered Hypergraph 3-Colouring Is NP-Hard

Authors: Andrei Krokhin and Danny Vagnozzi

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract
1-in-3 SAT is a classical NP-hard constraint satisfaction problem (CSP). Given a satisfiable instance of 1-in-3 SAT, it is NP-hard to find a satisfying assignment for it, but it may be possible to efficiently find a solution subject to a weaker (not necessarily Boolean) predicate than "1-in-3". There is a conjecture, which we call the Approximate 1-in-3 SAT conjecture, made independently by several researchers, that predicts a dichotomy: for certain choices of weaker predicates the problem becomes tractable and for the remaining choices the task remains NP-hard. Such problems belong to the Promise CSP (PCSP) framework, which studies how one CSP can be approximated by another, in a specific qualitative sense. The Approximate 1-in-3 SAT conjecture is notable because there is no P versus NP-hard dichotomy conjecture for general PCSPs yet (due to insufficient evidence). One specific predicate, corresponding to the problem of linearly ordered 3-colouring of 3-uniform hypergraphs, has been mentioned in several recent papers as an obstacle to further progress in proving the Approximate 1-in-3 SAT conjecture. We prove that the problem for this predicate is NP-hard, as predicted by the conjecture. This completes the proof of the conjecture for predicates on a 3-element domain.
Cite as

Andrei Krokhin and Danny Vagnozzi. Approximating 1-In-3 SAT by Linearly Ordered Hypergraph 3-Colouring Is NP-Hard. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 184:1-184:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{krokhin_et_al:LIPIcs.ICALP.2026.184,
  author =	{Krokhin, Andrei and Vagnozzi, Danny},
  title =	{{Approximating 1-In-3 SAT by Linearly Ordered Hypergraph 3-Colouring Is NP-Hard}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{184:1--184:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.184},
  URN =		{urn:nbn:de:0030-drops-265729},
  doi =		{10.4230/LIPIcs.ICALP.2026.184},
  annote =	{Keywords: Constraint satisfaction, complexity theory}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.3
Maximum And- vs. Even-SAT

Authors: Tamio-Vesa Nakajima and Stanislav Živný

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
A multiset of literals, called a clause, is strongly satisfied by an assignment if no literal evaluates to false. Finding an assignment that maximises the number of strongly satisfied clauses is NP-hard. We present a simple algorithm that finds, given a multiset of clauses that admits an assignment that strongly satisfies ρ of the clauses, an assignment in which at least ρ of the clauses are weakly satisfied, in the sense that an even number of literals evaluate to false. In particular, this implies an efficient algorithm for finding an undirected cut of value ρ in a graph G given that a directed cut of value ρ in G is promised to exist. A similar argument also gives an efficient algorithm for finding an acyclic subgraph of G with ρ edges under the same promise.
Cite as

Tamio-Vesa Nakajima and Stanislav Živný. Maximum And- vs. Even-SAT. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 3:1-3:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{nakajima_et_al:LIPIcs.APPROX/RANDOM.2025.3,
  author =	{Nakajima, Tamio-Vesa and \v{Z}ivn\'{y}, Stanislav},
  title =	{{Maximum And- vs. Even-SAT}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{3:1--3:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.3},
  URN =		{urn:nbn:de:0030-drops-243696},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.3},
  annote =	{Keywords: approximation, promise constraint satisfaction, max and, max even, max cut, max dicut, max acyclic}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.19
On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems

Authors: Ian DeHaan, Neng Huang, and Euiwoong Lee

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
We study minimum cost constraint satisfaction problems (MinCostCSP) through the algebraic lens. We show that for any constraint language Γ which has the dual discriminator operation as a polymorphism, there exists a |D|-approximation algorithm for MinCostCSP(Γ) where D is the domain. Complementing our algorithmic result, we show that any constraint language Γ where MinCostCSP(Γ) admits a constant-factor approximation must have a near-unanimity (NU) polymorphism unless P = NP, extending a similar result by Dalmau et al. on MinCSPs. These results imply a dichotomy of constant-factor approximability for constraint languages that contain all permutation relations (a natural generalization for Boolean CSPs that allow variable negation): either MinCostCSP(Γ) has an NU polymorphism and is |D|-approximable, or it does not have any NU polymorphism and is NP-hard to approximate within any constant factor. Finally, we present a constraint language which has a majority polymorphism, but is nonetheless NP-hard to approximate within any constant factor assuming the Unique Games Conjecture, showing that the condition of having an NU polymorphism is in general not sufficient unless UGC fails.
Cite as

Ian DeHaan, Neng Huang, and Euiwoong Lee. On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 19:1-19:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dehaan_et_al:LIPIcs.APPROX/RANDOM.2025.19,
  author =	{DeHaan, Ian and Huang, Neng and Lee, Euiwoong},
  title =	{{On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{19:1--19:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.19},
  URN =		{urn:nbn:de:0030-drops-243851},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.19},
  annote =	{Keywords: Constraint satisfaction problems, approximation algorithms, polymorphisms}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.83
Three Fundamental Questions in Modern Infinite-Domain Constraint Satisfaction

Authors: Michael Pinsker, Jakub Rydval, Moritz Schöbi, and Christoph Spiess

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
The Feder-Vardi dichotomy conjecture for Constraint Satisfaction Problems (CSPs) with finite templates, confirmed independently by Bulatov and Zhuk, has an extension to certain well-behaved infinite templates due to Bodirsky and Pinsker which remains wide open. We provide answers to three fundamental questions on the scope of the Bodirsky-Pinsker conjecture. Our first two main results provide two simplifications of this scope, one of structural, and the other one of algebraic nature. The former simplification implies that the conjecture is equivalent to its restriction to templates without algebraicity, a crucial assumption in the most powerful classification methods. The latter yields that the higher-arity invariants of any template within its scope can be assumed to be essentially injective, and any algebraic condition characterizing any complexity class within the conjecture closed under Datalog reductions must be satisfiable by injections, thus lifting the mystery of the better applicability of certain conditions over others. Our third main result uses the first one to show that any non-trivially tractable template within the scope serves, up to a Datalog-computable modification of it, as the witness of the tractability of a non-finitely tractable finite-domain Promise Constraint Satisfaction Problem (PCSP) by the so-called sandwich method. This generalizes a recent result of Mottet and provides a strong hitherto unknown connection between the Bodirsky-Pinsker conjecture and finite-domain PCSPs.
Cite as

Michael Pinsker, Jakub Rydval, Moritz Schöbi, and Christoph Spiess. Three Fundamental Questions in Modern Infinite-Domain Constraint Satisfaction. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 83:1-83:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{pinsker_et_al:LIPIcs.MFCS.2025.83,
  author =	{Pinsker, Michael and Rydval, Jakub and Sch\"{o}bi, Moritz and Spiess, Christoph},
  title =	{{Three Fundamental Questions in Modern Infinite-Domain Constraint Satisfaction}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{83:1--83:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.83},
  URN =		{urn:nbn:de:0030-drops-241903},
  doi =		{10.4230/LIPIcs.MFCS.2025.83},
  annote =	{Keywords: (Promise) Constraint Satisfaction Problem, dichotomy conjecture, polymorphism, identity, algebraicity, homogeneity, \omega-categoricity, finite boundedness, Datalog}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.34
Adaptive Query Algorithms for Relational Structures Based on Homomorphism Counts

Authors: Balder ten Cate, Phokion G. Kolaitis, and Arnar Á. Kristjánsson

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
A query algorithm based on homomorphism counts is a procedure to decide membership for a class of finite relational structures using only homomorphism count queries. A left query algorithm can ask the number of homomorphisms from any structure to the input structure and a right query algorithm can ask the number of homomorphisms from the input structure to any other structure. We systematically compare the expressive power of different types of left or right query algorithms, including non-adaptive query algorithms, adaptive query algorithms that can ask a bounded number of queries, and adaptive query algorithms that can ask an unbounded number of queries. We also consider query algorithms where the homomorphism counting is done over the Boolean semiring 𝔹, meaning that only the existence of a homomorphism is recorded, not the precise number of them.
Cite as

Balder ten Cate, Phokion G. Kolaitis, and Arnar Á. Kristjánsson. Adaptive Query Algorithms for Relational Structures Based on Homomorphism Counts. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 34:1-34:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{tencate_et_al:LIPIcs.MFCS.2025.34,
  author =	{ten Cate, Balder and Kolaitis, Phokion G. and Kristj\'{a}nsson, Arnar \'{A}.},
  title =	{{Adaptive Query Algorithms for Relational Structures Based on Homomorphism Counts}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{34:1--34:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.34},
  URN =		{urn:nbn:de:0030-drops-241413},
  doi =		{10.4230/LIPIcs.MFCS.2025.34},
  annote =	{Keywords: Query algorithms, homomorphisms, homomorphism counts, directed graphs, relational structures, Datalog, constraint satisfaction}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.37
New Hardness Results for Low-Rank Matrix Completion

Authors: Dror Chawin and Ishay Haviv

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
The low-rank matrix completion problem asks whether a given real matrix with missing values can be completed so that the resulting matrix has low rank or is close to a low-rank matrix. The completed matrix is often required to satisfy additional structural constraints, such as positive semi-definiteness or a bounded infinity norm. The problem arises in various research fields, including machine learning, statistics, and theoretical computer science, and has broad real-world applications. This paper presents new NP-hardness results for low-rank matrix completion problems. We show that for every sufficiently large integer d and any real number ε ∈ [2^{-O(d)},1/7], given a partial matrix A with exposed values of magnitude at most 1 that admits a positive semi-definite completion of rank d, it is NP-hard to find a positive semi-definite matrix that agrees with each given value of A up to an additive error of at most ε, even when the rank is allowed to exceed d by a multiplicative factor of O (1/(ε²⋅log(1/ε))). This strengthens a result of Hardt, Meka, Raghavendra, and Weitz (COLT, 2014), which applies to multiplicative factors smaller than 2 and to ε that decays polynomially in d. We establish similar NP-hardness results for the case where the completed matrix is constrained to have a bounded infinity norm (rather than be positive semi-definite), for which all previous hardness results rely on complexity assumptions related to the Unique Games Conjecture. Our proofs involve a novel notion of nearly orthonormal representations of graphs, the concept of line digraphs, and bounds on the rank of perturbed identity matrices.
Cite as

Dror Chawin and Ishay Haviv. New Hardness Results for Low-Rank Matrix Completion. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 37:1-37:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chawin_et_al:LIPIcs.MFCS.2025.37,
  author =	{Chawin, Dror and Haviv, Ishay},
  title =	{{New Hardness Results for Low-Rank Matrix Completion}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{37:1--37:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.37},
  URN =		{urn:nbn:de:0030-drops-241448},
  doi =		{10.4230/LIPIcs.MFCS.2025.37},
  annote =	{Keywords: hardness of approximation, low-rank matrix completion, graph coloring}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.121
Maximum Bipartite vs. Triangle-Free Subgraph

Authors: Tamio-Vesa Nakajima and Stanislav Živný

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
Given a (multi)graph G which contains a bipartite subgraph with ρ edges, what is the largest triangle-free subgraph of G that can be found efficiently? We present an SDP-based algorithm that finds one with at least 0.8823 ρ edges, thus improving on the subgraph with 0.878 ρ edges obtained by the classic Max-Cut algorithm of Goemans and Williamson. On the other hand, by a reduction from Håstad’s 3-bit PCP we show that it is NP-hard to find a triangle-free subgraph with (25 / 26 + ε) ρ ≈ (0.961 + ε) ρ edges. As an application, we classify the Maximum Promise Constraint Satisfaction Problem, denoted byMaxPCSP(G, H), for all bipartite G: Given an input (multi)graph X which admits a G-colouring satisfying ρ edges, find an H-colouring of X that satisfies ρ edges. This problem is solvable in polynomial time, apart from trivial cases, if H contains a triangle, and is NP-hard otherwise.
Cite as

Tamio-Vesa Nakajima and Stanislav Živný. Maximum Bipartite vs. Triangle-Free Subgraph. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 121:1-121:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{nakajima_et_al:LIPIcs.ICALP.2025.121,
  author =	{Nakajima, Tamio-Vesa and \v{Z}ivn\'{y}, Stanislav},
  title =	{{Maximum Bipartite vs. Triangle-Free Subgraph}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{121:1--121:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.121},
  URN =		{urn:nbn:de:0030-drops-234987},
  doi =		{10.4230/LIPIcs.ICALP.2025.121},
  annote =	{Keywords: approximation, promise constraint satisfaction, triangle-free subgraphs}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2025.166
Limitations of Affine Integer Relaxations for Solving Constraint Satisfaction Problems

Authors: Moritz Lichter and Benedikt Pago

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We show that various recent algorithms for finite-domain constraint satisfaction problems (CSP), which are based on solving their affine integer relaxations, do not solve all tractable and not even all Maltsev CSPs. This rules them out as candidates for a universal polynomial-time CSP algorithm. The algorithms are ℤ-affine k-consistency, BLP+AIP, BA^{k}, and CLAP. We thereby answer a question by Brakensiek, Guruswami, Wrochna, and Živný [Joshua Brakensiek et al., 2020] whether a constant level of BA^{k}solves all tractable CSPs in the negative: Indeed, not even a sublinear level k suffices. We also refute a conjecture by Dalmau and Opršal [Víctor Dalmau and Jakub Opršal, 2024] (LICS 2024) that every CSP is either solved by ℤ-affine k-consistency or admits a Datalog reduction from 3-colorability. For the cohomological k-consistency algorithm, that is also based on affine relaxations, we show that it correctly solves our counterexample but fails on an NP-complete template.
Cite as

Moritz Lichter and Benedikt Pago. Limitations of Affine Integer Relaxations for Solving Constraint Satisfaction Problems. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 166:1-166:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{lichter_et_al:LIPIcs.ICALP.2025.166,
  author =	{Lichter, Moritz and Pago, Benedikt},
  title =	{{Limitations of Affine Integer Relaxations for Solving Constraint Satisfaction Problems}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{166:1--166:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.166},
  URN =		{urn:nbn:de:0030-drops-235431},
  doi =		{10.4230/LIPIcs.ICALP.2025.166},
  annote =	{Keywords: constraint satisfaction, affine relaxation, promise CSPs, \mathbb{Z}-affine k-consistency, cohomological k-consistency algorithm, Tseitin, graph isomorphism}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2025.158
Restricted CSPs and F-Free Digraph Algorithmics

Authors: Santiago Guzmán-Pro and Barnaby Martin

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
In recent years, much attention has been placed on the complexity of graph homomorphism problems when the input is restricted to ℙ_k-free and ℙ_k-subgraph-free graphs. We consider the directed version of this research line, by addressing the question is it true that digraph homomorphism problems CSP(H) have a P versus NP-complete dichotomy when the input is restricted to ℙ→_k-free (resp. ℙ→_k-subgraph-free) digraphs? Our main contribution in this direction shows that if CSP(H) is NP-complete, then there is a positive integer N such that CSP(H) remains NP-hard even for ℙ→_N-subgraph-free digraphs. Moreover, CSP(H) becomes polynomial-time solvable for ℙ→_{N-1}-subgraph-free acyclic digraphs. We then verify the questions above for digraphs on three vertices and a family of smooth tournaments. We prove these results by establishing a connection between F-(subgraph)-free algorithmics and constraint satisfaction theory. On the way, we introduce restricted CSPs, i.e., problems of the form CSP(H) restricted to yes-instances of CSP(H') - these were called restricted homomorphism problems by Hell and Nešetřil. Another main result of this paper presents a P versus NP-complete dichotomy for these problems. Moreover, this complexity dichotomy is accompanied by an algebraic dichotomy in the spirit of the finite domain CSP dichotomy.
Cite as

Santiago Guzmán-Pro and Barnaby Martin. Restricted CSPs and F-Free Digraph Algorithmics. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 158:1-158:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{guzmanpro_et_al:LIPIcs.ICALP.2025.158,
  author =	{Guzm\'{a}n-Pro, Santiago and Martin, Barnaby},
  title =	{{Restricted CSPs and F-Free Digraph Algorithmics}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{158:1--158:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.158},
  URN =		{urn:nbn:de:0030-drops-235352},
  doi =		{10.4230/LIPIcs.ICALP.2025.158},
  annote =	{Keywords: Digraph homomorphisms, constraint satisfaction problems, subgraph-free algorithmics}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.38
Optimal Inapproximability of Promise Equations over Finite Groups

Authors: Silvia Butti, Alberto Larrauri, and Stanislav Živný

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
A celebrated result of Håstad established that, for any constant ε > 0, it is NP-hard to find an assignment satisfying a (1/|G|+ε)-fraction of the constraints of a given 3-LIN instance over an Abelian group G even if one is promised that an assignment satisfying a (1-ε)-fraction of the constraints exists. Engebretsen, Holmerin, and Russell showed the same result for 3-LIN instances over any finite (not necessarily Abelian) group. In other words, for almost-satisfiable instances of 3-LIN the random assignment achieves an optimal approximation guarantee. We prove that the random assignment algorithm is still best possible under a stronger promise that the 3-LIN instance is almost satisfiable over an arbitrarily more restrictive group.
Cite as

Silvia Butti, Alberto Larrauri, and Stanislav Živný. Optimal Inapproximability of Promise Equations over Finite Groups. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 38:1-38:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{butti_et_al:LIPIcs.ICALP.2025.38,
  author =	{Butti, Silvia and Larrauri, Alberto and \v{Z}ivn\'{y}, Stanislav},
  title =	{{Optimal Inapproximability of Promise Equations over Finite Groups}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{38:1--38:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.38},
  URN =		{urn:nbn:de:0030-drops-234150},
  doi =		{10.4230/LIPIcs.ICALP.2025.38},
  annote =	{Keywords: promise constraint satisfaction, approximation, linear equations}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2025.140
Containment for Guarded Monotone Strict NP

Authors: Alexey Barsukov, Michael Pinsker, and Jakub Rydval

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
Guarded Monotone Strict NP (GMSNP) extends Monotone Monadic Strict NP (MMSNP) by guarded existentially quantified predicates of arbitrary arities. We prove that the containment problem for GMSNP is decidable, thereby settling an open question of Bienvenu, ten Cate, Lutz, and Wolter, later restated by Bourhis and Lutz. Our proof also comes with a 2NEXPTIME upper bound on the complexity of the problem, which matches the lower bound for containment of MMSNP due to Bourhis and Lutz. In order to obtain these results, we significantly improve the state of knowledge of the model-theoretic properties of GMSNP. Bodirsky, Knäuer, and Starke previously showed that every GMSNP sentence defines a finite union of CSPs of ω-categorical structures. We show that these structures can be used to obtain a reduction from the containment problem for GMSNP to the much simpler problem of testing the existence of a certain map called recolouring, albeit in a more general setting than GMSNP; a careful analysis of this yields said upper bound. As a secondary contribution, we refine the construction of Bodirsky, Knäuer, and Starke by adding a restricted form of homogeneity to the properties of these structures, making the logic amenable to future complexity classifications for query evaluation using techniques developed for infinite-domain CSPs.
Cite as

Alexey Barsukov, Michael Pinsker, and Jakub Rydval. Containment for Guarded Monotone Strict NP. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 140:1-140:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{barsukov_et_al:LIPIcs.ICALP.2025.140,
  author =	{Barsukov, Alexey and Pinsker, Michael and Rydval, Jakub},
  title =	{{Containment for Guarded Monotone Strict NP}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{140:1--140:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.140},
  URN =		{urn:nbn:de:0030-drops-235176},
  doi =		{10.4230/LIPIcs.ICALP.2025.140},
  annote =	{Keywords: guarded, monotone, SNP, forbidden patterns, query containment, recolouring, decidability, computational complexity, \omega-categoricity, constraint satisfaction, homogeneity, amalgamation property, Ramsey property, canonical function}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2025.169
Complexity of Approximate Conflict-Free, Linearly-Ordered, and Nonmonochromatic Hypergraph Colourings

Authors: Tamio-Vesa Nakajima, Zephyr Verwimp, Marcin Wrochna, and Stanislav Živný

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
Using the algebraic approach to promise constraint satisfaction problems, we establish complexity classifications of three natural variants of hypergraph colourings: standard nonmonochromatic colourings, conflict-free colourings, and linearly-ordered colourings. Firstly, we show that finding an 𝓁-colouring of a k-colourable r-uniform hypergraph is NP-hard for all constant 2 ≤ k ≤ 𝓁 and r ≥ 3. This provides a shorter proof of a celebrated result by Dinur et al. [FOCS'02/Combinatorica'05]. Secondly, we show that finding an 𝓁-conflict-free colouring of an r-uniform hypergraph that admits a k-conflict-free colouring is NP-hard for all constant 2 ≤ k ≤ 𝓁 and r ≥ 4, except for r = 4 and k = 2 (and any 𝓁); this case is solvable in polynomial time. The case of r = 3 is the standard nonmonochromatic colouring, and the case of r = 2 is the notoriously difficult open problem of approximate graph colouring. Thirdly, we show that finding an 𝓁-linearly-ordered colouring of an r-uniform hypergraph that admits a k-linearly-ordered colouring is NP-hard for all constant 3 ≤ k ≤ 𝓁 and r ≥ 4, thus improving on the results of Nakajima and Živný [ICALP'22/ACM TocT'23].
Cite as

Tamio-Vesa Nakajima, Zephyr Verwimp, Marcin Wrochna, and Stanislav Živný. Complexity of Approximate Conflict-Free, Linearly-Ordered, and Nonmonochromatic Hypergraph Colourings. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 169:1-169:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{nakajima_et_al:LIPIcs.ICALP.2025.169,
  author =	{Nakajima, Tamio-Vesa and Verwimp, Zephyr and Wrochna, Marcin and \v{Z}ivn\'{y}, Stanislav},
  title =	{{Complexity of Approximate Conflict-Free, Linearly-Ordered, and Nonmonochromatic Hypergraph Colourings}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{169:1--169:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.169},
  URN =		{urn:nbn:de:0030-drops-235460},
  doi =		{10.4230/LIPIcs.ICALP.2025.169},
  annote =	{Keywords: hypergraph colourings, conflict-free colourings, unique-maximum colourings, linearly-ordered colourings}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2025.13
Symmetric Linear Arc Monadic Datalog and Gadget Reductions

Authors: Manuel Bodirsky and Florian Starke

Published in: LIPIcs, Volume 328, 28th International Conference on Database Theory (ICDT 2025)

Abstract
A Datalog program solves a constraint satisfaction problem (CSP) if and only if it derives the goal predicate precisely on the unsatisfiable instances of the CSP. There are three Datalog fragments that are particularly important for finite-domain constraint satisfaction: arc monadic Datalog, linear Datalog, and symmetric linear Datalog, each having good computational properties. We consider the fragment of Datalog where we impose all of these restrictions simultaneously, i.e., we study symmetric linear arc monadic (slam) Datalog. We characterise the CSPs that can be solved by a slam Datalog program as those that have a gadget reduction to a particular Boolean constraint satisfaction problem. We also present exact characterisations in terms of a homomorphism duality (which we call unfolded caterpillar duality), and in universal-algebraic terms (using known minor conditions, namely the existence of quasi Maltsev operations and k-absorptive operations of arity nk, for all n,k ≥ 1). Our characterisations also imply that the question whether a given finite-domain CSP can be expressed by a slam Datalog program is decidable.
Cite as

Manuel Bodirsky and Florian Starke. Symmetric Linear Arc Monadic Datalog and Gadget Reductions. In 28th International Conference on Database Theory (ICDT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 328, pp. 13:1-13:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bodirsky_et_al:LIPIcs.ICDT.2025.13,
  author =	{Bodirsky, Manuel and Starke, Florian},
  title =	{{Symmetric Linear Arc Monadic Datalog and Gadget Reductions}},
  booktitle =	{28th International Conference on Database Theory (ICDT 2025)},
  pages =	{13:1--13:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-364-5},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{328},
  editor =	{Roy, Sudeepa and Kara, Ahmet},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2025.13},
  URN =		{urn:nbn:de:0030-drops-229548},
  doi =		{10.4230/LIPIcs.ICDT.2025.13},
  annote =	{Keywords: Datalog, Gadget Reductions, Homomorphism Dualities, Minor Conditions}
}
Document
DOI: 10.4230/LIPIcs.CSL.2025.16
Undefinability of Approximation of 2-To-2 Games

Authors: Anuj Dawar and Bálint Molnár

Published in: LIPIcs, Volume 326, 33rd EACSL Annual Conference on Computer Science Logic (CSL 2025)

Abstract
Recent work by Atserias and Dawar [Albert Atserias and Anuj Dawar, 2019] and Tucker-Foltz [Jamie Tucker-Foltz, 2024] has established undefinability results in fixed-point logic with counting (FPC) corresponding to many classical complexity results from the hardness of approximation. In this line of work, NP-hardness results are turned into unconditional FPC undefinability results. We extend this work by showing the FPC undefinability of any constant factor approximation of weighted 2-to-2 games, based on the NP-hardness results of Khot, Minzer and Safra. Our result shows that the completely satisfiable 2-to-2 games are not FPC-separable from those that are not ε-satisfiable, for arbitrarily small ε. The perfect completeness of our inseparability is an improvement on the complexity result, as the NP-hardness of such a separation is still only conjectured. This perfect completeness enables us to show the FPC undefinability of other problems whose NP-hardness is conjectured. In particular, we are able to show that no FPC formula can separate the 3-colourable graphs from those that are not t-colourable, for any constant t.
Cite as

Anuj Dawar and Bálint Molnár. Undefinability of Approximation of 2-To-2 Games. In 33rd EACSL Annual Conference on Computer Science Logic (CSL 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 326, pp. 16:1-16:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dawar_et_al:LIPIcs.CSL.2025.16,
  author =	{Dawar, Anuj and Moln\'{a}r, B\'{a}lint},
  title =	{{Undefinability of Approximation of 2-To-2 Games}},
  booktitle =	{33rd EACSL Annual Conference on Computer Science Logic (CSL 2025)},
  pages =	{16:1--16:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-362-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{326},
  editor =	{Endrullis, J\"{o}rg and Schmitz, Sylvain},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2025.16},
  URN =		{urn:nbn:de:0030-drops-227735},
  doi =		{10.4230/LIPIcs.CSL.2025.16},
  annote =	{Keywords: Hardness of Approximation, Unique Games, Descriptive Complexity, Fixed-Point Logic with Counting}
}
  • Refine by Type
  • 21 Document/PDF
  • 12 Document/HTML

  • Refine by Publication Year
  • 2 2026
  • 13 2025
  • 3 2024
  • 1 2021
  • 1 2020
  • Show More...

  • Refine by Author
  • 4 Nakajima, Tamio-Vesa
  • 4 Opršal, Jakub
  • 4 Živný, Stanislav
  • 3 Guruswami, Venkatesan
  • 3 Rydval, Jakub
  • Show More...

  • Refine by Series/Journal
  • 21 LIPIcs

  • Refine by Classification
  • 10 Theory of computation → Problems, reductions and completeness
  • 5 Theory of computation → Finite Model Theory
  • 4 Theory of computation → Approximation algorithms analysis
  • 4 Theory of computation → Design and analysis of algorithms
  • 4 Theory of computation → Logic
  • Show More...

  • Refine by Keyword
  • 4 Datalog
  • 4 constraint satisfaction
  • 4 promise constraint satisfaction
  • 3 approximation
  • 2 Homomorphism Dualities
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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