[1]   Noga Alon and Dániel Marx: Sparse balanced partitions and the complexity of subgraph problems. Manuscript, 2010.

[2]   Noga Alon, Raphael Yuster, and Uri Zwick: Color-coding. J. ACM, 42(4):844–856, 1995. [doi:10.1145/210332.210337].

[3]   Hans L. Bodlaender: A tourist guide through treewidth. Acta Cybernet., 11(1-2):1–21, 1993.

[4]   Hans L. Bodlaender: A partial k-arboretum of graphs with bounded treewidth. Theoret. Comput. Sci., 209(1-2):1–45, 1998. [doi:10.1016/S0304-3975(97)00228-4].

[5]   Andrei Bulatov, Andrei Krokhin, and Peter Jeavons: The complexity of maximal constraint languages. In Proc. 33rd STOC, pp. 667–674. ACM Press, 2001. [doi:10.1145/380752.380868].

[6]   Andrei A. Bulatov: Tractable conservative constraint satisfaction problems. In Proc. 18th Ann. IEEE Symp. Logic in Computer Science (LICS), p. 321, Los Alamitos, CA, USA, 2003. IEEE Comp. Soc. Press. [doi:10.1109/LICS.2003.1210072].

[7]   Andrei A. Bulatov: A dichotomy theorem for constraint satisfaction problems on a 3-element set. J. ACM, 53(1):66–120, 2006. [doi:10.1145/1120582.1120584].

[8]   Hubie Chen and Martin Grohe: Constraint satisfaction with succinctly specified relations. J. Comput. System Sci., 76(8):847–860, 2010. [doi:10.1016/j.jcss.2010.04.003].

[9]   Jianer Chen, Benny Chor, Mike Fellows, Xiuzhen Huang, David W. Juedes, Iyad A. Kanj, and Ge Xia: Tight lower bounds for certain parameterized NP-hard problems. In Proc. 19th Ann. IEEE Conf. Comput. Complexity, pp. 150–160. IEEE Comp. Soc. Press, 2004. [doi:10.1109/CCC.2004.1313826].

[10]   Jianer Chen, Xiuzhen Huang, Iyad A. Kanj, and Ge Xia: Linear FPT reductions and computational lower bounds. In Proc. 36th STOC, pp. 212–221, New York, 2004. ACM Press. [doi:10.1145/1007352.1007391].

[11]   Víctor Dalmau, Phokion G. Kolaitis, and Moshe Y. Vardi: Constraint satisfaction, bounded treewidth, and finite-variable logics. In Proc. 8th Intern. Conf. Principles and Practice of Constraint Programming (CP), pp. 310–326, London, UK, 2002. Springer-Verlag. [doi:10.1007/3-540-46135-3_21].

[12]   Reinhard Diestel: Graph theory. Volume 173 of Graduate Texts in Mathematics. Springer-Verlag, Berlin, third edition, 2005.

[13]   Rodney G. Downey, Vladimir Estivill-Castro, Michael R. Fellows, Elena Prieto, and Frances Rosamond: Cutting up is hard to do. In James Harland, editor, Electron. Notes Theor. Comput. Sci., volume 78. Elsevier, 2003.

[14]   Rodney G. Downey and Michael R. Fellows: Parameterized Complexity. Monogr. Comput. Sci. Springer, New York, 1999.

[15]   Tomás Feder and Moshe Y. Vardi: The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory. SIAM J. Comput., 28(1):57–104, 1999. [doi:10.1137/S0097539794266766].

[16]   Uriel Feige, MohammadTaghi Hajiaghayi, and James R. Lee: Improved approximation algorithms for minimum weight vertex separators. SIAM J. Comput., 38(2):629–657, 2008. [doi:10.1137/05064299X].

[17]   Michael R. Fellows, Danny Hermelin, Frances A. Rosamond, and Stéphane Vialette: On the parameterized complexity of multiple-interval graph problems. Theoret. Comput. Sci., 410(1):53–61, 2009. [doi:10.1016/j.tcs.2008.09.065].

[18]   Jörg Flum and Martin Grohe: Parameterized complexity and subexponential time. Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, (84):71–100, 2004.

[19]   Jörg Flum and Martin Grohe: Parameterized Complexity Theory. Texts Theoret. Comput. Sci. EATCS Ser. Springer, Berlin, 2006.

[20]   Fedor Fomin, Petr Golovach, Daniel Lokshtanov, and Saket Saurabh: Algorithmic lower bounds for problems parameterized by clique-width. In Proc. 21st Ann. ACM-SIAM Symp. Discrete Algorithms (SODA 2010), pp. 493–502. ACM Press, 2006.

[21]   Eugene C. Freuder: Complexity of k-tree structured constraint satisfaction problems. In Proc. 8th National Conf. Artif. Intell. (AAAI), pp. 4–9, Boston, MA, 1990. AAAI Press.

[22]   Ofer Gabber and Zvi Galil: Explicit constructions of linear-sized superconcentrators. J. Comput. System Sci., 22(3):407–420, 1981. Special issued dedicated to Michael Machtey. [doi:10.1016/0022-0000(81)90040-4].

[23]   Georg Gottlob, Martin Grohe, Nysret Musliu, Marko Samer, and Francesco Scarcello: Hypertree decompositions: Structure, algorithms, and applications. In Graph-Theoretic Concepts in Computer Science, volume 3787 of Lecture Notes in Comput. Sci., pp. 1–15. Springer, Berlin, 2005. [doi:10.1007/11604686_1].

[24]   Georg Gottlob and Stefan Szeider: Fixed-parameter algorithms for artificial intelligence, constraint satisfaction and database problems. Comput. J., 51(3):303–325, 2008. [doi:10.1093/comjnl/bxm056].

[25]   Martin Grohe: The structure of tractable constraint satisfaction problems. In Proc. Mathematical Found. of Computer Science, volume 4162 of Lecture Notes in Comput. Sci., pp. 58–72. Springer, 2006. [doi:10.1007/11821069_5].

[26]   Martin Grohe: The complexity of homomorphism and constraint satisfaction problems seen from the other side. J. ACM, 54(1):1, 2007. [doi:10.1145/1206035.1206036].

[27]   Martin Grohe and Dániel Marx: Constraint solving via fractional edge covers. In Proc. 17th Ann. ACM-SIAM Symp. Discrete Algorithms (SODA 2006), pp. 289–298, New York, NY, USA, 2006. ACM Press. [doi:10.1145/1109557.1109590].

[28]   Martin Grohe and Dániel Marx: On tree width, bramble size, and expansion. J. Combin. Theory Ser. B, 99(1):218–228, 2009. [doi:10.1016/j.jctb.2008.06.004].

[29]   Martin Grohe, Thomas Schwentick, and Luc Segoufin: When is the evaluation of conjunctive queries tractable? In Proc.33rd STOC, pp. 657–666, New York, NY, USA, 2001. ACM Press. [doi:10.1145/380752.380867].

[30]   Russell Impagliazzo, Ramamohan Paturi, and Francis Zane: Which problems have strongly exponential complexity? J. Comput. System Sci., 63(4):512–530, 2001. [doi:10.1109/SFCS.1998.743516].

[31]   Peter Jeavons, David A. Cohen, and Marc Gyssens: Closure properties of constraints. J. ACM, 44(4):527–548, 1997. [doi:10.1145/263867.263489].

[32]   Ton Kloks: Treewidth. Volume 842 of Lecture Notes in Comput. Sci. Springer, Berlin, 1994.

[33]   Tom Leighton and Satish Rao: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM, 46(6):787–832, 1999. [doi:10.1145/331524.331526].

[34]   Dániel Marx: Closest substring problems with small distances. SIAM J. Comput., 38(4):1382–1410, 2008. [doi:10.1137/060673898].

[35]   Dániel Marx: Tractable structures for constraint satisfaction with truth tables. In Susanne Albers and Jean-Yves Marion, editors, Proc. 26th Intern. Symp. Theoretical Aspects of Computer Science (STACS), pp. 649–660. Schloß Dagstuhl - Leibniz-Zentrum für Informatik, Germany, 2009. [doi:10.4230/LIPIcs.STACS.2009.1807].

[36]   Dániel Marx: Approximating fractional hypertree width. ACM Trans. Algorithms, 6(2), 2010. [doi:10.1145/1721837.1721845].

[37]   Dániel Marx: Tractable hypergraph properties for constraint satisfaction and conjunctive queries. In Proc. 42nd STOC, pp. 735–744. ACM Press, 2010. [doi:10.1145/1806689.1806790].

[38]   B. A. Reed: Tree width and tangles: A new connectivity measure and some applications. In R.A. Bailey, editor, Surveys in Combinatorics, volume 241 of LMS Lecture Note Series, pp. 87–162. Cambridge University Press, 1997. [doi:10.1017/CBO9780511662119.006].

[39]   Neil Robertson and P. D. Seymour: Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms, 7(3):309–322, 1986. [doi:10.1016/0196-6774(86)90023-4].

[40]   Neil Robertson and P. D. Seymour: Graph minors. V. Excluding a planar graph. J. Combin. Theory Ser. B, 41(1):92–114, 1986. [doi:10.1016/0095-8956(86)90030-4].

[41]   Francesco Scarcello, Georg Gottlob, and Gianluigi Greco: Uniform constraint satisfaction problems and database theory. In Complexity of Constraints, pp. 156–195, 2008. [doi:10.1007/978-3-540-92800-3_7].

[42]   Thomas J. Schaefer: The complexity of satisfiability problems. In Proc. 10th STOC, pp. 216–226. ACM Press, New York, 1978. [doi:10.1145/800133.804350].