The seminar is a continuation of the course NALG117 (Introduction to the complexity of the CSP). According to
partincipants' interest we focus on selected deeper results, for example the dichotomy for conservative CSPs, the dichotomy
for CSPs on a three-element set, few subpowers CSPs, the dichotomy for smooth digraphs or characterization of bounded
width problems.
Last update: T_KA (14.05.2013)
Seminář navazuje na přednášku NALG117 Úvod do složitosti CSP. Podle zájmu účastníků se zaměříme na vybrané hlubší
výsledky, jako například dichotomii pro konzervativní CSP, dichotomii pro CSP na tříprvkové množině, "few subpowers"
CSP, dichotomii pro hladké digrafy nebo charakterizaci problémů konečné šířky.
Last update: T_KA (14.05.2013)
Literature -
[1] L. Barto, M. Kozik: Constraint Satisfaction Problems of Bounded Width. manuscript, 2009.
[2] L. Barto, M. Kozik, T. Niven: Graphs, polymorphisms and the complexity of homomorphism problems. In STOC'08: Proceedings of the 40th annual ACM symposium on Theory of computing, pages 789-796, New York, NY, USA, 2008.
[3] A. Bulatov: Tractable conservative constraint satisfaction problems. In LICS 03: Proceedings of the 18th Annual IEEE Symposium on Logic in Computer Science, page 321, Washington, DC, USA, 2003. IEEE Computer Society.
[4] A. Bulatov: A dichotomy theorem for constraint satisfaction problems on a 3-element set. J. ACM, 53(1):66-120, 2006.
[5] A. Bulatov, A. Krokhin, P. Jeavons: Constraint satisfaction problems and finite algebras. In: Proc. 27th International Colloquium on Automata, Languages and Programming, ICALP'00. Volume 1853 of LNCS, Springer-Verlag (2000) 272-282.
[6] T. Feder, M.Y. Vardi: The computational structure of monotonie monadic SNP and constraint satisfaction: a study through Datalog and group theory. SIAM J. Computing, 28 (1), 1998, 57-104.
[7] P. Idziak, P. Markovic, R. McKenzie, M. Valeriote, and R. Willard: Tractability and learnability arising from algebras with few subpowers, pp. 213-224, 22nd Annual IEEE Symposium on Logic in Computer Science (LICS 2007), 2007
[8] B. Larose, L. Zádori: Bounded width problems and algebras. Algebra Universalis 56 (3-4), 2007, 439-466.
Last update: T_KA (14.05.2013)
[1] L. Barto, M. Kozik: Constraint Satisfaction Problems of Bounded Width. manuscript, 2009.
[2] L. Barto, M. Kozik, T. Niven: Graphs, polymorphisms and the complexity of homomorphism problems. In STOC'08: Proceedings of the 40th annual ACM symposium on Theory of computing, pages 789-796, New York, NY, USA, 2008.
[3] A. Bulatov: Tractable conservative constraint satisfaction problems. In LICS 03: Proceedings of the 18th Annual IEEE Symposium on Logic in Computer Science, page 321, Washington, DC, USA, 2003. IEEE Computer Society.
[4] A. Bulatov: A dichotomy theorem for constraint satisfaction problems on a 3-element set. J. ACM, 53(1):66-120, 2006.
[5] A. Bulatov, A. Krokhin, P. Jeavons: Constraint satisfaction problems and finite algebras. In: Proc. 27th International Colloquium on Automata, Languages and Programming, ICALP'00. Volume 1853 of LNCS, Springer-Verlag (2000) 272-282.
[6] T. Feder, M.Y. Vardi: The computational structure of monotonie monadic SNP and constraint satisfaction: a study through Datalog and group theory. SIAM J. Computing, 28 (1), 1998, 57-104.
[7] P. Idziak, P. Markovic, R. McKenzie, M. Valeriote, and R. Willard: Tractability and learnability arising from algebras with few subpowers, pp. 213-224, 22nd Annual IEEE Symposium on Logic in Computer Science (LICS 2007), 2007
[8] B. Larose, L. Zádori: Bounded width problems and algebras. Algebra Universalis 56 (3-4), 2007, 439-466.
