Near unanimity constraints have bounded pathwidth duality

DOI10.1109/LICS.2012.24MaRDI QIDQ2986788zbMATH OpenOpenAlexFDO

Authors Libor Barto, Marcin Kozik, Ross Willard

Publication date 16 May 2017

Published in 2012 27th Annual IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/lics.2012.24

zbMATH Keywords

absorptionconstraint satisfactionlinear Datalognear unanimitypathwidth dualitypolymorphism

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• Majority constraints have bounded pathwidth duality
• scientific article; zbMATH DE number 2086640
• CSP duality and trees of bounded pathwidth
• Dualities for Constraint Satisfaction Problems
• Linear Datalog and Bounded Path Duality of Relational Structures

Cited in

(16)

• Towards a characterization of constant-factor approximable finite-valued CSPs
• The number of clones determined by disjunctions of unary relations
• Deciding absorption in relational structures
• Majority constraints have bounded pathwidth duality
• Majority functions on structures with finite duality
• \(n\)-permutability and linear Datalog implies symmetric Datalog
• scientific article; zbMATH DE number 7359806 (Why is no real title available?)
• Absorption in universal algebra and CSP
• Algebra and the complexity of digraph CSPs: a survey
• Solving CSPs using weak local consistency
• Robust algorithms with polynomial loss for near-unanimity CSPs
• The smallest hard trees
• Graphs of finite algebras: edges, and connectivity
• A polynomial relational class of binary CSP
• Symmetric linear arc monadic Datalog and gadget reductions
• Symmetric linear arc monadic Datalog and gadget reductions

This page was built for publication: Near unanimity constraints have bounded pathwidth duality

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