• O.k p log k/. • For all {v;w} 2 E, there is an i 2 I with v, w 2 Xi . • For all v 2 V , the set {i 2 I jv 2 Xi} induces a connected subtree of T . The width of a tree decomposition is max i2I jXi j 1, and the treewidth of a graph G is the minimum width of a tree decomposition of G (Fig. 1). An alternative definition is in terms of chordal graphs. A graph G D .V; E/ is chordal, if and only if each cycle of length at least 4 has a chord, i.e., an edge between two vertices that are not successive on the cycle. A graph G has treewidth at most k, if and only if G is a subgraph of a chordal graph H that has maximum clique size at most k. A third alternative definition is in terms of orderings of the vertices. Let be a permutation (called elimination scheme in this context) of the vertices of G D .V; E/. Repeat the following step for i = 1,. . . , jV j: take vertex .i/, turn the set of its neighbors into a clique, and then remove v. The width of is the maximum over all vertices of its degree when it was eliminated. The treewidth of G equals the minimum width over all elimination schemes. In the treewidth problem, the given input is an undirected graph G D .V; E/, assumed to be given in its adjacency list representation, and a positive integer k < jV j. The problem is to decide if G has treewidth at most k and, if so, to give a tree decomposition of G of width at most k.