K. R. Abrahamson and M. R. Fellows, Finite Automata, Bounded Treewidth and Well-Quasiordering, AMS Summer Workshop on Graph Minors, Graph Structure Theory, Contemporary Mathematics, vol.147, pp.539-564, 1993.

S. Arnborg, J. Lagergren, and D. Seese, Easy problems for tree-decomposable graphs, Journal of Algorithms, vol.12, pp.308-340, 1991.

L. Hans, R. G. Bodlaender, M. R. Downey, D. Fellows, and . Hermelin, On problems without polynomial kernels, J. Comput. Syst. Sci, vol.75, pp.423-434, 2009.

L. Hans, F. V. Bodlaender, D. Fomin, E. Lokshtanov, S. Penninkx et al., Meta) Kernelization. J. ACM, vol.63, issue.5, 2016.

L. Hans, . Bodlaender, M. P. Bart, S. Jansen, and . Kratsch, Kernelization Lower Bounds by Cross-Composition, SIAM J. Discrete Math, vol.28, issue.1, pp.277-305, 2014.

L. Hans, B. Bodlaender, and . Van-antwerpen-de-fluiter, Reduction algorithms for graphs of small treewidth, Inf. Comput, vol.167, pp.86-119, 2001.

R. B. Borie, R. G. Parker, and C. A. Tovey, Automatic Generation of Linear-Time Algorithms from Predicate Calculus Descriptions of Problems on Recursively Constructed Graph Families, Algorithmica, vol.7, pp.555-581, 1992.

Y. Chen, J. Flum, and M. Müller, Lower Bounds for Kernelizations and Other Preprocessing Procedures, Theory Comput. Syst, vol.48, issue.4, pp.803-839, 2011.

B. Courcelle, J. A. Makowsky, and U. Rotics, On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic, Workshop on Graph Theoretic Concepts in Computer Science, vol.108, pp.23-52, 2001.

B. Courcelle, The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Information and Computation, vol.85, pp.12-75, 1990.
URL : https://hal.archives-ouvertes.fr/hal-00353765

B. Courcelle and M. Mosbah, Monadic second-order evaluations on tree-decomposable graphs, Theor. Comput. Sci, vol.109, pp.49-82, 1993.

M. Cygan, V. Fedor, L. Fomin, D. Kowalik, D. Lokshtanov et al., Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms, 2015.

A. Dawar, M. Grohe, and S. Kreutzer, Locally Excluding a Minor, 21st IEEE Symposium on Logic in Computer Science (LICS'07), pp.270-279, 2007.

F. Babette-de, Algorithms for Graphs of Small Treewidth, 1997.

H. Dell, AND-Compression of NP-Complete Problems: Streamlined Proof and Minor Observations, Algorithmica, vol.75, issue.2, pp.403-423, 2016.

J. Díaz, M. Serna, and D. M. Thilikos, Efficient algorithms for counting parameterized list H-colorings, J. Comput. System Sci, vol.74, issue.5, pp.919-937, 2008.

G. Rodney, M. R. Downey, and . Fellows, Fundamentals of Parameterized Complexity. Texts in Computer Science, 2013.

A. Drucker, New Limits to Classical and Quantum Instance Compression, SIAM J. Comput, vol.44, issue.5, pp.1443-1479, 2015.

Z. Dvorak, D. Kral, and R. Thomas, Deciding First-Order Properties for Sparse Graphs, 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS '10, pp.133-142, 2010.

, Data-Compression for Parametrized Counting Problems on Sparse Graphs

Z. Dvo?ák, D. Král, and R. Thomas, Testing First-order Properties for Subclasses of Sparse Graphs, J. ACM, vol.60, issue.5, p.24, 2013.

J. Flum and M. Grohe, Fixed-parameter tractability, definability, and modelchecking, SIAM J. Comput, vol.31, issue.1, pp.113-145, 2001.

J. Flum and M. Grohe, Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series, 2006.

F. V. Fomin, D. Lokshtanov, S. Saurabh, and D. M. Thilikos, Bidimensionality and Kernels, 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), pp.503-510, 2010.

V. Fedor, D. Fomin, N. Lokshtanov, S. Misra, and . Saurabh, Planar F-Deletion: Approximation, Kernelization and Optimal FPT Algorithms, 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, pp.470-479, 2012.

V. Fedor, D. Fomin, and . Lokshtanov, Saket Saurabh, and Dimitrios M. Thilikos. Bidimensionality and Kernels. CoRR, abs/1606.05689, 2016. Revised version

L. Fortnow and R. Santhanam, Infeasibility of instance compression and succinct PCPs for, NP. J. Comput. Syst. Sci, vol.77, issue.1, pp.91-106, 2011.

M. Frick, Generalized Model-Checking over Locally Tree-Decomposable Classes. Theory of Computing Systems, vol.37, pp.157-191, 2004.

M. Frick and M. Grohe, Deciding First-Order Properties of Locally Tree-Decomposable Graphs, Jirí Wiedermann, Peter van Emde Boas, and Mogens Nielsen, vol.1644, pp.72-72, 1999.

M. Grohe, Logic, graphs, and algorithms, Logic and Automata, pp.357-422, 2008.

M. Grohe and S. Kreutzer, Methods for algorithmic meta theorems, chapter Model Theoretic Methods in Finite Combinatorics, pp.181-206, 2011.

M. Grohe, S. Kreutzer, and S. Siebertz, Deciding First-order Properties of Nowhere Dense Graphs, Proceedings of the 46th Annual ACM Symposium on Theory of Computing, STOC '14, pp.89-98, 2014.

A. Gupta, E. Lee, J. Li, P. Manurangsi, and M. Wlodarczyk, Losing treewidth by separating subsets, 2018.

D. Harnik and M. Naor, On the Compressibility of NP Instances and Cryptographic Applications, SIAM J. Comput, vol.39, issue.5, pp.1667-1713, 2010.

E. J. Kim, A. Langer, C. Paul, F. Reidl, P. Rossmanith et al., Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions, ACM Trans. Algorithms, vol.12, issue.2, 2016.
URL : https://hal.archives-ouvertes.fr/lirmm-00829999

E. J. Kim, M. Serna, and D. M. Thilikos, Data-compression for parametrized counting problems on sparse graphs, 2018.
URL : https://hal.archives-ouvertes.fr/lirmm-02342803

S. Kreutzer, Algorithmic Meta-theorems, IWPEC, pp.10-12, 2008.

D. Lokshtanov, N. Misra, and S. Saurabh, Kernelization -Preprocessing with a Guarantee, The Multivariate Algorithmic Revolution and Beyond, pp.129-161, 2012.

R. Niedermeier, Invitation to fixed-parameter algorithms, Oxford Lecture Series in Mathematics and its Applications, vol.31, 2006.

N. Nishimura, P. Ragde, and D. M. Thilikos, Parameterized Counting Algorithms for General Graph Covering Problems, Algorithms and Data Structures, 9th International Workshop, WADS 2005, vol.3608, pp.99-109, 2005.

D. Seese, The structure of the models of decidable monadic theories of graphs, Annals of Pure and Applied Logic, vol.53, issue.2, pp.169-195, 1991.

D. Seese, Linear Time Computable Problems and First-Order Descriptions, Mathematical Structures in Computer Science, vol.6, issue.6, pp.505-526, 1996.

M. Thurley, Kernelizations for parameterized counting problems, 4th international conference on Theory and applications of models of computation, TAMC'07, pp.705-714

. Springer-verlag, , 2007.

M. Thurley, Tractability and Intractability of Parameterized Counting Problems, 2006.