Subexponential time algorithms for finding small tree and path decompositions Hans L. Bodlaender∗ Jesper Nederlof† 6 May 5, 2016 1 0 2 y a M Abstract 4 The Minimum Size Tree Decomposition (MSTD) and Minimum Size Path Decomposition (MSPD) problems ask for a given n-vertex ] S graph G and integer k, what is the minimum number of bags of a D tree decomposition (respectively, path decomposition) of G of width . at most k. The problems are known to be NP-complete for each fixed s c k ≥ 4. We present algorithms that solve both problems for fixed k [ in 2O(n/logn) time and show that they cannot be solved in 2o(n/logn) 2 time, assuming the Exponential Time Hypothesis. v 5 1 1 Introduction 4 2 0 . In this paper, we consider two bicriteria problems concerning path and tree 1 decompositions, namely, for an integer k, find for a given graph G a path or 0 6 tree decomposition with the minimum number of bags. For both problems, 1 we give exact algorithms that use 2O(n/logn) time and give a matching lower : v bound, assuming the Exponential Time Hypothesis. The results have a num- i X ber of interesting features. To our knowledge, these are the first problems r for which a matching upper and lower bound (assuming the ETH) with the a running time 2Θ(n/logn) is known. The algorithmic technique is to improve the analysis of a simple idea by van Bodlaender and van Rooij [5]: a branch- ing algorithm with memorization would use 2O(n) time, but combining this ∗Utrecht University and Technical University Eindhoven, the Netherlands. Email: [email protected]. PartiallysupportedbytheNetworksproject,fundedbytheDutch Ministry of Education, Culture and Science through NWO. †Technical University Eindhoven. Email:[email protected]. Supported by NWO Veni project 639.021.438 1 with the easy observation that isomorphic subgraphs give rise to equivalent subproblems, by adding isomorphism tests on the right locations in the algo- rithm, the savings in time is achieved. Our lower bound proofs use a series of reductions; the intermediate problems in the reductions seem quite useful for showing hardness for other problems. Bicriteria problems are in many cases more difficult than problems with one criterion that must be optimized. For the problems that we consider in thispaper, thisisnotdifferent: ifwejustaskforatreeorpathdecomposition withtheminimumnumberofbags, thentheproblemistrivialastherealways is a tree or path decomposition with one bag. Also, it is well known that the problem to decide if the treewidth or pathwidth of a graph is bounded by a given number k is fixed parameter tractable. However, recent results show that if we ask to minimize the number of bags of the tree or path decompo- sition of width at most k, then the problem becomes para-NP-complete (i.e., NP-complete for some fixed k) as shown in [6, 9]. The problem to find path decompositions with a bound on the width and a minimum number of bags was first studied by Dereniowski et al. [6]. Formulatedasadecisionproblem, theproblemMSPD istodetermine, given k a graph G = (V,E) and integer s, whether G has a path decomposition of width at most k and with at most s bags. Dereniowski et al. [6] mention a number of applications of this problem and study the complexity of the problem for small values of k. They show that for k ≥ 4, the problem is NP- complete, and for k ≥ 5, the problem is NP-complete for connected graphs. They also give polynomial time algorithms for the MSPD problem for k ≤ 3 k and discuss a number of applications of the problem, including the Partner Units problem, problems in scheduling, and in graph searching. Li et al. [9] introduced the MSTD problem: given a graph G and integer k (cid:96), does G have a tree decomposition of width at most k and with at most (cid:96) bags. They show the problem to be NP-complete for k ≥ 4 and for k ≥ 5 for connected graphs, with a proof similar to that of Dereniowski et al. [6] for the pathwidth case, and show that the problem can be solved in polynomial time when k ≤ 2. In this paper, we look at exact algorithms for the MSPD and MSTD k k problems. Interestingly,theseproblems(forfixedvaluesofk)allowforsubex- ponential time algorithms. The running time of our algorithm is of a form that is not frequently seen in the field: for each fixed k, we give algorithms for MSPD and MSTD that use 2O(n/logn) time. Moreover, we show that these results are tight in the sense that there are no 2o(n/logn) time algorithms for MSPD and MSTD for some large enough k, assuming the Exponential k k Time Hypothesis. Our algorithmic technique is a variation and extension of the technique 2 used by Bodlaender and van Rooij [5] for subexponential time algorithms for Intervalizing k-Colored Graphs. That algorithm has the same running time as ours; we conjecture a matching lower bound (assuming the ETH) for Intervalizing 6-Colored Graphs. 2 Preliminaries Notation In this paper, we interpret vectors as strings and vice versa whenever convenient, and for clarity use boldface notation for both. When a,b ∈ Σ(cid:96) are strings, we denote a||b for the string obtained by concatenating a and b. We let s(cid:96) denote the string repeating symbol s (cid:96) times. Also, we denote a (cid:22) b to denote that a ≤ b for every 1 ≤ i ≤ n and use 1 to denote i i the vector with each entry equal to 1 (the dimension of 1 will always be clear from the context). We also add vectors, referring to component-wise addition. Tree and Path decompositions. Unless stated otherwise, the graphs we consider in this paper are simple and undirected. We let n = |V| denote the number of vertices of the graph G = (V,E). A path decomposition of a graph G = (V,E) is a sequence of subsets of V: (X ,...,X ) such that 1 s (cid:83) • X = V, 1≤i≤s i • For all edges {v,w} ∈ E: there is an i, 1 ≤ i ≤ s, with v,w ∈ X , i • For all vertices v ∈ V: there are i , j , such that i ∈ [i ,j ] ⇔ v ∈ X . v v v v i Thewidthofapathdecomposition(X ,...,X )ismax |X |−1; itssizeis 1 s 1≤i≤s i s. ThepathwidthofagraphGistheminimumwidthofapathdecomposition ofG. We will refer toX as thelast bag of (X ,...,X ). Atree decomposition s 1 s of a graph G = (V,E) is a pair ({X | i ∈ I},T = (I,F)) with {X | i ∈ I} i i a family of subsets of V, and T a rooted tree, such that (cid:83) • X = V. i∈I i • For all edges {v,w} ∈ E: there is an i ∈ I with v,w ∈ X . i • For all vertices v ∈ V: the set I = {i ∈ I | v ∈ X } induces a subtree v i of T (i.e., is connected.) Thewidthofatreedecomposition({X |i ∈ I},T = (I,F))ismax |X |−1; i i∈I i its size is |I|. The treewidth of a graph G is the minimum width of a tree decomposition of G. In the definition above, we assume that T is rooted: 3 this does not change the minimum width or size, but makes proofs slightly easier. Elements of I and numbers in {1,2,...,s} and their corresponding sets X are called bags. i A tree decomposition ({X | i ∈ I},T = (I,F)) of a graph G = (V,E) is i nice, if for each i ∈ I, one of the following cases holds: • i has two children j and j with X = X = X (join node.) 1 2 i j1 j2 • i has one child j and there is a v ∈ V with X = X ∪{v} (introduce i j node.) • i has one child j and there is a v ∈ V with X = X \{v} (forget node.) i j • i has no children (leaf node). The following result is folklore. Lemma 1 ([8], Lemma 13.1.2) Let G = (V,E) have treewidth at most k. Then G has a nice tree decomposition of width at most k with at most 4n bags. Usually, nice tree and path decompositions have more than the minimum number of bags. The notions are still very useful for our analysis; in partic- ular, they help to count the number of non-isomorphic graphs of treewidth or pathwidth at most k, as we see shortly. We will use the following fact. A weakly binary tree is a rooted tree where each vertex has at most two children. Lemma 2 (Otter 1948 [11]) Thenumberofnon-isomorphicweaklybinary trees with n vertices is bounded by O(2.484n). Lemma 3 The number of non-isomorphic graphs with n vertices of treewidth at most k is 2O(kn). Proof. By Lemma 1, we have a nice tree decomposition ({X },T) of width i at most k and size at most 4n. It is well known that we can color the vertices of a graph with treewidth k by k+1 colors, such that all vertices in a bag have a different color. (The inductive proof is as follows: this clearly holds if we have a tree decompo- sition with one bag. Otherwise, take a leaf bag i with neighboring bag j. Inductively, color all vertices except the vertices in X −X ; the vertices in i j X − X do not belong to any bag other than X ; color these with colors, i j i different from all other vertices in X .) i 4 To bound the number of non-isomorphic graphs of treewidth k with n vertices, weassociatewitheachsuchgraphanicetreedecompositionofwidth k with the vertices colored as above, and multiply a bound on the number of underlying binary trees by a bound on the number of non-isomorphic cases for the bags. The number of underlying binary trees is bounded by 2O(n), by Otter’s result (Lemma 2). To obtain our bound, we note that for each edge e = {v,w} ∈ E, there is exactly one node i in the tree decomposition, such that {v,w} ∈ X and i e ie e is the root of the tree decomposition or the parent of i is a forget node that e forgets v or forgets w. This enables us to count the number of possibilities for edges in the graph when looking at forget nodes, with the root as a simple special case. Let us now count the number of possibilities of each non-root bag of T, distinguishing on its type: • Join node. There is no additional information: 1 possibility. • Introduce. At introduce nodes, we only determine what color the newly introduced vertex has. This gives at most k +1 possibilities. • Forget. At a forget node, we have at most (k+1)·2k possibilities: we identify the forgotten vertex by it color (k +1 possibilities), and each of the other at most k vertices in the bag below the forget node can have an edge to the forgotten vertex or not (2k possibilities). • Leaf. For each of the k+1 colors, there can be a vertex with this color in the leaf bag or not: 2k+1 possibilities. We thus have 2O(k) possibilities per non-root bag; we have O(n) bags, which gives an upper bound of 2O(kn). We still need to count the number of different possibilities concerning the edges between vertices in the root bag: for each pair of vertices in the root bag, there can be an edge or not — this gives an extra multiplicative factor of 2O(k2), but as k < n, the number of combinations stays 2O(kn). (cid:3) 3 Path and tree decompositions with few bags 3.1 Finding path decompositions with memorization and isomorphism tests In this section, we describe our algorithm for the MSPD problem. Through- out the section, we assume that k is a fixed positive integer and that G has 5 treewidth at most k (note that we can determine this in linear time for fixed k (cf. [2]) and return NO if the treewidth is higher than k). Our branching algorithm is parameterized by ‘a good pair’, formalized as follows: Definition 1 A good pair is a pair of vertex sets (X,W), such that • |X| ≤ k +1, • X ∩W = ∅, and • for all v ∈ W, N(v) ⊆ W ∪ X. Equivalently, W is the union of the vertex sets of zero or more connected components of G[V \X]. For a good pair (X,W), let mstd (X,W) (mspd (X,W)) be the minimum k k s such that there is a tree (path) decomposition of G[X∪W] of width at most k, where X is the root bag (last bag) of the tree (path) decomposition. Arecursiveformulationforpathdecompositions. Thefollowinglemma gives a recursive formulation for mspd . The formulation is the starting point k for our algorithm, but we will in addition exploit graph isomorphisms, see below. Lemma 4 If |X| ≤ k +1, then mspd (X,∅) = 1. Otherwise, let (X,W) be k a good pair, and W (cid:54)= ∅. Then mspd (X,W) = min 1+mspd (Y,W \Y). (1) k k Y⊆X∪W X(cid:54)=Y W∩N(X\Y)=∅ Proof. The first part with |X| ≤ k + 1 is trivial: take the only path decomposition with one bag X. Otherwise, suppose Y fulfills W ∩N(X\Y) = ∅. Let PD = (X ,...,X ) 1 s be a path decomposition of width at most k of G[Y ∪W] with X = Y. Now s we verify that (X ,...,X ,X) is a path decomposition of width at most k 1 s of G[X ∪ W]. Since there can be no edges between X \ Y and W, all the edges incident to X \ Y are covered in the bag X and all other edges are covered in PD since it is a path decomposition of G[Y ∪W]. Also, a vertex v ∈ X \ Y cannot occur in PD so the bags containing a particular vertex will still induce a connected part in the path decomposition. Conversely, suppose(X ,...,X ,X)isaminimalsizepathdecomposition 1 s of width at most k of G[X ∪ W]. Note that X = X contradicts this path s decomposition being of minimal size, so we may assume X (cid:54)= X . Vertices in s (cid:83) X\X donot belongto X , by thedefinition ofpathdecomposition, s 1≤i≤s−1 i 6 so we must have that W ∩ N(X \ X ) = ∅ since otherwise not all edges s incident to X are covered in the path decomposition. Hence, X fulfills all s the conditions of the minimization in the recurrence. We have that (X ,...,X ) is a path decomposition of G[X ∪(W \X )], 1 s s s which has at least mspd (X ,W \ X ) bags and hence taking Y = X k s−1 s−1 s shows that mspd (X,W) ≤ s+1. (cid:3) k Isomorphism. The following notion will be needed for presenting the used recurrence for tree decompositions and essential for quickly evaluating (1). Intuitively, it indicates G[X ∪ W] being isomorphic to G[Y ∪ Z] with an isomorphism that maps X to Y. More formally, Definition 2 Good pairs (X,W) and (X,Z) are isomorphic if there is a bijection f : X ∪W ↔ X ∪Z, such that 1. For all v,w ∈ X ∪W: {v,w} ∈ E ⇔ {f(v),f(w)} ∈ E, and 2. f(v) = v for all v ∈ X. We will use the following obvious fact: Observation 5 Suppose good pair (X,W) is isomorphic to good pair (X,Z). Then mspd (X,W) = mspd (X,Z) and mstd (X,W) = mstd (X,Z) k k k k In our algorithm we use a result by Loksthanov et al. [10] which gives an algorithm that for fixed k maps each graph G of treewidth at most k to a string can(G) (called its canonical form), such that two graphs G and H are isomorphic if and only if can(G) = can(H). The result also holds for graphs where vertices (or edges) are labeled with labels from a finite set and the isomorphism should map vertices to vertices of the same label. We can use this result to make canonical forms for good pairs: Observation 6 An isomorphism class of the good pairs (X,W) can be de- scribed by the triple can(X,W) := (X,can(G[X∪W],f) where f is a bijection from X to |X|. Here, f : X ↔ X can be (for example) be defined as the restriction of π onto X of the lexicographically smallest (with respect to some arbitrary ordering) isomorphism π of G[X ∪W]. 7 Algorithm PD (X,W) k 1: if |X| ≤ k +1 and W = ∅ then return 1 2: if D(can(X,W)) is stored then return D(can(X,W)) 3: m ← ∞. 4: for all Y ⊆ X ∪W such that Y (cid:54)= X,N(X \Y) ⊆ X,|Y| ≤ k do 5: m ← min{m,1+PD (Y,W \Y)}. k 6: Store D(can(X,W)) ← m. 7: return m. Algorithm 1: Finding a small path decompositions of width at most k. A recursive algorithm with memorization. Wenowgivearecursiveal- gorithmPD tocomputeforagivengoodpair(X,W)thevaluemspd (X,W). k k Thealgorithmusesmemorization. InadatastructureD, westorevaluesthat we have computed. We can use e.g., a balanced tree or a hash table for D, that is initially assumed empty. Confer Algorithm 1. The correctness of this method follows directly from Lemma 4 and Ob- servation 5. The main difference with a traditional evaluation (with mem- orization) of the recursive formulation of mspd is that we store and lookup values under their canonical form under isomorphism — this simple change is essential for obtaining a subexponential running time. The fact that we workwithgraphsofboundedtreewidthandforthese, Graph Isomorphism is polynomial [1, 10] makes that we can perform this step sufficiently fast. Equipped with the PD algorithm, we solve the MSPD problem as follows: k for all X ⊆ V with |X| ≤ k+1, run PD (X,V \X); report the smallest value k over all choices of X. 3.2 The number of good pairs We now will analyze the number of good pairs. This is the main ingredient of the analysis of the running time of the algorithm given above. Theorem 7 Let k be a constant. Let G be a graph with n vertices and treewidth at most k. Then G has 2O(n/logn) non-isomorphic good pairs. Proof. Let us define a basic good pair as a good pair (X,W) where G[W] is connected. The isomorphism classes (with respect to the notion of isomorphism from Definition 2) of good pairs can be described as follows: let X be a set of size at most k. Let C ,...,C be a partition of the connected 1 (cid:96) components of G[V \X] into basic good pair isomorphism classes, e.g.: we have for two connected components C ,C that C ,C ∈ C for some i if and a b a b i 8 only if there exists a bijection X ∪C ↔ X ∪C such that for all v ∈ X we a a have f(v) = v and for all v,w ∈ X ∪C : {v,w} ∈ E ⇔ {f(v),f(w)} ∈ E. a We order the isomorphism classes arbitrarily (e.g., in some lexicographical order). Then an isomorphism class of all good pairs can be described by a triple (X,s = {c ,...,c },f) where c is the number of connected components of 1 s i G[V \ X] in basic pair isomorphism class C . Then we have the following i bound: Claim 1 There is a c > 0, such that for a constant k, the number of iso- morphism classes of basic good pairs (X,W) with |W|+|X| ≤ 1 logn is at √ ck most n for sufficiently large n. Proof. For each c > 0, by Lemma 3, the number of graph isomorphism classes of G[X ∪W] with |W|+|X| ≤ 1 logn is at most 2O(k logn) since we ck ck assumed the treewidth to be at most k (as stated in the beginning of this section). The isomorphism class of a basic good pair is described by the set X, the permutation of X and the graph isomorphism class of G[W ∪ X], thus we have that the number of basic good pair isomorphism classes is at most O(kn) O(kn) √ k!2 ck logn ≤ 2O(klog(k))+ ck logn which is n for large enough n, and proper choice of c depending on the constants hidden in the O(·) notation. (cid:3) Say an isomorphism class C is small if (X,W) ∈ C implies |X|+|W| ≤ i i 1 logn (with c as given by Claim 1), and it is large otherwise. Assume ck √ C ,...,C are small. By Claim 1, z is at most n. Thus, since we know 1 z c ≤ n, the number of possibilities of s on the small isomorphism classes is at i √ most nO( n). For the remaining (cid:96)−z isomorphism classes of large connected components, wehavethat(cid:80)(cid:96) c ≤ ckn/logn = O(n/logn). Thus, there j=z+1 i are only 2O(n/logn) subsets of the large connected components that can be in W. Combining both bounds gives the upper bound of 2O(n/logn) for the number of non-isomorphic good pairs, as desired. (cid:3) 3.3 Analysis of the algorithm In this section, we analyze the running time of Algorithm 1. First, we note that per recursive call we have O(nk+1) calls of the form PD (X,V \ X). k ObservethateachcalltoPD iswithagoodpairasparameter, andthesegood k pairs on Line 4 can be enumerated with linear delay. Thus, by Theorem 7, there are 2O(n/logn) calls to PD that make recursive calls to PD . Within each k k 9 single call, we have O(nk+1) choices for a set Y; computing s = can(X,W) can be done in O(n5) time (confer [10]), and thus, the overhead of a single recursive call is bounded by O(nmax{k+1,5}). Putting all ingredients together shows that the algorithm uses 2O(n/logn) time. Theorem 8 For fixed k, the MSPD problem can be solved in 2O(n/logn) time. 3.4 Extension to finding tree decompositions Now we discuss how to extend the algorithm for solving the MSTD prob- lem. Note that, like usual, dealing with tree decompositions instead of path decompositions amounts to dealing with join bags. We have the following analogue of Lemma 4. Lemma 9 If |X| ≤ k +1, then mstd (X,∅) = 1. Otherwise, let (X,W) be k a good pair, and W (cid:54)= ∅. Then mstd (X,W) = min{extend,branch} where k extend = min 1+mstd (Y,W \Y). k Y⊆X∪W X(cid:54)=Y W∩N(X\Y)=∅ (2) branch = min mstd(X,W )+mstd(X,W \W )−1. 1 1 W1⊆W N(W1)⊆W1∪X Proof. The cases extend and branch refer to whether the root bag r with vertex set X has exactly one child, or at least two children. If r has one child, then the same arguments that show (1) can be used to show correctness of the extend case. If r has two or more children, then we can guess the set of vertices W ⊆ W that appear in bags in the subtree rooted by the first 1 child of r. We must have that W is a union of connected components of 1 G[W] by the definition of tree decompositions. Thus, the tree decomposition can be obtained by taking a tree decomposition of G[X ∪ W ] and a tree 1 decomposition of G[X ∪ (W \ W )], both with X as the vertex set of the 1 root bag, and then taking the union, identifying the two root bags. The number of bags thus equals the minimum number of bags for the first tree decomposition (which equals mstd(X,W )), plus the minimum number of 1 bagsforthesecond(equallymstd(X,W\W )), subtractingoneaswecounted 1 the bag with vertex set X twice. (cid:3) Given Algorithm 1 and (2), the algorithm for computing mstd suggests itself since it is easy to see that again we only need to evaluate mstd (X,W) k for good pairs (X,W). This is indeed our approach but there is one small complication, since we cannot compute branch in a naive way because the number of connected components of G[W] could be Ω(n). We deal with this 10