Near Unanimity Constraints Have Bounded Pathwidth Duality

DOI10.1109/LICS.2012.24zbMath1362.68095OpenAlexW1979119667MaRDI QIDQ2986788

Marcin Kozik, Libor Barto, 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

polymorphismabsorptionconstraint satisfactionnear unanimitylinear Datalogpathwidth duality

Mathematics Subject Classification ID

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

Related Items (11)

Towards a characterization of constant-factor approximable finite-valued CSPs ⋮ Deciding absorption in relational structures ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The smallest hard trees ⋮ Algebra and the Complexity of Digraph CSPs: a Survey ⋮ A polynomial relational class of binary CSP ⋮ Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs ⋮ The number of clones determined by disjunctions of unary relations ⋮ Solving CSPs Using Weak Local Consistency ⋮ Unnamed Item

This page was built for publication: Near Unanimity Constraints Have Bounded Pathwidth Duality