Topology and Adjunction in Promise Constraint Satisfaction

DOI10.1137/20M1378223MaRDI QIDQ5885596

Marcin Wrochna, Andrei A. Krokhin, Jakub Opršal, Stanislav Živný

Publication date: 4 April 2023

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2003.11351

zbMATH Keywords

graph coloringpolymorphismconstraint satisfactionpromise problemgraph homomorphism problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Square-free graphs are multiplicative
• Digraph functors which admit both left and right adjoints
• Hedetniemi's conjecture and adjoint functors in thin categories
• Kneser's conjecture, chromatic number, and homotopy
• On the complexity of H-coloring
• On the arc-chromatic number of a digraph
• A survey on Hedetniemi's conjecture
• Galois theory for minors of finite functions
• Box complexes and homotopy theory of graphs
• The wonderland of reflections
• Strong inapproximability results on balanced rainbow-colorable hypergraphs
• Topological lower bounds for the chromatic number: a hierarchy
• Dismantlability, connectedness, and mixing in relational structures
• Counterexamples to Hedetniemi's conjecture
• \(\mathbb{Z}_2\)-indices and Hedetniemi's conjecture
• On inverse powers of graphs and topological implications of Hedetniemi's conjecture
• The hardness of 3-uniform hypergraph coloring
• Complexes of graph homomorphisms
• Closed systems of functions and predicates
• Arc colorings of digraphs
• WI-posets, graph complexes and \(\mathbb{Z}_2\)-equivalences
• Robustly Solvable Constraint Satisfaction Problems
• Improved Hardness of Approximating Chromatic Number
• Coloring 3-Colorable Graphs with Less than n ^1/5 Colors
• Conditional Hardness for Approximate Coloring
• On the power of unique 2-prover 1-round games
• On the Conditional Hardness of Coloring a 4-Colorable Graph with Super-Constant Number of Colors
• Undirected connectivity in log-space
• On the Simple ℤ₂-homotopy Types of Graph Complexes and Their Simple ℤ₂-universality
• Applications of product colouring
• The Complexity of Near-Optimal Graph Coloring
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Closure properties of constraints
• On the Hardness of 4-Coloring a 3-Colorable Graph
• Drei Sätze über die n-dimensionale euklidische Sphäre
• Loop conditions for strongly connected digraphs
• The Quest for Strong Inapproximability Results with Perfect Completeness
• Algebraic Approach to Promise Constraint Satisfaction
• The Complexity of Promise SAT on Non-Boolean Domains
• Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy
• A Proof of the CSP Dichotomy Conjecture
• The Power of the Combined Basic Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems
• Symmetric Polymorphisms and Efficient Decidability of Promise CSPs
• Improved hardness for H-colourings of G-colourable graphs
• Improved Inapproximability of Rainbow Coloring
• Algebraic approach to promise constraint satisfaction
• Homomorphism Reconfiguration via Homotopy
• Rainbow Coloring Hardness via Low Sensitivity Polymorphisms
• Towards a proof of the 2-to-1 games conjecture?
• An Algorithmic Blend of LPs and Ring Equations for Promise CSPs
• Hedetniemi's Conjecture and Strongly Multiplicative Graphs
• Classifying the Complexity of Constraints Using Finite Algebras
• $(2+\varepsilon)$-Sat Is NP-hard
• New hardness results for graph and hypergraph colorings
• A Characterisation of First-Order Constraint Satisfaction Problems
• The PCP theorem by gap amplification
• Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry. Written in cooperation with Anders Björner and Günter M. Ziegler
• Combinatorial algebraic topology
• On the hardness of approximating the chromatic number

This page was built for publication: Topology and Adjunction in Promise Constraint Satisfaction