Subexponential parameterized algorithms on graphs of bounded-genus and H -minor-free graphs Erik D. Demaine Fedor V. Fomin MohammadTaghi Hajiaghayi Dimitrios M. Thilikos Abstract We introduce a new framework for designing fixe-parameter ald gorithms with subexponential running time--2O( k) nO(1) . Our results apply to a broad family of graph problems, called bidimensional problems, which includes many domination and covering problems such as vertex cover, feedback vertex set, minimum maximal matching, dominating set, edge dominating set, clique-transversal set, and many others restricted to bounded-genus graphs. Furthermore, it is fairly straightforward to prove that a problem is bidimensional. In particular, our framework includes as special cases all previously known problems to have such subexponential algorithms. Previously, these algorithms applied to planar graphs, single-crossing-minor-free graphs, and map graphs; we extend these results to apply to bounded-genus graphs as well. In a parallel development of combinatorial results, we establish an upper bound on the treewidth (or branchwidth) of a bounded-genus graph that excludes some planar graph H as a minor. This bound depends linearly on the size |V (H )| of the excluded graph H and the genus g (G) of the graph G, and applies and extends the graphminors work of Robertson & Seymour. Building on these results, we develop subexponential fixedparameter algorithms for dominating set, vertex cover, and set cover in any class of graphs excluding a fixed graph H as a minor. In particular, this general category of graphs includes planar graphs, bounded-genus graphs, single-crossing-minor-free graphs, and any class of graphs that is closed under taking minors. Specifically, the running time is 2O( k) nh , where h is a constant depending only on H , which is polynomial for k = O(log2 n). We introduce a general approach for developing algorithms on H -minor-free graphs, based on structural results about H -minor-free graphs at the heart of Robertson & Seymour's graph-minors work. We believe this approach opens the way to further development for problems on H -minor-free graphs. MIT Laboratory for Computer Science, 200 Technology Square, Cambridge, Massachusetts 02139, USA, {edemaine, hajiagha}@mit.edu Department of Informatics, University of Bergen, N-5020 Bergen, Norway, fomin@ii.uib.no Departament de Llenguatges i Sistemes Informatics, Universitat ` ` ` Politecnica de Catalunya, Campus Nord ­ Modul C5, c/Jordi Girona Salgado 1-3, E-08034, Barcelona, Spain, sedthilk@lsi.upc.es. This author was supported by EC contract IST-1999-14186: Project ALCOMFT (Algorithms and Complexity) - Future Technologies and by the Spanish CICYT project TIC-2002-04498-C05-03 (TRACER). 1 Introduction Dominating set is a classic NP-complete graph optimization problem which fits into the broader class of domination and covering problems on which hundreds of papers have been written; see e.g. the survey [23]. A sample application is the problem of finding sites for emergency service facilities such as fire stations. Here we suppose that we can afford to build k fire stations to cover a city, and we require that every building is covered by at least one fire station. This problem is k -dominating set (finding a dominating set of size k ) in the graph where edges represent suitable pairings of fire stations with buildings. In this application, we can afford high running time (e.g., several weeks of real time) if the resulting solution builds fewer fire stations (which are extremely expensive). Thus, we prefer exact fixed-parameter algorithms (which run fast provided the parameter k is small) over approximation algorithms, even if the approximation were within an additive constant. The theory of fixed-parameter algorithms and parameterized complexity has been thoroughly developed over the past few years; see e.g. [11, 15, 17, 18, 20, 2]. In the last two years, several researchers have obtained exponential speedups in fixed-parameter algorithms for various problems on several classes of graphs. While most previous fixed-parameter algorithms have a running time of O(2O(k) nO(1) ) or worse, the exponential speedups results in subexponential algorithms with running times of O(2O( k) nO(1) ). For example, the first fixed-parameter algorithm for k -dominating set in planar graphs [15] has running time O(11k |G|); subsequently, a sequence of subexponential algorithms and improvements have been obta ed, in 6 34k 27 k starting with running time O(4 n) [1], then O(2 n) [24], and finally O(215.13 k k + n3 + k 4 ) [18]. Other subexponential algorithms for other domination and covering problems on planar graphs also have been obtained [1, 2, 7, 26, 22]. However, all of these algorithms apply only to planar graphs. In another sequence of papers, these results have been generalized to other classes of graphs: map graphs [11], which include planar graphs; K3,3 -minor-free Copyright © 2004 by the Association for Computing Machinery, Inc. and the Society for industrial and Applied Mathematics. All Rights reserved. Printed in The United States of America. No part of this book may be reproduced, stored, or transmitted in any manner without the written permission of the publisher. For information, write to the Association for Computing Machinery, 1515 Broadway, New York, NY 10036 and the Society for Industrial and Applied Mathematics, 3600 University City Science Center, Philadelphia, PA 19104-2688 830 graphs and K5 -minor-free graphs [14], which include planar graphs; and single-crossing-minor-free graphs [13, 14], which include K3,3 or K5 -minor-free graphs. These algorithms [11, 13, 14] apply to dominating set and several other problems related to domination, covering, and logic. Algorithms for H -minor-free graphs for a fixed graph H have been studied extensively; see e.g. [8, 21, 9, 25, 28]. In particular, it is generally believed that several algorithms for planar graphs can be generalized to H -minor-free graphs for any fixed H [21, 25, 28]. H -minor-free graphs are very general. The deep Graph-Minor Theorem of Robertson & Seymour shows that any graph class that is closed under minors is characterized by excluding a finite set of minors. In particular, any graph class that is closed under minors excludes at least one minor H . Our results. We introduce a framework for extending algorithms for planar graphs to apply to H -minor-free graphs for any fixed H . In particular, we design subexponential fixed-parameter algorithms for dominating set, vertex cover, and set cover (viewed as one-sided dominating in a bipartite graph) for H -minor-free graphs. Our framework consists of three components, as described below. We believe that many of these components can be applied to other problems and conjectures as well. First we extend the algorithm for planar graphs to bounded-genus graphs. Roughly speaking, we study the structure of the solution to the problem in k × k grids, which form a representative substructure in both planar graphs and bounded-genus graphs, and capture the main difficulty of the problem for these graphs. Then using Robertson & Seymour's graph-minor theory, we repeatedly remove handles to reduce the bounded-genus graph down to a planar graph, which is essentially a grid. Second we extend the algorithm to almost-embeddable graphs which can be drawn in a bounded-genus surface except for a bounded number of "local areas of non-planarity", called vortices, and for a bounded number of "apex" vertices, which can have any number of incident edges that are not properly embedded. Because the vortices have bounded pathwidth, their number is bounded, and the number of apexes is bounded, we are able to provide a solution to almost-embeddable graphs using our solution to boundedgenus graphs. Third we apply a deep theorem of Robertson & Seymour which characterizes H -minor-free graphs as a tree structure of pieces, where each piece is an almost-embeddable graph. Using dynamic programming on such tree structures, analogous to algorithms for graphs of bounded treewidth, we are able to combine the pieces and solve the problem for H minor-free graphs. The first step of this procedure, for bounded-genus graphs, applies to a broad class of problems called "bidimensional problems". Roughly speaking, a parameterized problem is bidimensional if the parameter is large (linear) in a grid and closed under contractions. Examples of bidimensional problems include vertex cover, feedback vertex set, minimum maximal matching, dominating set, edge dominating set, clique-transversal set, and set cover. We obtain subexponential fixed-parameter algorithms for all of these problems in bounded-genus graphs. As an special case, this generalization settles an open problem about dominating set posed by Ellis, Fan, and Fellows [16]. We also improve substantially on the results of [10]. Along the way, we establish an upper bound on the treewidth (or branchwidth) of a bounded-genus graph that excludes some planar graph H as a minor. This bound depends linearly on the size |V (H )| of the excluded graph H and the genus g (G) of the graph G, and applies and extends the graph-minors work of Robertson & Seymour. This paper is organized as follows. First, we introduce the terminology used throughout the paper, and formally define tree decompositions, treewidth, and fixed-parameter tractability in Section 2. We construct a general framework for obtaining subexponential parameterized algorithms on graphs of bounded genus in Section 3. First we introduce the concept of bidimensional problem, and then prove that every bidimensional problem has a subexponential parameterized algorithm on graphs of bounded genus. The proof techniques used in this section are very indirect and are based on deep Theorems from Robertson & Seymour's Graph Minors XI and XII. As a byproduct of our results we obtain a generalization of Quickly Excluding Planar Graph Theorem for graphs of bounded genus. In Section 4 we make a step further by developing subexponential algorithms for graphs containing no fixed graph H as a minor. The proof of this result is based on combinatorial bounds from the previous section, a deep structural theorem from Graph Minors XIV (one of the cornerstones of the Graph Minors Theory), and complicated dynamic programming. Finally, in Section 5, we present several extensions of our results and some open problems. 2 Definitions All the graphs in this paper are undirected without loops or multiple edges. The reader is referred to standard references for appropriate background [5]. The (disjoint) union of two disjoint graphs G1 and G2 , G1 G2 , is the graph G with merged vertex and edge sets: V (G) = V (G1 ) V (G2 ) and E (G) = E (G1 ) E (G2 ). Given an edge e = {x, y } of a graph G, the graph G/e is obtained from G by contracting the edge e; that is, to get G/e we identify the vertices x and y and remove all loops and duplicate edges. A graph H obtained by a sequence of edge-contractions is said to be a contraction of G. H is a minor of G if H is the subgraph of a some contraction of G. We use the notation H G (resp. H c G) for H is a 831 minor (a contraction) of G. A graph class C is a minor-closed class if any minor of any graph in C is also a member of C . A minor-closed graph class C is H -minor-free if H C . For example, a planar graph is a graph excluding both K3,3 and K5 as minors. The notion of treewidth was introduced by Robertson & Seymour [29] and plays an important role in their fundamental work on graph minors. To define this notion, first we consider the representation of a graph as a tree, which is the basis of our algorithms in this paper. A tree decomposition of a graph G, denoted by T D(G), is a pair (, T ) in which T is a tree and = {i |ii V (T )} is a family of subsets of V (G) such that: (1) V (T ) i = V (G); (2) for each edge e = {u, v } E (G) there exists an i V (G) such that both u and v belong to i ; and (3) for all v V (G), the set of nodes {i V (T )|v i } forms a connected subtree of T . To distinguish between vertices of the original graph G and vertices of T in T D(G), we call vertices of T nodes and their corresponding i 's bags. The maximum size of a bag in T D(G) minus one is called the width of the tree decomposition. The treewidth of a graph G (tw(G)) is the minimum width over all tree decompositions of G. A tree decomposition is called a path decomposition if T = (I , F ) is a path. The pathwidth of a graph G (tw(G)) is the minimum width over all possible path decompositions of G. A branch decomposition of a graph (or a hyper-graph) G is a pair (T , ), where T is a tree with vertices of degree 1 or 3 and is a bijection from the set of leaves of T to E (G). The order of an edge e in T is the number of vertices v V (G) such that there are leaves t1 , t2 in T in different components of T (V (T ), E (T ) - e) with (t1 ) and (t2 ) both containing v as an endpoint. The width of (T , ) is the maximum order over all edges of T , and the branchwidth of G, bw(G), is the minimum width over all branch decompositions of G. Robertson & Seymour [(5.1) in [31]] proved that for any connected graph G where |E (G)| 3, bw(G) 3 tw(G) + 1 2 bw(G). Also, we will need the following result of Robertson, Seymour & Thomas. (Theorems (4.3) in [31] and (6.3) in [34].) T H E O R E M 2 . 1 . ( [ 3 4 ] ) Let r 1 be an integer. Every planar graph with no (r, r)-grid as a minor has branchwidth 4r - 3. A parameter P is any function mapping graphs to nonnegative integers. The parameterized problem associated with P asks, for some fixed k , whether P (G) k for a given graph G. Let G be a graph and let v V (G). Also suppose we have a partition Pv = (N1 , N2 ) of the set of the neighbors of v . Define the splitting of G with respect to v and Pv to be the graph obtained from G by (i) removing v and its incident edges, (ii) introducing two new vertices v 1 , v 2 and (iii) connecting v i with the vertices in Ni , i = 1, 2. If H is the result of the consecutive application of the above operation on some graph G then we say that H is a splitting of G. If additionally in such a splitting process we do not split vertices that are results of previous splittings then we say that H is a fair splitting of G. We say a parameter P is -splittable, if for every graph w G and for each vertex v V (G) the result of splitting G ith respect to v has P (G ) P (G) + . Many natural graph problems are -splittable for small . Examples of 1-splittable problems are dominating set, vertex cover, edge dominating set, independent set, clique-transversal set and feedback vertex set among many others. 3 Bidimensional Parameters In this section, we define a general framework of parameterized problems for which subexponential algorithms with small constants can be obtained. Our framework is sufficiently broad that an algorithmic designer only needs to check two simple properties of any desired parameter to determine the applicability and practicality of our approach. A partially triangulated (r × r)-grid is any graph obtained by adding edges between pairs of nonconsecutive vertices on a common face of a planar embedding of a (r × r)grid. · A parameter P is called minor bidimensional with density if (i) contracting or deleting an edge in a graph G cannot increase P (G), and (ii) there exists a function f , f (x) = o(x) such that for the (r × r)-grid R, P (R) = ( r)2 + f (( r)2 ). · A parameter P is called contraction bidimensional with density if (i) contracting an edge in a graph G cannot increase P (G), (ii) there exists a function f , f (x) = o(x) such that for any partially triangulated (r × r)-grid R, P (R) ( r)2 + f (( r)2 ), and is the smallest real number for which this inequality holds. In either case, P is called bidimensional. The density of P is the minimum of the two possible densities (when both definitions are applicable). We call the sublinear function f residual function of P . Many parameters are bidimensional, mention just a few. Examples of minor bidimensional parameters along with some estimations for their densities are: vertex cover ( = 1/ 2), feedback vertex set (VS) ( 1/2) and minimum F maximal matching ( 1/ 8). Examples of contraction bidimensional parameters are dominating set ( = 1/3), edge dominating set ( = 1/ 14) and clique-transversal set ( 1/2 2). Notice that density assigns a real number in (0, 1] to any bidimensional parameter. This assignment defines a total order on all such parameters. The class of bidimensional parameterized problems contains all known from the literature planar graph parame- 832 T H E O R E M 3 . 2 . Suppose that P is a minor bidimensional parameter with density and normalization factor ( 1 and 1). Then for any graph G 2-cell embedded in a surface of Euler genus eg(), bw(G) 4 (eg() + P 3.1 The bounded treewidth approach Almost all known (G) + 1. techniques for obtaining subexponential parameterized algo- 1) rithms on planar graphs are based on the following "bounded 3.2 Combinatorial Results and Further Improvements treewidth approach" [1, 18, 24]: As part of their seminal Graph Minors series, Robertson & (I1) Prove that the treewidth/branchwidth of G is at most Seymour proved the following: P c (G) for some constant c; T H E O R E M 3 . 3 . ( [ 3 0 ] ) If G excludes a planar graph H as (I2) Compute the treewidth (or branchwidth) of G; a minor, then the branchwidth of G is at most bH and the P (I3) If treewidth is > c (G) there is no solutP n to the treewidth of G is at most tH , where bH and tH are constants io problem. If treewidth/branchwidth is c (G) run depending only on H . The current best estimate of these constants is the expo5 nential upper bound tH 202(2|V (H )|+4|E (H )|) [34]. HowAll previously known ways of obtaining the most im- ever, combining Theorem 2.1 with a lemma of [34] we have portant step (I1) are based on rather complicated techniques that the constants depend only linearly on the size of H . based on separators. Let us first give some hints why bidimensional parameters are important for the design of subex- T H E O R E M 3 . 4 . If G is a planar graph excluding a planar ponential algorithms on planar graphs. The proof of the next graph H as a minor, then its branchwidth is at most bH 4(2|V (H )| + 4|E (H )|). lemma is easy and omitted. Note that the parameter P (G) = |V (G)| is minor L E M M A 3 . 1 . Let P be a contraction (minor) bidimensional bidimensional with and equal to 1. Thus Theorems 3.1 parameter with density and normalization factor . Then P (G) < ( r)2 implies that G excludes the (r × r)-grid as and 3.2 implies the following generalization of Theorem 2.1 a minor (and all partial triangulations of the (r × r)-grid as for graphs of bounded genus. contractions). T H E O R E M 3 . 5 . If G is a graph of genus g (G) with branchwidth more than 4r(g (G) + 1), then G has a (r × r)-grid as Theorem 2.1 and Lemma 3.1 imply the following. a minor. P RO P O S I T I O N 3 . 1 . Let P be a bidimensional parameter In the same way, we are able to quickly exclude any with density and normalizatioP factor . Then for any n planar graph from bounded-genus graphs. In other words, planar graph G, tw(G) 4 (G). we generalize Theorem 3.4 as follows: Proposition 3.1 is a first hint on the importance of bidimensionality for easy achieving low bounds like the ones T H E O R E M 3 . 6 . If G is a graph of genus g (G) that excludes l required for step (I1) of the bounded treewidth approach. agpnanar graph H as a minor, then its branchwidth is at most e bH,gus ) 4(2|V (H )| + 4|E (H )|)(g (G) + 1). (G The main result of this section is the following generalization of preposition 3.1. The proof is quite lengthy and technical 3.3 Algorithmic Consequences As we already discussed, and can be found in the Appendix. the combinatorial upper bounds for branchwidth/treewidth T H E O R E M 3 . 1 . Suppose that P is an -splittable bidimen- are used for constructing subexponential parameterized alsional parameter (for 0) with density and normaliza- gorithms as follows. Let G be a graph and P be a parametertion factor ( 1 and 1). Then for any graph G 2-cell ized problem we need to solve on G. First one constructs a standard dynamic programming on graph of bounded treewidth/branchwidth which takes 2O( P (G)) n steps. ters with subexponetial parameterized algorithms. Recently, Cai et al. [6] defined a class P lanar T M I N1 and proved that for every graph G and parameter P P lanar T M I N1 , P tw(G) = O( (G)). Every problem in P lanar T M I N1 can be expressed as a special type of dominating set problem on bipartite graphs (we refer to [6] for definitions and further properties of P lanar T M I N1 ) and Proposition 3.1 yields immediately the result of Cai et al. If P is a bidimensional parameter with density and residual function f then we define the normalization factor of P as min{ | ( r)2 ( r)2 + f ( r), for any r 1 }. embedded in a surPace of Euler genus eg(), bw(G) f (G) + 1 + 8( (eg() + 1))2 . 4 (eg() + 1) Theorem 3.1 is a general theorem which applies for any -splittable bidimensional parameter. For minor bidimensional parameters the bound for branchwidth can be further improved (we omit the proof because it is similar to that of Theorem 3.1). 833 branch/tree decomposition of G that is optimal or 'almost' optimal. A (, , )-approximation scheme for branchwidth/treewidth consists of, for every w, an O(2 w n )-time algorithm that, given a graph G, either reports that G has branchwidth/treewidth at least w or produces a branch/tree decomposition of G with width at most w. For example, the current best schemes are a (3 + 2/3, 3.698, 3 + )approximation scheme for treewidth [3] and a (3, lg 27, 2)approximation scheme for branchwidth [32]. If the branchwidth/treewidth of a graph is "large", then combinatorial upper bounds come into play and we conclude that P has no solution on G. Otherwise we run dynamic programming on graphs of bounded branchwidth/treewidth and compute P (G). Thus we conclude with the main algorithmic result of this section: T H E O R E M 3 . 7 . Let P be a bidimensional parameter with density > . Suppose there is an algorithm for the associated parameterized problem that runs in O(2aw nb ) time given a tree/branch decomposition of the graph G with width w. Suppose also that we have a (, , )-approximation scheme for treewidth/branchwidth. Set = 1 in the case of branchwidth and = 1.5 in the case of treewidth. Then the parameterized problem asking whe er P (G) k can be solved th max{a , } 4 (g (G)+1)( k+1+µ (g (G)+1)) max{b,} in O(2 n ) time for minor bidimensional parameter P (G) with density and normalization factor , where µ is 0 if P is minor bidimensional and is 2 if P is -splittable contraction bidimensional. The first condition of the theorem holds with small values of a and b for many examples of bidimensional parameters; see [1, 2, 7, 14, 18, 26]. Observe that the correctness of our algorithms is simply based on Theorems 3.1 and 3.2, despite their nonalgorithmic natures, and (, , )approximation scheme for branch/tree decomposition. We note that the time bounds we provide do not contain any hidden constants, and the constants are reasonably low for a broad collection of problem covering all the problems for s O ( k) O (1) which there already exist 2 n -time algorithms. 4 H -minor free graphs In this section we will generalize the results on graphs of bounded genus to graphs with excluded minors. 4.1 Characterizations of H -minor-free graphs In this section, we describe the deep theorem of Robertson & Seymour on graphs excluding a fixed graph H as a minor. Intuitively, Robertson-Seymour's theorem says for every graph H , every H -minor-free graph can be expressed as a tree-structure of "pieces", where each piece is a graph which can be drawn in a surface in which H cannot be drawn, except for a bounded number of "apex" vertices and a bounded number of "local areas of non-planarity" called vortices. Here the bounds only depend on H . A graph G is h-almost embeddable in S if there exists a vertex set X of size at most h called apices such that G - X can be written as G0 G1 · · · Gh , where · G0 has an embedding in S ; · the graphs Gi , called vortices, are pairwise disjoint; · there are (not necessarily distinct) faces F1 , . . . , Fh of G0 in S , and there are pairwise disjoint disks D1 , . . . , Dh in S , such that for i = 1, . . . , h, Di Fi and Ui := V (G0 ) V (Gi ) = V (G0 ) Di ; and · the graph Gi has a path decomposition (Bu )uUi of width less than h, such that u Bu for all u Ui . We note that the sets Bu are ordered by the ordering of their indices u as points in Ci , where Ci is the boundary cycle of Fi in G0 . An h-almost embeddable graph is called apex-free if the set X of apices is empty. Suppose G1 and G2 are graphs with disjoint vertex-sets and k 0 is an integer. For i = 1, 2, let Wi V (Gi ) form a clique of size k and let Gi (i = 1, 2) be obtained from Gi by deleting some (possibly no) edges from Gi [Wi ] with both endpoints in Wi . Consider a bijection h : W1 W2 . We define a k -sum1 G of G1 and G2 , denoted by G = G1 k G2 or simply by G = G1 G2 , to be the graph obtained from the union of G1 and G2 by identifying w with h(w) for all w W1 . The images of the vertices of W1 and W2 in G1 k G2 form the join set. In the rest of this section, when we refer to a vertex v of G in G1 or G2 , we mean the corresponding vertex of v in G1 or G2 (or both). Now, the result 2 of Robertson & Seymour is as follows. T H E O R E M 4 . 1 . ( [ 3 3 ] ) For every graph H there exists an integer h 0 only depending on |V (H )| such that every H -minor-free graph can be obtained by at most h-sums of graphs of size at most h and h-almost-embeddable graphs in some surfaces in which H cannot be embedded. In particular, if H is fixed, any surface in which H cannot be embedded has bounded genus. Thus, the summands in the theorem are h-almost-embeddable graphs in boundedgenus surfaces. This structural theorem plays an important role in obtaining the rest of the results of this paper. From the algorithmic point of view, because Robertson & Seymour [33] have shown that every minor-closed class of graphs has a polynomial-time membership test, one can observe the following theorem used by Grohe [19, Lemma 15]. Also, Seymour [35] claims that we can construct the clique-sum decomposition algorithmically using the proof of the Theorem 4.1. 1 It is worth mentioning that is not a well-defined operator and it can have a set of possible results. 2 Theorem 4.1 is very general and has not appeared in print so far. However already several nice applications (see e.g. [4, 19]) are known. 834 THEOREM 4 . 2 . For any graph H , there is an algorithm with running time nO(1) that either computes a clique-sum decomposition as in Theorem 4.1 for any given H -minorfree graph G, or outputs that G is not H -minor-free. The exponent in the running time depends on H . Let G be an h-almost embeddable on a surface of genus g in a clique-sum decomposition of a graph G . Suppose the set of apices in G is X . Assume G has clique-sums with graphs G1 , · · · , Gp via joinsets W1 , · · · , Wp , where |Wi | h, 1 i p. A clique Wi is called fully dominated by a set S V (G) if V (Gi ) - X NG (S ), otherwise clique Wi is called partially dominated by S . A vertex v of G is fully dominated by a set S if NG [V (G)-X ] (v ) NG (S ). We note that in the above definition, the only edges that appear in G, but may not appear in G are the edges among vertices of |Wi |, 1 i p. T H E O R E M 4 . 3 . Let G be an h-almost embeddable on a surface of genus g in a clique-sum decomposition of a graph G . Assume G has clique-sums with graphs G1 , . . . , Gp via join sets W1 , . . . , Wp , where |Wi | h, 1 i p. Suppose G has a dominating set of size at most k . Then there is a subset S V (G) of size at most h such that if we remove all fully dominated vertices which are not included in any ^ partially dominat clique Wi from G and obtain graph G, ed ^ ) = O(h2 g k + h + g 2 ) = O( k ). tw(G In order to prove Theorem 4.3 we need first some preliminary results. A vertex w is called r-dominated by a set S , if the distance from w to a vertex v S is at most r. An r-dominating set is a set S of vertices such that every vertex of the graph is r-dominated by S . The problem of finding an r-dominating set of size k is also called the (k , r)-center problem (see Section 5). From the main combinatorial result of [11], r-dominating set is a 1splittable bidimensional parameter. This and Theorem 3.1 imply the following. L E M M A 4 . 1 . For any constant r, if a graph G of genus g has an r-dominating set of size at most k , then the treewidth of G is at most O(g k + g 2 ). Now, we extend this result for apex-free h-almost embeddable graphs (the proof is not hard and is omitted). L E M M A 4 . 2 . Consider an apex-free h-almost-embeddable graph G = G0 G1 · · · Gh . Suppose further that, for each 1 i h, Ui = {u1 , u2 , . . . , umi } forms a path in i i i G0 . Then tw(G) (h2 + 1)(tw(G0 ) + 1) - 1. L E M M A 4 . 3 . For any constant r, an apex-free h-almostembeddable graph G embedded on a surface of genus g with a set S V (G) of size at most k which r-dominates every vertex G which is not in vortex has treewidth at most of a O(h2 g k + h + g 2 ) = O(g k ) (g and h are constants). Proof. Consider an apex-free h-almost embeddable graph G = G0 G1 · · · Gh in a surface of genus g . Suppose Ui = {u1 , u2 , . . . , umi }. Let G0 be the graph obtained i i i from G0 by adding new vertices c1 , c2 , · · · , ch and edges (ci , uj ) and (uj , uj +1 ) (where j + 1 is treated modulo mi ) i i i for all 1 i h and 1 j mi . Notice that by adding these edges, vertices Ui , 1 i h, form a path in G0 . If G has the aforementioned r-dominating set of size k , then G0 has an r-dominating set of size at most k + h: just delete all vertices in the r-dominating set that are in Gi - G0 , 1 i h, and add instead all new vertices c1 , c2 , · · · , ch to the r-dominating set. Notice that G0 is embeddable on , since G0 is embeddable. Thus, according to Lemma 4.1 it has treewidth at most O(g k + h + g 2 ). By Lemma 4.2, the treewidth of G = G0 G1 · · · Gh is O((h2 + 1)(g k + h + 1) + g 2 - 1). Ui forming a path in G0 . Because G is a subgraph of G , the lemma follows. Proof of Theorem 4.3 Suppose X is the set of apices in G, so that G - X is an apex-free h-almost embeddable graph. Let D be a dominating set of size k of G and let S = X D. We claim that S is our desired set. The rest of ^ the proof is as follows: we construct a set D of size at most ^ ^ k for G - X which 2-dominates every vertex v of G - X ^ which is not included in any vortex. Then since G - X is an apex-free h-almost-embeddable on a surface of genus g with a 2-dominating-type set of size at most k desired by Lemma 4.3, it has treewidth at most O(h2 g k + h + g 2 ). Then we can add vertices of X to all bags and still have a tree decomposition of width O(h2 g k + h + g 2 ), as desired. We ^ ^ construct D from D as follows. First, we set D = D V (G). For each 1 i p, if D (V (Gi ) - Wi ) = and Wi X , ^ we add an arbitrary vertex w Wi - X to D. Here we say ^ a vertex v of D is mapped to a vertex w of D if v = w or if v D (V (Gi ) - Wi ) and vertex w Wi - X is the one that ^ we have added to D. One can easily observe that since each ^ new vertex in D is in fact accounted by a unique vertex in D, ^ |D| k . It only remains to show that D is a 2-dominating ^ ^ set for G - X . If a vertex v V (G) - X is not fullydominated, then there exists a vertex w NG (v ) which is not dominated by S and thus not dominated by X (since S = D X ). It means v is 2-dominated by a vertex u of ^ G - X which dominates w (we note that u can be originally a vertex u in (V (Gi ) - Wi ) D which is mapped to u in ^ D). Also, we note that for each clique Wi in which there is a mapped vertex of D, this vertex dominates all vertices ^ of Wi - X in G - X and thus we keep the whole clique Wi - X in G. It only remains to show that every vertex of a partially dominated clique Wi is 2-dominated by a vertex ^ of G - X . We consider two cases: if Wi S = , since V (Gi ) - Wi = , there must exists a (mapped) vertex of ^ D in Wi - X and we are done. Now assume Wi S = . ^ If Wi X then Wi (V (G) - X ) = and we are done ^ (since there is no clique in G - X at all.) Otherwise, there 835 exists a vertex Wi - X . If (V (Gi ) - Wi ) NG (S ) = , then V (Gi ) D = . Thus there exists a mapped vertex w Wi - X and we have 1-dominated vertices of Wi - X . As mentioned before if D (Wi - X ) = , vertices Wi - X are 1-dominated and we are done. The only remaining case is the case in which there exists a vertex w Wi - X which is dominated by a vertex x V (G) and by assumption w NG (S ) (we note that in this case, there is no dominating vertex in V (Gi ) - Wi for any i for which w Wi .) It means ^ vertex x is not fully dominated and thus it remains in G. In addition, vertex x 2-dominates all vertices of Wi - X , since Wi is a clique in G and thus all vertices of Wi - X are 2dominated. This completes the proof of the theorem. 4.2 Main result T H E O R E M 4 . 4 . One can test whether an H -minor-free graph G has a dominating set of size at most k in time 2O( k) nO(1) , where the constants in the exponents depend on H . Proof. First, using the nO(1) -time algorithm of Theorem 4.2, we obtain the clique-sum decomposition of graph G . In fact, this clique-sum decomposition can be considered as a generalized tree decomposition of G . More precisely, we consider the clique-sum decomposition as a rooted tree. We try to find a k -dominating set in this graph using a two-level dynamic programming. Suppose a graph G is an h-almost embeddable on a surface of genus g in a clique-sum decomposition of a graph G . Assume G has clique-sums with graphs G0 , . . . , Gp via join sets W0 , W1 , . . . , Wp , where |Wi | h, 0 i p. Also assume that G0 is considered as the parent of G and G1 , . . . , Gp are considered as children of G. Colorings. The subproblems in our first-level dynamic program are defined by a coloring of the vertices in Wi . Each vertex will be assigned one of 3 colors, labelled 0, 1, and 1. The meaning of the coloring of a vertex v is as follows. Color 0 represents that vertex v belongs to the chosen dominating set. Colors 1 and 1 represent that the vertex v is not in the chosen dominating set. Such a vertex v must have a neighbor w in the dominating set (i.e., colored 0); we say that vertex w resolves vertex v . Color 1 for vertex v represents that the dominating vertex w is in the subtree of the clique-sum decomposition rooted at the current graph G, whereas 1 represents that the dominating vertex w is elsewhere in the clique-sum decomposition. Intuitively, the vertices colored 1 have already been resolved, whereas the vertices colored 1 still need to be assigned to a dominating vertex. Locally valid colorings. A coloring of the vertices of Wi is called locally valid with respect to sets S1 , S2 V (G) if the following properties hold: · for any two adjacent vertices v and w in Wi , if v is colored 0, w is colored 1; and · if v S1 Wi , then v is colored 0; and · if v S2 Wi , then v is not colored 0. Our colorings are similar to that of previous work (e.g., [1]), but we use them in a new dynamic-programming framework that acts over clique-sum decompositions instead of tree decompositions. Dynamic program subproblems. Our first-level dynamic program has one subproblem for each graph G in the cliquesum decomposition and for each coloring c of the vertices in W0 . Because each join set has at most h vertices, the number of subproblems is O(n · 3h ). We define D(G, c) to be the size of the minimum "semi"-dominating set of the vertices in subtree rooted at G subject to the following restrictions: 1. Vertices colored 1 are adjacent to at least one vertex in the dominating set. (Vertices colored 1 are dominated "for free".) 2. Vertices colored 0 are precisely the vertices in the dominating set. 3. Vertices in W0 are colored according to c. If we solve every such subproblem, then in particular, we solve the subproblems involving the root node of the clique-sum decomposition in which every vertex is colored 0 or 1 . The final dominating set of size k is given by the best solution to these subproblems. Induction step. Suppose for each coloring c of Wi , 1 i p, we know D(Gi , c). If the graph G is of size at most h, then we can try all colorings in O(3h · h2 ) = O(1) time (where the factor of h2 is for checking validity). Thus, we focus on almost-embeddable graphs G. First, we guess a subset X of size at most h. Then for each subset S of X , we put the vertices of S in the dominating set and forbid vertices of X - S from being in the dominating set. Now we remove from G all fully dominated vertices of G - X that are not included in any partially dominated clique Wi . all C ^ ^ the resulting graph G. By Theorem 4.3, tw(G) = O( k ). We can obtain such a ee decomposition of width 3 + 2/3 tr times optimum, in 2O( k) n3+ time by a result of Amir [3]. All vertices absent from this tree decomposition are fully dominated and thus, in any minimum dominating set that includes S , they will not appear except the following case. It is possible that up to |X - S | = O(h) vertices, which are either fully dominated or belong to V (Gi ) - Wi where Wi is fully dominated, appear in the dominating set to dominate vertices of X - S . Call the set of such vertices S . We can guess this set S by choosing at most h vertices among the discarded vertices that have at least one neighbor in X - S , and then add S to the dominating set. On the other hand, for any partially dominated clique Wi , we know that all of its vertices are present in the tree decomposition; because they form a clique, there is a bag i in any tree decomposition that contains all vertices of Wi . We find i in our tree decomposition and map Wi and Gi to this bag. We also 836 assume W0 is contained in all bags, because its size is at most h. Now, for each coloring c of W0 , we run the dynamic program of Alber et al. [1] on the tree decomposition, with the restriction that the colorings of the bags are locally valid with respect to S1 := S S and S2 := X - S , and are consistent with the coloring c of W0 . For each bag i to which we mapped Gi , we add to the cost of the bag the value D(Gi , c ) for the current coloring c of Wi . Using this dynamic program, we can obtain D(G, c) for each coloring c of W 0 . Running time. The running time for each coloring c of W0 and each choice of S is 2O( k) n according to [1]. We have 3h choices for c, O(nh+1 ) choices for X , O(2h ) choices for S , and O(nh+1 ) choices for S . Thus the running time for this inductive step is 6h n2h+2 2O( k) . There are O(n) graphs in the clique-sum decomposition of G. Therefore, the total running time of the algorithm is O(6h n2h+3 2O( k) ) + nO(1) (the latter term for creating the clique-sum decompo sition), which is 2O( k) nO(1) as desired. 5 Conclusions and Future Work Theorem 4.4 can be used to obtain subexponential algorithms not only for dominating set problems. For example, for vertex cover one can use the following reduction. For a graph G let G be the graph obtained from G by adding a path of length two between any pair of adjacent vertices. The following lemma is obvious. L E M M A 5 . 1 . For any Kh -minor free graph G, h 4, and integer k 1 · G is Kh -minor free, · G has vertex cover of size k if and only if G has a dominating set of size k . Combining Lemma 5.1 with Theorem 4.4 we conclude that parameterized vertex cover can be solved in subexponential time on graphs with an excluded minor. Another example is the set cover problem. Given a collection C = (C1 , C2 , . . . , Cm ) of subsets of a finite set S = (s1 , s2 , . . . , sn ), a set cover is a subcollection C C such that Ci C = S . Minimum set cover (SC) problem is to find a cover of minimum size. For a SC problem (C, S ) its graph GS is a bipartite graph with bipartition (C, S ). Vertices si and Cj are adjacent in GS if and only if si Cj . Theorem 4.4 can be used to prove that SC with GS H -minor free for some fixed graph H , can be References solved in subexponential time. In fact, for a given graph GS we construct an auxiliary graph AS by adding new vertices [1] J . A L B E R , H . L . B O D L A E N D E R , H . F E R NAU , T. K L O K S , v , u, w and making adjacent v to {u, w, C1 , C2 , . . . , Cm }. A N D R . N I E D E R M E I E R , Fixed parameter algorithms for domThen inating set and related problems on planar graphs, Algorith· (C, S ) has a set cover of size k if and only if AS has a mica, 33 (2002), pp. 461­493. dominating set of size k + 1. [2] J . A L B E R , H . F E R NAU , A N D R . N I E D E R M E I E R, Parameterized complexity: Exponential speed-up for planar graph prob· If GS is Kh -minor free then AS is Kh+1 -minor free. We believe that we can generalize Theorem 4.4 in order to obtain a fixed-parameter algorithm with exponential speed-up for the (k , r)-center problem on H -minor-free graphs. The (k , r)-center problem is a generalization of the dominating set problem in which one asks whether an input graph G has k vertices (called centers) such that every vertex of G is within distance r from some center. Demaine et al. [11] consider this problem for planar graph and map graphs and present a generalization of dynamic programming mentioned in the proof of Theorem 4.4 to solve the (k , r)-center problem for graphs of bounded treewidth/branchwidth. Using this dynamic programming and a generalization of Lemma 4.3, one can obtain the desired result for H -minor-free graphs. Using the solution for the (k , r)-center problem in [11], we can solve the dominating set problem in constant powers of H -minor-free graphs, the most general class of graphs so far for which one can obtain the exponential speed-up. However it is an open and tempting question if our technique can be generalized to solve in subexponential time on graphs with excluded minors every problem solved in subexponential time on bounded-genus graphs. We also suspect that there is a strong connection between bidimensional parameters and the existence of linearsize kernels for the corresponding parameterized problems in bounded-genus graphs. The final question is if the upper bounds Theorems 3.1 and 3.2 can be extended to larger graph classes. The first step in this direction was obtained by the authors for minorclosed graph families: A graph family F has dominationtreewidth property if there is some function f (d) such for that every graph G F with dominating set of size k , tw(G) f (k ). It was shown that a minor-closed graph family has domination-treewidth property if and only if this is bounded local treewidth family. We conjecture that for any bidimensional parameter P and minor-closed graph family P (G)) for every G F if and only if F F , tw(G) = O( is of bounded local treewidth. This conjecture was recently proved for the dominating-set parameter [12]. Acknowledgments. The authors are indebated to Paul D. Seymour for many discussions that led to combinatorial results of this paper and for providing a portal into the Graph Minor Theory. We also thank Naomi Nishimura and Prabhakar Ragde for encouragement and helpful discussions. 837 lems, in Electronic Colloquium on Computational Complexity (ECCC), Germany, 2001. [3] E . A M I R, Efficient approximation for triangulation of minimum treewidth, in Uncertainty in Artificial Intelligence: Proceedings of the Seventeenth Conference (UAI-2001), San Francisco, CA, 2001, Morgan Kaufmann Publishers, pp. 7­15. ¨ [4] T. B O H M E , J . M A H A R RY, A N D B . M O H A R, Ka,k minors in graphs of bounded tree-width, J. Combin. Theory Ser. B, 86 (2002), pp. 133­147. [5] J . A . B O N DY A N D U . S . R . M U RT Y, Graph Theory with Applications, American Elsevier Publishing Co., Inc., New York, 1976. [6] L . C A I , M . F E L L OW S , D . J U E D E S , A N D F. RO S A M O N D, On efficient polynomial-time approximation schemes for problems on planar structures, manuscript, (2003). [7] M . - S . C H A N G , T. K L O K S , A N D C . - M . L E E, Maximum clique transversals, in Proceedings of the 27th International Workshop on Graph-Theoretic Concepts in Computer Science, Mathematical Programming Society, Boltenhagen, Germany, 2001, pp. 300­310. [8] M . C H A R I K A R A N D A . S A H A I, Dimension reduction in the l1 norm, in The 43th Annual Symposium on Foundations of Computer Science (FOCS'02), 2002, pp. 551­560. [9] C . C H E K U R I , A . G U P TA , I . N E W M A N , Y. R A B I N OV I C H , A N D S . A L I S TA I R , Embedding k -outerplanar graphs into 1, in ACM-SIAM Symposium on Discrete Algorithms (SODA'03), 2003, pp. 527­536. [10] J . C H E N , I . K A N J , L . P E R KOV I C , E . S E D G W I C K , A N D G . X I A, Genus characterizes the complexity of graph problems: Some tight results, in 30th International Colloquium on Automata, Languages and Programming (ICALP 2003), pp. 845­856. [11] E . D . D E M A I N E , F. V. F O M I N , M . H A J I AG H AY I , A N D D . M . T H I L I KO S, Fixed-parameter algorithms for the (k, r)center in planar graphs and map graphs, in 30th International Colloquium on Automata, Languages and Programming (ICALP 2003), pp. 829­844. [12] E . D . D E M A I N E A N D M . H A J I AG H AY I, Equivalence of local treewidth and linear local treewidth and its algorithmic applications, in Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'04), 2004. To appear. [13] E . D . D E M A I N E , M . H A J I AG H AY I , A N D D . M . T H I L I KO S, A 1.5-approximation for treewidth of graphs excluding a graph with one crossing, in The 5th International Workshop on Approximation Algorithms for Combinatorial Optimization (Italy, APPROX 2002), LNCS, 2002, pp. 67­80. [14] E . D . D E M A I N E , M . H A J I AG H AY I , A N D D . M . T H I L I KO S, Exponential speedup of fixed parameter algorithms on K3,3 minor-free or K5 -minor-free graphs, in The 13th Anual International Symposium on Algorithms and Computation-- ISAAC 2002 (Vancouver, Canada), Springer, Lecture Notes in Computer Science, Berlin, vol.2518, 2002, pp. 262­273. [15] R . G . D OW N E Y A N D M . R . F E L L OW S, Parameterized Complexity, Springer-Verlag, New York, 1999. [16] J . E L L I S , H . FA N , A N D M . F E L L OW S, The dominating set problem is fixed parameter tractable for graphs of bounded genus, in The 8th Scandinavian Workshop on Algorithm Theory--SWAT 2002 (Turku, Finland), Springer, Lecture Notes in Computer Science, Berlin, vol. 2368, 2002, pp. 180­ 189. [17] M . R . F E L L OW S, Parameterized complexity: The main ideas and some research frontiers, in The 12th Annual International Symposium on Algorithms and Computation (ISAAC 2001), 2001, pp. 291­307. [18] F. V. F O M I N A N D D . M . T H I L I KO S, Dominating sets in planar graphs: Branch-width and exponential speed-up, in Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, 2003, pp. 168­177. [19] M . G RO H E, Local tree-width, excluded minors, and approximation algorithms. To appear in Combinatorica. [20] M . G RO H E A N D J . F L U M, The parameterized complexity of counting problems, in The 43rd IEEE Symposium on Foundations of Comupter Science (FOCS 2002), 2002, pp. 538­547. [21] A . G U P TA , I . N E W M A N , Y. R A B I N OV I C H , A N D S . A L I S TA I R , Cuts, trees and l1 -embeddings of graphs, in The 40th Annual Symposium on Foundations of Computer Science (FOCS'99), 1999, pp. 399­409. [22] G . G U T I N , T. K L O K S , A N D C . L E E, Kernels in planar digraphs, in Optimization Online, Mathematical Programming Society, Philadelphia, 2001. [23] T. W. H AY N E S , S . T. H E D E T N I E M I , A N D P. J . S L AT E R, Fundamentals of domination in graphs, Marcel Dekker Inc., 1998. ´ [24] I . K A N J A N D L . P E R KOV I C, Improved parameterized algorithms for planar dominating set, in Mathematical Foundations of Computer Science--MFCS 2002, Springer, Lecture Notes in Computer Science, Berlin, vol.2420, 2002, pp. 399­ 410. [25] P. N . K L E I N , S . A . P L OT K I N , A N D S . R AO, Excluded minors, network decomposition, and multicommodity flow, in The Twenty-Fifth Annual ACM Symposium on Theory of Computing (STOC'93), 1993, pp. 682­690. [26] T. K L O K S , C . M . L E E , A N D J . L I U, New algorithms for kface cover, k-feedback vertex set, and k-disjoint set on plane and planar graphs, in The 28th International Workshop on Graph-Theoretic Concepts in Computer Science(WG 2002), Springer, Lecture Notes in Computer Science, Berlin, vol. 2573, 2002, pp. 282­296. [27] B . M O H A R A N D C . T H O M A S S E N, Graphs on surfaces, Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 2001. [28] S . A . P L OT K I N , S . R AO , A N D W. D . S M I T H, Shallow excluded minors and improved graph decompositions, in The Fifth Annual ACM-SIAM Symposium on Discrete Algorithms(SODA'94), 1994, pp. 462­470. [29] N . RO B E RT S O N A N D P. D . S E Y M O U R, Graph minors. II. Algorithmic aspects of tree-width, J. Algorithms, 7 (1986), pp. 309­322. [30] N . RO B E RT S O N A N D P. D . S E Y M O U R, Graph minors. V. Excluding a planar graph, J. Combin. Theory Ser. B, 41 (1986), pp. 92­114. [31] , Graph minors. X. Obstructions to tree-decomposition, J. Combin. Theory Ser. B, 52 (1991), pp. 153­190. [32] , Graph minors. XIII. The disjoint paths problem, J. Combin. Theory Ser. B, 63 (1995), pp. 65­110. 838 [33] N . RO B E RT S O N A N D P. D . S E Y M O U R, Graph minors XVI. excluding a non-planar graph, (2003). To appear in J. Combin. Theory Ser. B, available electronically in journal site. [34] N . RO B E RT S O N , P. D . S E Y M O U R , A N D R . T H O M A S, Quickly excluding a planar graph, J. Combin. Theory Ser. B, 62 (1994), pp. 323­348. [35] P. S E Y M O U R. Personal communication. · each connected component Gi of G can be 2-cell embedded in a surface with Euler genus strictly smaller than eg() and is a contraction of some graph G obtained from G after splittings. i Proof. [ of Theorem 3.1] We use induction on the Euler genus of . In case eg() = 0, Lemma 3.1 implies that if P (G) < ( r)2 , then G excludes the (r × r)-grid as a minor. Indeed, this is obvious in case P is minor bidimensional. If P is contraction bidimensional, then it is enough to observe that if the planar graph G can be transformed to H via a sequence of edge contractions or removals, then by applying only the contractions in this sequence we get a partial triangulation of H . Using now Theorem 2.1 we get that if P (G) < ( r)2 , then bw(G) 4r - 6. If we set P P r= (G) + 1, we have that bw(G) 4 (G) - 2. As , , 0, the induction base is done. Suppose now that eg() 1 and that induction hypothesis holds for any graph 2-cell embedded in a sphere with Euler genus less than eg(). Let G be a graph embedded in . We set k = P (G) and we claim that the representativity of G is 4 k + 1 . Lemma 3.1 implies that if k < ( r)2 , then G excludes any triangulation of the (r × r)-grid as a contraction. By the contrapositive of Lemma A.1, this imies that the represenpl tativity of G is < 4r. If we set r = k + 1 + 1, we have that the representativity of G is 4 k + 1 . Let N be a min imum size non-conactible noose N on meeting vertices of tr G where 4 k + 1 . By Lemma A.2, there is a fair split ting along the vertices met by N such that one of the conditions (1) or (2) holds. Let G be the resulting graph and let be a sphere such that eg( ) eg() - 1 and every component of G is 2cell embedable in . e claim that in each of the cases (1), (2), W bw(G ) 4 eg() k + + 1 + 8( )2 (eg())2 . Case (1): We apply the induction hypothesis on G and get that P bw(G ) 4 (eg( ) + 1) (G ) + 1 + 8( )2 (eg( ) + 1)2 . As G is obtained from G after splittings and P is an -splittable parameter, we have P (G ) k + . Taking in mind that eg ( ) eg() - 1, we obtain bw(G ) 4 eg() k + + 1 + 8( )2 (eg())2 . Case (2): We apply the induction hypothesis on each of the connected components of G. Let Gi be such a component. We get P that bw(Gi ) 4 (eg( )+1) (Gi ) + 1+8( )2 (eg( )+ 2 1) . As Gi is a contraction of some graph G obtained from G i after splittings and P is an -splittable parameter, we get that P (Gi ) P (G ) k + . Again since eg( ) eg() - 1, i we have bw(Gi ) 4 eg() k + + 1 + 8( )2 (eg())2 . Notice that bw(G ) = maxi (bw(Gi )) which in turn implies 2 ) that bw(G 4 eg() k + + 1 + 8( ) (eg())2 . As G is the result of consecutive vertex splittings on G and the splitting operation cannot increase the branchwidth more than one we get th bw(G) bw(G ) + . Therefore, bw(G) at 4 eg() k + + 1 + 8( )2 (eg())2 + 4 (eg() + 1) k + 1 + 8( (eg() + 1))2 . A Proof of Theorem 3.1 We need first some basic definitions and results. A surface is a compact 2-manifold, without boundary. A line in is subset homeomorphic to [0, 1]. An O-arc is a subset of homeomorphic to a circle. Let G be a graph 2-cell embedded in , i.e., every region in the embedding is homeomorphic to a disc. To simplify notations we do not distinguish between a vertex of G and the point of used in the drawing to represent the vertex or between an edge and the line representing it. We also consider G as the union of the points corresponding to its vertices and edges. That way, a subgraph H of G can be seen as a graph H where H G. We call by region of G any connected component of - E (G) - V (G). (Every region is an open set.) We use the notation V (G), E (G), and R(G) for the set of the vertices, edges and regions of G. If , then denotes the closure of , and the boundary of is b d() = - . An edge e (a vertex v ) is incident with a region r if e b d(r) (v b d(r)). A subset of meeting the drawing only in vertices of G is called G-normal. If an O-arc is G-normal then we call it noose. The length of a noose is the number of its vertices. is an open disc if it is homeomorphic to {(x, y ) : x2 + y 2 < 1}. We say that a disc D is bounded by a noose N if N = b d(D). A graph G 2-cell embedded in a connected surface is -representative if every noose of length < is contractable (null-homotopic in ). Lemma A.1 bounds the representativity of graphs excluding some graphs as a minor/contraction (we remove its proof because of lack of space). L E M M A A . 1 . Let G be a graph 2-cell embedded in a non-planar surface of representativity at least . Then G contains as a contraction a partially triangulated (/4 × /4)-grid. The Euler genus eg() of a nonorientable surface is equal to the nonorientable genus g () (or the crosscap number). The ~ Euler genus eg() of an orientable surface is 2g (), where g () is the orientable genus of . The following lemma is very useful in proofs by induction on the genus. The first part of the lemma follows from Lemma 4.2.4 (corresponding to nonseparating cycle) and the second part follows from Proposition 4.2.1 (corresponding to surface separating cycle) in [27]. L E M M A A . 2 . Let G be a connected graph 2-cell embedded in a non-planar surface , and let N be a noncontractible noose on G. Then there is a fair splitting G of G affecting the set S = (v1 , . . . , v ) of the vertices of G met by N such that one of the following holds · G can be 2-cell embedded in a surface with Euler genus strictly smaller than eg(). 839