Finite automata, bounded treewidth, and well-quasiordering, Proc. of Graph Structure Theory, Contemporary Mathematics 147, pp.539-564, 1991. ,

Faster parameterized algorithms for minor containment, Theoretical Computer Science, vol.412, issue.50, pp.7018-7028, 2011. ,

URL : https://hal.archives-ouvertes.fr/lirmm-00736522

Irrelevant vertices for the planar disjoint paths problem, Journal of Combinatorial Theory, Series B, vol.122, pp.815-843, 2017. ,

URL : https://hal.archives-ouvertes.fr/hal-01632343

Polynomial-Time Data Reduction for Dominating Set, Journal of the ACM, vol.51, issue.3, pp.363-384, 2004. ,

An algebraic theory of graph reduction, Journal of the ACM, vol.40, issue.5, pp.1134-1164, 1993. ,

Scattered packings of cycles. Theoretical Computer Science, vol.647, pp.33-42, 2016. ,

URL : https://hal.archives-ouvertes.fr/hal-01401905

A linear-time algorithm for finding tree-decompositions of small treewidth, SIAM Journal on Computing, vol.25, issue.6, pp.1305-1317, 1996. ,

(meta) kernelization, Journal of the ACM, vol.63, issue.5, 2016. ,

URL : https://hal.archives-ouvertes.fr/lirmm-01483628

Kernel bounds for disjoint cycles and disjoint paths, Theoretical Computer Science, vol.412, issue.35, pp.4570-4578, 2011. ,

URL : https://hal.archives-ouvertes.fr/lirmm-00806805

Reduction algorithms for graphs of small treewidth, Information and Computation, vol.167, issue.2, pp.86-119, 2001. ,

Automatic generation of linear-time algo-rithms from predicate calculus descriptions of problems on recursively constructed graph families, Algorithmica, vol.7, pp.555-581, 1992. ,

Weak second order arithmetic and finite automata, Logik und Grundlagen der Mathematik, vol.6, pp.66-92, 1960. ,

Large-treewidth graph decompositions and applications, Proc. of the 45th Symposium on the Theory of Computing (STOC), pp.291-300, 2013. ,

Polynomial bounds for the grid-minor theorem, Proc. of the 46th ACM Symposium on the Theory of Computing (STOC), pp.60-69, 2014. ,

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

, Parameterized Algorithms, 2015.

Solving connectivity problems parameterized by treewidth in single exponential time, Proc. of the 52nd IEEE Symposium on Foundations of Computer Science (FOCS), pp.150-159, 2011. ,

Linearity of grid minors in treewidth with applications through bidimensionality, Combinatorica, vol.28, issue.1, pp.19-36, 2008. ,

Graph Theory, vol.173, 2010. ,

On independent circuits contained in a graph, Canadian Journal of Mathematics, vol.17, pp.347-352, 1965. ,

Graphbased data clustering with overlaps, Discrete Optimization, vol.8, issue.1, pp.2-17, 2011. ,

An Analogue of the Myhill-Nerode Theorem and Its Use in Computing Finite-Basis Characterizations (Extended Abstract), Proc. of the 30th IEEE Symposium on Foundations of Computer Science (FOCS), pp.520-525, 1989. ,

On search, decision, and the efficiency of polynomial-time algorithms, Journal of Computer and System Sciences, vol.49, issue.3, pp.769-779, 1994. ,

Kernelization algorithms for packing problems allowing overlaps, Proc. of the 12th Annual Conference on Theory and Applications of Models of Computation, vol.9076, pp.415-427, 2015. ,

Contraction obstructions for treewidth, Journal of Combinatorial Theory, Series B, vol.101, issue.5, pp.302-314, 2011. ,

Bidimensionality and EP-TAS, Proc. of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.748-759, 2011. ,

Bidimensionality and kernels, Proc. of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.503-510, 2010. ,

Strengthening Erd?s-Pósa property for minor-closed graph classes, Journal of Graph Theory, vol.66, issue.3, pp.235-240, 2011. ,

Explicit linear kernels via dynamic programming, SIAM Journal on Discrete Mathematics, vol.29, issue.4, pp.1864-1894, 2015. ,

URL : https://hal.archives-ouvertes.fr/lirmm-01263857

Partial Orderings and Algorithms on Graphs, 2012. ,

Linear problem kernels for NP-hard problems on planar graphs, Proc. of the 34th International Colloquium on Automata, Languages and Programming (ICALP), vol.4596, pp.375-386, 2007. ,

Explicit bounds for graph minors, 2013. ,

Linear min-max relation between the treewidth of H-minor-free graphs and its largest grid, Proc. of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS), vol.14, pp.278-289, 2012. ,

URL : https://hal.archives-ouvertes.fr/hal-00678187

A simpler algorithm and shorter proof for the graph minor decomposition, Proc. of the 43rd ACM Symposium on Theory of Computing (STOC), pp.451-458, 2011. ,

Linear kernels and single-exponential algorithms via protrusion decompositions, ACM Transactions on Algorithms, vol.12, issue.2, p.21, 2016. ,

URL : https://hal.archives-ouvertes.fr/lirmm-01288472

, Treewidth. Computations and Approximations, 1994.

Lower bounds based on the exponential time hypothesis, Bulletin of the EATCS, vol.105, pp.41-72, 2011. ,

A single exponential bound for the redundant vertex theorem on surfaces, 2013. ,

URL : https://hal.archives-ouvertes.fr/hal-00867663

A problem kernelization for graph packing, Proc. of the 35th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), vol.5404, pp.401-412, 2009. ,

Graph Minors. V. Excluding a Planar Graph, Journal of Combinatorial Theory, Series B, vol.41, issue.1, pp.92-114, 1986. ,

Graph Minors. XIII. The Disjoint Paths Problem, Journal of Combinatorial Theory, Series B, vol.63, issue.1, pp.65-110, 1995. ,

Graph minors. XVI. excluding a non-planar graph, Journal of Combinatorial Theory, Series B, vol.89, issue.1, pp.43-76, 2003. ,

The G-packing with t-overlap problem, Proc. of the 8th International Workshop on Algorithms and Computation (WALCOM), vol.8344, pp.114-124, 2014. ,

A parameterized algorithm for packing overlapping subgraphs, Proc. of the 9th International Computer Science Symposium in Russia (CSR), vol.8476, pp.325-336, 2014. ,

Let (T, X ) claim that for any node x of T , the graph G x is a progressive representative of its equivalence class with respect to ? E FSP ,G,t , namely C . Indeed, assume for contradiction that G x is not progressive, and therefore we know that there exists G x ? C such that ? E FSP ,t (G x , G x ) < 0. Let G be the graph obtained from G by replacing G x with G x . Since ? * E FSP ,G,t is DP-friendly, it follows that, Since we assume that E FSP is g-confined, we have that for any G ? B t with ?(G) = I, the function f E FSP (G, · ) can take at most g(t) + 2 distinct values (g(t) + 1 finite values and possibly the value ??). Therefore, it follows that the number of equivalence classes of ? * f E FSP (G 2 , R) for every encoding R such that f E FSP ,

it follows that the height of T is at most the number of equivalence classes of ? E FSP ,G,t , which is at most r(E FSP , g, t, G) by Lemma 1. Since T is a binary tree ,

, A.5 Proof of Lemma, vol.4

FSP ) be the given encoder. We start by generating a repository of them ,