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 ,