D. Marx, Similarly, we can show that there is a value x + y ? t 2 < x + 2y such that ?(S 2 (t 2 )) ? 2c(c + 1) + 1. Denote by T (t 1 , t 2 ) the vertices of M (t 1 , t 2 ) on level less than d 0 We claim that ?(T (t 1 , t 2 )) ? 3. First, T (t 1 , t 2 ) can contain at most 3 vertices on each level 3·2 d?d 0 ? 3y ? t 2 ?t 1 , contradicting the assumption on the ?-values. Every v i,j ? T (t 1 , t 2 ) has a descendant v i ? ,j ? ? T (t 1 , t 2 ) for every i < i ? < d 0 , namely v i ? ,j ? with j ? = j2 i ? ?i . Thus by covering the at most 3 vertices of T (t 1 , t 2 ) on level d 0 ? 1 by at most 3 large edges, we can cover T (t 1 , t 2 ), and ?(T (t 1 , t 2 )) ? 3 follows. Define S := S(t 1 )?S(t 2 )?T (t 1 , t 2 ) Clearly, ?(S) ? 2(2c(c+1)+1)+3 = 4c(c+1)+5. We show that S separates M (t 1 , t 2 ) from the rest of the vertices. Suppose that v i,j , v i ? ,j ? ? S are adjacent vertices such that v i,j ? M (t 1 , t 2 ) and v i ? ,j ? ? M (t 1 , t 2 ) We have i ? d 0 (otherwise v i,j ? T (t 1 , t 2 )), hence v i,j ? A(t 1 ) If ?(v i ? ,j ? ) < t 1 , then v i ? ,j ? ? S(t 1 ) ? S, a contradiction. Moreover, if ?(v i ? ,j ? ) > t 2 , then i ? ? d 0 as v i,j and v i ? ,j ? are not neighbors if ?(v i,j ) < ?(v i ? ,j ? ) and i > i ? . Thus v i ? ,j ? ? A(t 2 ) and v i,j ? S(t 2 ) ? S, a contradiction, By the definition of x and y, we have ?(M (t 1 , t 2 )?W ) ? ?(M (x, x+y)?W ) ? ?(W )/4. To complete the proof that ?(W ? C) ? 3?(W )/4 for every component C of H(d, c) \ S, we show that ?(M (t 1 , t 2 ) ? W ) ? 3?(W )/4: as we have seen that every such component C is fully contained in either M (t 1 , t 2 ) or V \ M (t 1 this means that no component C can have ?(W ? C) > 3?(W )/4. Since x? t 1 < y, the minimality of y implies ?(M (t 1 , x)? W ) ? ?(W )/4. Similarly, it follows from t 2 ?(x+y) < y that ?(M (x+y, t 2 )?W ) ? ?(W )/4. Now ?(M (t 1 , t 2 )? W ) = ?(M (t 1 , x)? W )+ ?(M (x, x+ y)? W )+ ?(M (x+ y, t 2 )? W ) ? 3 4 ?(W )

H. Chen and M. Grohe, Constraint satisfaction problems with succinctly specified relations, Downey and M. R. Fellows. Parameterized Complexity, 1999.

J. Flum, M. Grohe, and E. C. Freuder, Parameterized Complexity Theory Complexity of k-tree structured constraint satisfaction problems, Proc. of AAAI-90, pp.4-9, 1990.

G. Gottlob, F. Scarcello, and M. Sideri, Fixed-parameter complexity in AI and nonmonotonic reasoning, Artificial Intelligence, vol.138, issue.1-2, pp.55-86, 2002.
DOI : 10.1016/S0004-3702(02)00182-0

M. Grohe, The complexity of homomorphism and constraint satisfaction problems seen from the other side, J. ACM, vol.54, issue.11, 2007.

M. Grohe and D. Marx, Constraint solving via fractional edge covers, SODA '06, pp.289-298, 2006.

R. Impagliazzo, R. Paturi, and F. Zane, Which problems have strongly exponential complexity?, Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280), pp.512-530, 2001.
DOI : 10.1109/SFCS.1998.743516
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.29.8482

D. Marx, Approximating fractional hypertree width, SODA '09, pp.902-911, 2009.
DOI : 10.1145/1721837.1721845
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.215.3266

D. Marx, Can you beat treewidth?, 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), pp.169-179, 2007.
DOI : 10.1109/FOCS.2007.27