Treewidth: An Introduction to a Key Graph Parameter

AN INTRODUCTION TO TREEWIDTH Daniel Lokshtanov, UCSD

WHAT IS TREEWIDTH? A graph parameter that measures how close a graph is to being a tree. Graphs with constant treewidth share many properties with trees, this can be exploited algorithmically For polynomial time algorithms (ex; minor testing) Faster Exponential Time Algorithms for hard problems Space-Bounded Computation Parameterized Algorithms Approximation Algorithms Preprocessing Heuristics (Kernelization)

ORIGINS Discovered independently in several fields; graph grammars, graph minors, logic. Several different names in the 80 s. The ones i remember are Treewidth and partial k-trees. Generalized to digraphs, hypergraphs, matroids ... here; only undirected graphs.

EVERYTHING IS EASY ON TREES Independent Set (ISET): IN: Graph G, integer k. Q: Does G have a vertex set S of size k such that every pair of vertices in S are non-adjacent? NP-Complete in general, but linear time for trees. Why?

DYNAMIC PROGRAMMING FOR ISET ON TREES Root the tree T at r Let Tvbe the subtree of T rooted at r In[v] = Largest iset S in Tvsuch that v S. Out[v] = Largest iset S in Tvsuch that v S. Best[v] = Largest iset in Tv. In[v] = uOut[u] Out[v] = uBest[u] Best[v]=max{In[v], Out[v]}

GENERALIZE TREES? Dynamic Programming works because the information must transfer through a single vertex. Generalize to information transfer through a constant number of vertices. Width = 3 Tree-Partition

MORE GENERAL DYNAMIC PROGRAMMING G = graph T = decomposition tree. For each node v of T there is a bag Bvthat contains vertices of G. The bags of T partition the vertices of G. Root the tree T, Tvis the subtree rooted at T. Gvis G[ u TvBu]

ISET ON TREE-PARTITIONS Define Best[v,S] where v is a node in T and S Bv to be the size of the largest independent set X of Gv such that X Bv= S. Test[X] = 1 if G[X] is independent, - if not. Best[v,S] = |S| + uMaxS Bu Test[S S ]

ARE TREE-PARTITIONS THE RIGHT GENERALIZATION? u v3 v1 v2 vn-2 vn-1 vn What is the tree-partition-width? Decomposition tree must be a star with the bag B containing u in the center. At least one component of size n/|B| tree-partition-width n1/2

TOWARDS TREE-WIDTH Need to make tree-partitions more robust; adding a new vertex should increase the width by at most one, retaining nice algorithmic properties. What if every vertex could appear several times, but every edge only needed to appear once? v y Problem: Can decompose anything as a path! u v u v u v x x x x u y y y

TREE-DECOMPOSITION DEFINITION A tree-decomposition of a graph G=(V,E) is a tree T and a collection X of bags, with a bag Ba X for every node a T, such that: For every uv E, some bag contains both u and v For every vertex v V, v appears in a non-empty, connected subtree of T. Treewidth is NP-complete (Yannakakis) 1. 2. The width of the decomposition is max |Bv| - 1 The treewidth of G is the smallest width over any decomposition.

EXAMPLE Treewidth of trees is 1 {2} {3} 2 {8,a} 3 c a 8 4 1 7 b 9 5 6

CONNECTIVITY PROPERTIES: Lemma: Let (T,X) be a tree-decomposition of G, and let e=ab be an edge in T, splitting T into T1 and T2. Set V1= v T1Bvand V2= v T2Bv. Then, V1 V2= Ba Bband there are no edges between V1\ (Ba Bb) and V2\ (Ba Bb). a u b u V2 V1 u v u T1 T2 u v

MORAL OF PREVIOUS SLIDE For a node v of T, G \ Bvsplits into components corresponding to the components of T \ v.

EXERCISE Prove that ISET can be solved in time O(4wpoly(n)) if a tree-decomposition (T,X) of width w is given. Hint: Root the decoposition tree T at a vertex r. Define Tvto be the subtree below v, and Vvto be u TvBu.

SOLUTION Define Best[v,S] (where S Bv) and G[S] is an iset, to be the size of the largest independent set X in G[Vv] such that X Bv = S. u Best[v,S] = |S| + Max Best[u,S ]-|S Bu| S Bu S S S (Bu \ Bv) S S is an iset. Children of v

STRUCTURAL PROPERTIES

ADDING / DELETING VERTICES Lemma: (a) Adding a vertex v to G increases tw(G) by at most 1. (b) Deleting a vertex v from G can not increase tw(G). Proof (a): Add v to all bags. Proof (b): Delete v from all bags it appears in. Corollary: (a) Adding an edge e to G increases tw(G) by at most 1. (b) Deleting an edge e from G can not increase tw(G).

EXERCISE Show that treewidth of graph below is 2. u v3 v1 v2 vn-2 vn-1 vn Proof: G \ u is a tree, hence of treewidth 1. Removing u decreased treewidth by at most 1.

CONTRACTING AND SUBDIVIDING EDGES Contracting an edge uv in G can not increase tw(G). Proof: Replace all occurences of u and v by the new vertex uv . Since some bag contained u and v, all is well. Subdividing an edge uv can not increase tw(G). Proof: Some bag contains uv. Add a new bag to it.

TREEWIDTH OF CLIQUES Lemma: In a tree-decomposition of a clique C, all of C must appear in some bag. Proof: (Board for figure) Suppose not. Root the decomposition at a node a that maximizes |Ba C| (of course, |Ba C| < |C|). Let u C and u Ba. Let b be the topmost bag where u is. Some v Ba C is not in Bb C. Now uv can t be in any bag!

EXERCISE Prove that a graph G has treewidth 1 if and only if it is a forest (contains no cycles) Soln: Trees have treewidth 1 so forests do to. If G contains a cycle Cnthen tw(G) tw(Cn) because deleting vertices does not increase treewidth. tw(Cn) tw(C3) because contracting edges does not increase tw. tw(C3)=2.

BALANCED SEPARATORS Lemma: Let G be a graph of treewidth t, and X V. There exists a set S of size at most t+1 such that for every connected component C of G\S, |C X| |X|/2. (*) Proof: Root the tree at a node set p initially to be the root. While there is a child q of p such that |Vq X| > |X|/2, set p=q.

BALANCED SEPARATORD CONTD When the algorithm terminates, the subtrees of all children satisfy |C X| |X|/2. If p has a parent then |Vp X| > |X/2| (since the parent wasn t chosen) so the component C = G \ Tv satisfies |C X| |X/2|. |X|/2 p > |X|/2 |X|/2

BALANCED SEPARATORS 2: EXERCISE Lemma: For a graph G=(V,E) of treewidth t and a vertex set X, there is a partition of V into L S R such that: |S| t+1 There are no edges from L to R max{|L X|, |R X|} < 3|X|/4 Hint: Use previous Lemma + bin packing arguments.

SOLN. Find a set S of size t+1 such that all components C of G \ S satisfy |C X| |X|/2. Let C1and C2 be the components with largest intersection with X. Put C1into L, C2into R, and place the remaining componetns into L or R if they fit. don t fit then the smallest of them fits into the smallest of L and R. C fits into L if |(L C) X| |X|/2 If two components Caand Cb At most one component C, does not fit. wlog: so: |L X| |X-C|/2 |(L C) X| |X+C|/2 2|X|/3

ISET IN POLYNOMIAL SPACE Theorem: Independent set in graphs of treewidth t can be solved in time nO(t)and using polynomial space. Proof: Find partition of G into L, R and S as described, using X=V. Guess the intersection of solution with S. Solve for L and R recursively. T(n) 2t 2T(2n/3) 2t log3/2 n nO(t)

WHAT ABOUT ISET IN F(TW)NO(1)TIME AND POLYNOMIAL SPACE? Theorem: Independent Set in graphs of treewidth t can be solved in time 2O(t2)nO(1)and using polynomial space. Proof: If n 2tthen the 4tnO(1), 2tnO(1)space DP algorithm runs in polynomial space. If n 2tthen nO(t) (2t)O(t) 2O(t2)nO(1).

COMPUTING TREEWIDTH Theorem: [Bodlaender, early 90 s]: The treewidth of G can be computed in time 2O(t3)n.

WHAT TO OPTIMIZE? For algorithms on graphs on bounded treewidth one can try to optimize the dependence on t, or the dependence on n. For the dependence on n, Courcelle s theorem gives very strong results.

(C)MSOL Quantifiers: and for variables for vertex sets and edge sets, vertices and edges. Operators: = and Operators: inc(v,e) and adj(u,v) Logical operators: , and (C): Size modulo fixed integers operator: eqmodp,q(S) EXAMPLE: p(G,S) = S is an independent set of G : p(G,S) = u, v S, adj(u,v)

CMSOL OPTIMIZATION PROBLEMS FOR COLORED GRAPHS -Optimization Input: G, C1, ... Cx Max / Min |S| So that (G, C1, Cx, S) holds. CMSOL definable proposition

MODEL CHECKING CMSOL PROPERTIES -Model-Checking: IN: G, C1, ... Cx Q: Does (G, C1, ... Cx) hold? The properties G has an independent set of size 10 and G has an independent set of size 100 need different formulas!

COURCELLES THEOREM(S) V1.0: For every CMSOL property and integer t, there is a linear time algorithm for -Model-Checking on graphs of treewidth t. V1.1: For every CMSOL property and integer t, there is a linear time algorithm for -Optimization on graphs of treewidth t. Often accredited to Courcelle, actually proved by Arnborg, Lagergren and Seese.

OPTIMIZING F(TW) Until recently, fairly naive algorithms were the best ones known for most problems, and we did not know why. In 2008, the list to beat was: 2twn for ISET 4twn for DOMSET qtwn for q-Coloring tw!n for Hamiltonian Cycle

OPTIMIZING F(TW) CURRENT PICTURE 2twn for ISET 3twn for DOMSET [new upper bound, ESA09] qtwn for q-Coloring 4twn for Hamiltonian Cycle [new upper bound, Arxiv 11] Matching Lower bounds under SETH, SODA 11

Thank you!