Die Komplexität von Constraint-Satisfaction Problemen

• Applicant: Professor Dr. Martin Grohe
• Subject Area: Theoretical Computer Science
• Term: from 2004 to 2009
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 5432723

• Final Report Year: 2009

Final Report Abstract

Es ist uns meines Erachtens gelungen, zu den wesentlichen im Projektantrag genannten Fragestellungen substantielle Fortschritte zu erzielen. Als die Hauptresultate des Projekts sehe ich die erzielten Ergebnisse zu fraktionalen Kantenüberdeckungszahlen und strukturellen Kriterien für die effiziente Lösbarkeit von CSP und den bewiesenen Klassifikationssatz für die Komplexität von Partitionsfunktionen ZA an.

Publications

• Derandomization of PPSZ for Unique-SAT. In: F. Bacchus and T. Walsh, editors. Proceedings of the 8th International Conference on Theory and Applications of Satisfiability Testing, volume 3569 of Lecture Notes in Computer Science, pages 216-225. Springer-Verlag, 2005
  D. Rolf
  
• Constraint satisfaction, with succinctly specified relations
  H. Chen and M. Grohe
  
• Constraint solving via fractional edge covers. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 289-298, 2006
  M. Grohe and D. Marx
  
• Improved bound for the PPSZ/Schöning-algorithm for 3-SAT. Journal on Satisfiability, Boolean Modeling and Computation, 1:111-122,2006
  D. Rolf
  
• sharpSAT - counting models with advanced component caching and implicit BCP. In: A. Biere and C.P. Gomes, editors. Theory and Applications of Satisfiability Testing - SAT2006, 9th International Conference, Seattle, WA, USA, August 12-15, 2006, Proceedings, volume 4121 of Lecture Notes in Computer Science, pages 424-429. Springer-Verlag, 2006
  M. Thurley
  
• The structure of tractable constraint satisfaction problems. In: R. Královic and P. Urzyczyn, editors, Proceedings of the 31st Symposium on Mathematical Foundations of Computer Science, Volume 4162 of Lecture, Notes in Computer Science, pages 58-72. Springer-Verlag, 2006
  M. Grohe
  
• Can you beat treewidth? In: Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, pages 169-119,2007
  D. Marx
  
• Hypertree-width and related hypergraph invariants. European Journal of Combinatorics, 28:2167-2181, 2007
  I. Adler, G. Goulob, and M. Grohe
  
• The complexity of homomorphism and constraint satisfaction problems seen from the other side. Journal of the ACM, 54, 2007
  M. Grohe
  
• Non-dichotomies in constraint satisfaction complexity. In: L. Aceto, I. Damgaard, L.A. Goldberg, M.M. Halldórsson, A. Ingólfsdóttir, and I. Walukiewicz, editors, Proceedings of the 35th International Colloquium on Automata, Languages and Programming, Part II, volume 5126 of Lecture Notes in Computer Science, pages 184-196. Springer-Verlag, 2008
  M. Bodirsky and M. Grohe
  
• Size bounds and query plans for relational joins. In: Proceedings ofthe 49th Annual IEEE Symposium on Foundations of Computer Science, pages 739-748,2008
  A. Atserias, M. Grohe, and D. Marx
  
• A complexity dichotomy for partition functions with mixed signs. In: S. Albers and J.-Y. Marion, editors, Proceedings of the 26th Annual Symposium on Theoretical Aspects of Computer Science, pages 493-504, 2009
  L.A. Goldberg, M. Grohe, M. Jerrum, and M. Thurley
  
• Enumerating homomorphisms. In: S. Albers and J.-Y. Marion, editors, Proceedings of the 26th Annual Symposium on Theoretical Aspects of Computer-Science, psiges 231-242, 2009
  A. Bulatov, V. Dalmau, M. Grohe, and D. Marx
  
• The complexity of datalog on linear orders. Logical Methods in Computer Science, 5, 2009
  M. Grohe and G. Schwandtner
  
• Tradable structures for constraint satisfaction with tmth tables. In: S. Albers and J.-Y. Marion; editors, Proceedings of the 26th Annual Symposium on Theoretical Aspects of Computer Science, pages 649-660,2009
  D. Marx