The Complexity of the Extendibility Problem for Finite Posets

DOI10.1137/S0895480101389478zbMath1034.06004MaRDI QIDQ4443125

Benoit Larose, László Zádori

Publication date: 8 January 2004

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

NP-completeconstraint satisfaction problemzigzagsextendibility problem for posetstotally symmetric idempotent and near unanimity operations

Mathematics Subject Classification ID

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