The Complexity of the Extendibility Problem for Finite Posets
From MaRDI portal
Publication:4443125
DOI10.1137/S0895480101389478zbMath1034.06004MaRDI QIDQ4443125
Publication date: 8 January 2004
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
NP-completeconstraint satisfaction problemzigzagsextendibility problem for posetstotally symmetric idempotent and near unanimity operations
Combinatorics of partially ordered sets (06A07) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (11)
Dualities and algebras with a near-unanimity term ⋮ Critical relations of crowns in critical times of coronavirus depression ⋮ Colouring, constraint satisfaction, and complexity ⋮ Dismantlability, connectedness, and mixing in relational structures ⋮ SOLVABILITY OF SYSTEMS OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS ⋮ Algebra and the Complexity of Digraph CSPs: a Survey ⋮ Retractions onto series-parallel posets ⋮ A discrete homotopy theory for binary reflexive structures ⋮ CSP duality and trees of bounded pathwidth ⋮ TAYLOR TERMS, CONSTRAINT SATISFACTION AND THE COMPLEXITY OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS ⋮ A combinatorial constraint satisfaction problem dichotomy classification conjecture
This page was built for publication: The Complexity of the Extendibility Problem for Finite Posets