The complexity of resilience problems via valued constraint satisfaction problems

DOI10.1145/3661814.3662071MaRDI QIDQ6970266zbMATH OpenFDO

Authors Manuel Bodirsky, Žaneta Semanišinová, Carsten Lutz

Publication date 18 June 2025

Full work available at URL https://doi.org/10.1145/3661814.3662071

zbMATH Keywords

computational complexityconjunctive queriesfractional polymorphismsoligomorphic automorphism groupspolynomial-time tractabilitypp-constructionsresiliencevalued constraints

Mathematics Subject Classification ID

Applications of universal algebra in computer science (08A70) Database theory (68P15) Analysis of algorithms and problem complexity (68Q25) Computational aspects of satisfiability (68R07)

Cites work

• A Characterisation of First-Order Constraint Satisfaction Problems
• A complexity dichotomy in spatial reasoning via Ramsey theory
• A dichotomy for first-order reducts of unary structures
• A dichotomy theorem for nonuniform CSPs
• A Galois connection for weighted (relational) clones of infinite size
• A proof of CSP dichotomy conjecture
• A proof of the CSP dichotomy conjecture
• A universal-algebraic proof of the complexity dichotomy for monotone monadic SNP
• Algebraic properties of valued constraint satisfaction problem
• An Algebraic Characterisation of Complexity for Valued Constraint
• An algebraic theory of complexity for discrete optimization.
• Complexity of infinite-domain constraint satisfaction
• Computer Science Logic
• Correlation clustering
• Directed flow-augmentation
• Duality theorems for finite structures (characterising gaps and good characterisations)
• Homomorphism and embedding universal structures for restricted classes
• scientific article; zbMATH DE number 44603 (Why is no real title available?)
• scientific article; zbMATH DE number 1007358 (Why is no real title available?)
• Parameterized algorithms
• Piecewise Linear Valued CSPs Solvable by Linear Programming Relaxation
• PROJECTIVE CLONE HOMOMORPHISMS
• Solving hard cut problems via flow-augmentation
• Testing the Complexity of a Valued CSP Language
• The Combined Basic LP and Affine IP Relaxation for Promise VCSPs on Infinite Domains
• The complexity of equality constraint languages
• The complexity of finite-valued CSPs
• The complexity of general-valued CSPs
• The complexity of valued CSPs
• The power of linear programming for general-valued CSPs
• The wonderland of reflections
• Universal graphs with forbidden subgraphs and algebraic closure
• Universial structures with forbidden homomorphisms

Cited in

(2)

• Temporal valued constraint satisfaction problems
• The complexity of resilience problems via valued constraint satisfaction

This page was built for publication: The complexity of resilience problems via valued constraint satisfaction problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6970266)