|
|
Algebraický přístup k CSP
Bulín, Jakub ; Barto, Libor (advisor) ; Růžička, Pavel (referee)
For a finite relational structure A, the Constraint Satisfaction Problem with template A, or CSP(A), is the problem of deciding whether an input relational structure X admits a homomorphism to A. The CSP dichotomy conjecture of Feder and Vardi states that for any A, CSP(A) is either in P or NP-complete. In the first part we present the algebraic approach to CSP and summarize known results about CSP for digraphs, also known as the H-coloring problem. In the second part we study a class of oriented trees called special polyads. Using the algebraic approach we confirm the dichotomy conjecture for special polyads. We provide a finer description of the tractable cases and give a construction of a special polyad T such that CSP(T) is tractable, but T does not have width 1 and admits no near-unanimity polymorphisms.
|
|
|
Constraint satisfaction, graphs and algebras
Bulín, Jakub ; Barto, Libor (advisor) ; Růžička, Pavel (referee) ; Bulatov, Andrei (referee)
Constraint satisfaction, graphs and algebras Jakub Bulín Abstract This thesis consists of three papers in the area of algebraic approach to the constraint satisfaction problem. In the first paper, a joint work with Deli'c, Jackson and Niven, we study the reduction of fixed template CSPs to digraphs. We construct, for every relational structure A, a digraph D(A) such that CSP(A) and CSP(D(A)) are logspace equivalent and most rele- vant properties carry over from A to D(A). As a consequence, the algebraic conjectures characterizing CSPs solvable in P, NL and L are equivalent to their restrictions to digraphs. In the second paper we prove that, given a core relational structure A of bounded width and B ⊆ A, it is decidable whether B is an absorbing subuniverse of the algebra of polymorphisms of A. As a by-product, we show that Jónsson absorption coincides with the usual absorption in this case. In the third paper we establish, using modern algebraic tools (e.g. absorption theory and pointing operations), the CSP dichotomy conjecture for so-called special oriented trees and in particular prove that all tractable core special trees have bounded width. Keywords: constraint satisfaction problem, algebra of polymorphisms, absorbing subuniverse, bounded width, oriented tree.
|
|
|
Algebraický přístup k CSP
Bulín, Jakub ; Barto, Libor (advisor) ; Růžička, Pavel (referee)
For a finite relational structure A, the Constraint Satisfaction Problem with template A, or CSP(A), is the problem of deciding whether an input relational structure X admits a homomorphism to A. The CSP dichotomy conjecture of Feder and Vardi states that for any A, CSP(A) is either in P or NP-complete. In the first part we present the algebraic approach to CSP and summarize known results about CSP for digraphs, also known as the H-coloring problem. In the second part we study a class of oriented trees called special polyads. Using the algebraic approach we confirm the dichotomy conjecture for special polyads. We provide a finer description of the tractable cases and give a construction of a special polyad T such that CSP(T) is tractable, but T does not have width 1 and admits no near-unanimity polymorphisms.
|
guest ::
