{'fraction_non_alphanumeric': 0.050756994348705786, 'fraction_numerical': 0.017302727970417917, 'mean_word_length': 3.6757462077964442, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
An Exponential Time 2-Approximation Algorithm for Bandwidth

The bandwidth of a graph G on n vertices is the minimum b such that the vertices of G can be labeled from 1 to n such that the labels of every pair of adjacent vertices differ by at most b. In this paper, we present a 2-approximation algorithm for the bandwidth problem that takes worst-case O(1.9797^n) time and uses polynomial space. This improves both the previous best 2- and 3-approximation algorithms of Cygan et al. which have an O(3^n) and O(2^n) worst-case time bounds, respectively. Our algorithm is based on constructing bucket decompositions of the input graph. A bucket decomposition partitions the vertex set of a graph into ordered sets (called buckets) of (almost) equal sizes such that all edges are either incident to vertices in the same bucket or to vertices in two consecutive buckets. The idea is to find the smallest bucket size for which there exists a bucket decomposition. The algorithm uses a simple divide-and-conquer strategy along with dynamic programming to achieve this improved time bound.


Introduction
Let G = (V, E) be a graph on n vertices and b be an integer. The Bandwidth problem asks whether the vertices of G can be labeled from 1 to n such that the labels of every pair of adjacent vertices differ by at most b. The Bandwidth problem is a special case of the Subgraph Isomorphism problem, as it can be formulated as follows: Is G isomorphic to a subgraph of P b n ? Here, P b n denotes the graph obtained from P n (the path on n vertices) by adding an edge between every pair of vertices at distance at most b in P n .
The Bandwidth problem is NP-hard [18], even for trees of maximum degree at most three [13] and caterpillars with hair length at most three [16]. Even worse, approximating the bandwidth within a constant factor is NP-hard, even for caterpillars of degree three [20]. Further, it is known that the problem is hard for every fixed level of the W-hierarchy [3] and unlikely to be solvable in f (b)n o(b) time [4].
Faced with this immense intractability, several approaches have been proposed in the literature for the Bandwidth problem. The first (polynomial time) approximation algorithm with a polylogarithmic approximation factor was provided by Feige [10]. Later, Dunagan and Vempala gave an O(log 3 n √ log log n)approximation algorithm. The current best approximation algorithm achieves an O(log 3 n(log log n) 1/4 )approximation factor [15]. For large b, the best approximation algorithm is the probabilistic algorithm of Blum et al. [2] which has an O( n/b log n)-approximation factor. Super-polynomial time approximation algorithms for the Bandwidth problem have also been widely investigated [5,8,9,12]. Feige and Talwar [12], and Cygan and Pilipczuk [8] provided subexponential time approximation schemes for approximating the bandwidth of graphs with small treewidth. For general graphs, a 2-approximation algorithm with a running time of O * (3 n ) 1 is easily obtained by combining ideas from [11] and [12] (as noted in [5]). Further, Cygan et al. [5] provide a 3-approximation algorithm with a running time of O * (2 n ), which they generalize to a (4r − 1)-approximation algorithm (for any positive integer r) with a running time of O * (2 n/r ).
Concerning exact exponential time algorithms, the fastest polynomial space algorithm is still the elegant O * (10 n ) time algorithm of Feige [11]. When allowing exponential space, this bound is improved in a sequence of algorithms by Cygan and Pilipczuk; their O * (5 n ) time algorithm uses O * (2 n ) space [6], their O(4.83 n ) time algorithm uses O * (4 n ) space [7], and their O(4.473 n ) time algorithm uses O(4.473 n ) space [8]. The most practical of these algorithms is probably the O * (5 n ) time algorithm as the space requirements of the other ones seems forbiddingly large for practical applications. The Bandwidth problem can also be solved exactly in O(n b ) time using dynamic programming [19,17].
Another recent approach to cope with the intractability of Bandwidth is through the concept of hybrid algorithms, introduced by Vassilevska et al. [21]. They gave an algorithm that after a polynomial time test, either computes the minimum bandwidth of a graph in O * (4 n+o(n) ) time, or provides a polylogarithmic approximation ratio in polynomial time. This result was recently improved by Amini et al. [1] who give an algorithm which, after a polynomial time test, either computes the minimum bandwidth of a graph in O * (4 n ) time, or provides an O(log 3/2 n)-approximation in polynomial time.
Our Results. Our main result is a 2-approximation algorithm for the Bandwidth problem that takes worstcase O(1.9797 n ) time (Theorem 3.8). This improves the O * (3 n ) time bound achieved by Cygan et al. [5] for the same approximation ratio. Also, the previous best 3-approximation algorithm of Cygan and Pilipczuk [8] has an O * (2 n ) time bound. Therefore, our 2-approximation algorithm is also faster than the previous best 3-approximation algorithm.
Our algorithm is based on constructing bucket decompositions of the input graph. A bucket decomposition partitions the vertex set of a graph into ordered sets (called buckets) of (almost) equal sizes such that all edges are either incident on vertices in the same bucket or on vertices in two consecutive buckets. The idea is to find the smallest bucket size for which there exists a bucket decomposition. This gives a 2-approximation for the Bandwidth problem (Lemmas 3.2 and 3.1). The algorithm uses a simple divide-and-conquer strategy along with dynamic programming to achieve this improved time bound.

Preliminaries
Let G = (V, E) be a graph on n vertices. A linear arrangement of G is a bijective function L : V → [n] = {1, . . . , n}, that is a numbering of its vertices from 1 to n. The stretch of an edge (u, v) is the absolute difference between the numbers assigned to its endpoints |L(u) − L(v)|. The bandwidth of a linear arrangement is the maximum stretch over all the edges of G and the bandwidth of a graph is the minimum bandwidth over all linear arrangements of G.
A bucket arrangement of G is a placement of its vertices into buckets such that for each edge, its endpoints are either in the same bucket or in two consecutive buckets. The buckets are numbered from left to right. A capacity vector C is a vector of positive integers. The length of a capacity vector C = . Given a capacity vector C of size n, a C-bucket arrangement of G is a bucket arrangement in which exactly C[i] vertices are placed in bucket i, for each i. For integers n and ℓ with ℓ < n/2, an (n, ℓ)-capacity vector is a capacity vector (a, ℓ, ℓ, . . . , ℓ, of size n such that a, b ≤ ℓ. We say that an (n, ℓ)-capacity vector is left-packed if a = ℓ. We say that an (n, ℓ)-capacity vector is balanced if |a − b| = 1. Let X ⊆ V be a subset of the vertices of G. We denote by G[X] the subgraph of G induced on X, and by G \ X the subgraph of G induced on V \ X. The open neighborhood of a vertex v is denoted by N G (v) and the open neighborhood of X is N G (X) := ( v∈X N G (v)) \ X.

Exponential Time Algorithms for Approximating Bandwidth
We first establish two simple lemmas that show that constructing a bucket arrangement can approximate the bandwidth of a graph. Lemma 3.1. Let G be a graph on n vertices, and let C be an (n, ℓ)-capacity vector. If there exists a C-bucket arrangement for G then the bandwidth of G is at most 2ℓ − 1.
Proof. Given a C-bucket arrangement for G, create a linear arrangement respecting the bucket arrangement (if u appears in a smaller numbered bucket than v, then L(u) < L(v)), where vertices in the same bucket are numbered in an arbitrary order. As the capacity of each bucket is at most ℓ and each edge spans at most two consecutive buckets, the maximum edge stretch in the constructed linear arrangement is at most 2ℓ − 1.

Lemma 3.2.
Let G be a graph on n vertices, and let C be an (n, ℓ)-capacity vector. If there exists no C-bucket arrangement for G then the bandwidth of G is at least ℓ + 1.
Proof. Suppose there exists a linear arrangement L of G of bandwidth at most ℓ. Construct a bucket arrangement placing the first C [1] vertices of L into the first bucket, the next C [2] vertices of L into the second bucket, and so on. In the resulting bucket arrangement, no edge spans more than two consecutive buckets. Therefore, a C-bucket arrangement exists for G, a contradiction.
Note that both the Lemmas 3.2 and 3.1 are true even if we restrict the vector to be left-packed or balanced. We will use the previous fastest 2-approximation algorithm of Cygan et al. [5] as a subroutine. For completeness, we describe this simple algorithm here.

Proposition 3.3 ([5]
). There is a polynomial space 2-approximation algorithm for the Bandwidth problem that takes worst-case O * (3 n ) time on connected graphs with n vertices.
Proof. Let G be a connected graph on n vertices. For ℓ increasing from 1 to ⌈n/2⌉, the algorithm does the following. Let C be an (n, ℓ)-capacity vector. The algorithm goes over all the k = n ℓ choices for assigning the first vertex to some bucket. The algorithm then chooses an unassigned vertex u which has at least one neighbor that has already been assigned to some bucket. Assume that a neighbor of u is assigned to the bucket i. Now there are at most three choices of buckets (i − 1, i, and i + 1) for assigning vertex u. Some of these choices may be invalid either because of the capacity constraints of the bucket or because of the previous assignments of (other) neighbors of u. If the choice is valid, the algorithm recurses by assigning u to that bucket. Let ℓ ′ be the smallest integer for which the algorithm succeeds, in some branch, to place all vertices of G into buckets in this way. Then, by Lemma 3.1, G has bandwidth at most 2ℓ ′ − 1 and by Lemma 3.2, G has bandwidth at least ℓ ′ . Thus, the algorithm outputs 2ℓ ′ − 1, which is a 2-approximation for the bandwidth of G. As the algorithm branches into at most 3 cases for each of the n vertices (except the first one), and all other computations only contribute polynomially to the running time of the algorithm, this algorithm runs in worst-case O * (3 n ) time using only polynomial space.
We now show another simple algorithm based on a divide-and-conquer strategy that given an (n, ℓ)capacity vector C, decides whether a C-bucket arrangement exists for a connected graph G. Proposition 3.4. Let G be a connected graph on n vertices and C be an (n, ℓ)-capacity vector with ℓ < n/2. There exists an algorithm that can decide if G has a C-bucket arrangement in O * n ℓ · n/2 ℓ · 2 4ℓ · 3 n/4 time.
Proof. Let k = n ℓ be the number of buckets in the C-bucket arrangement. Number the buckets from 1 to k from left to right according to the bucket arrangement. Select a bucket index i such that the sum of the capacities of the buckets numbered strictly smaller than i and the one for the buckets numbered strictly larger than i are both at most n/2.
The algorithm goes over all possible n ℓ choices of filling bucket i with ℓ vertices. Let X be a set of ℓ vertices assigned to the bucket i. Given a connected component of G \ X, note that all the vertices of this connected component must be placed either only in buckets 1 to i − 1 or buckets i + 1 to k. Note that each connected component of G \ X contains at least one vertex that is adjacent to a vertex in X (as G is connected). Therefore, for each connected component of G \ X, at least one vertex is placed into the bucket i − 1 or i + 1. As the capacity of each bucket is at most ℓ, G \ X has at most 2ℓ connected components, otherwise there is no C-bucket arrangement where X is assigned to the bucket i. Thus, there are at most 2 2ℓ choices for assigning connected components of G \ X to the buckets 1 to i − 1 and i + 1 to k. Some of these assignments might be invalid as they might violate the capacity constraints of the buckets. We discard these invalid assignments.
For each choice of X and each valid assignment of the connected components of G \ X to the left or right of bucket i, we have now obtained two independent subproblems: one subproblem for the buckets {1, . . . , i − 1} and one subproblem for the buckets {i + 1, . . . , k}. These subproblems have sizes at most n/2. Consider the subproblem for the buckets {1, . . . , i − 1} (the other one is symmetric) and let Y be the set of vertices associated to these buckets. Let Z ⊆ Y be the set of vertices in Y that have at least one neighbor in X. Now, add edges to the subgraph G[Y ] such that Z becomes a clique. This does not change the problem, as all the vertices in Z must be assigned to the bucket i − 1, and G[Y ] becomes connected. This subproblem can be solved recursively, ignoring those solutions where vertices in Z are not all assigned to the bucket i − 1.
The algorithm performs the above recursion until it reaches subproblems of size at most n/4, which corresponds to two levels in the corresponding search tree. On instances of size at most n/4, the algorithm invokes the algorithm of Proposition 3.3, which takes worst-case O * (3 n/4 ) time.
Let T (n) be the running time needed for the above procedure to check whether a graph with n vertices has a bucket arrangement for an (n, ℓ)-capacity vector. Then, This completes the proof of the proposition.
Combining Proposition 3.4 with Lemmas 3.1 and 3.2, we have the following corollary for 2-approximating the bandwidth of a graph.

Corollary 3.5.
There is an algorithm that, for a connected graph G on n vertices and an integer ℓ ≤ n can decide whether the bandwidth of G is at least ℓ + 1 or at most 2ℓ − 1 in O * n ℓ · n/2 ℓ · 2 4ℓ · 3 n/4 time.
Proof. If ℓ ≥ n/2, the bandwidth of G is at most 2ℓ − 1. Otherwise, use Proposition 3.4 with G and some (n, ℓ)-capacity vector C to decide if there exists a C-bucket arrangement for G. If so, then the bandwidth of G is at most 2ℓ − 1 by Lemma 3.1. If not, then the bandwidth of G is at least ℓ + 1 by Lemma 3.2.
The running time of the algorithm of Corollary 3.5 is interesting for small values of ℓ. For example if ℓ ≤ n/26, the running time is O(1.9737 n ). In the remainder of this section, we improve Proposition 3.4. We now concentrate on the cases where k = ⌈n/ℓ⌉ ≤ 26.
Let C be an (n, ℓ)-capacity vector. A partial C-bucket arrangement of an induced subgraph G ′ of G is a placement of vertices of G ′ into buckets such that: (a) each vertex in G ′ is assigned to a bucket or to a union of two consecutive buckets, (b) the endpoints of each edge in G ′ are either in the same bucket or in two consecutive buckets, and (c) at most C[i] vertices are placed in each bucket i. Let B be a partial C-bucket arrangement of an induced subgraph G ′ . We say that a bucket i is full in B if the number of vertices that have been assigned to it equals its capacity (= C[i]). We say that two consecutive buckets i and i + 1 are jointly full in B if a vertex subset Y of cardinality equal to the sum of the capacities of i and i + 1 have been assigned to these buckets (i.e., each vertex v ∈ Y is restricted to belong to the union of buckets i or i + 1, but which among these two buckets v belongs is not fixed). We say that a bucket is empty in B if no vertices have been assigned to it. If the bucket i is full in B, let X i denote the set of vertices assigned to it. If the buckets i and i + 1 are jointly full in B, let X i,i+1 denote the set of vertices assigned to the union of buckets i and i + 1. We use dynamic programming to start from a partial bucket arrangement satisfying the above conditions to construct a C-bucket arrangement. During its execution, the algorithm assigns vertices to the buckets which are empty in B. We only present an outline of the dynamic programming algorithm here. The dynamic programming algorithm constructs a table T [. . . ], which has the following indices.
• An index p, representing the subproblem on the first p connected components of G \ V ′ .
• For every empty bucket i in B such that both the buckets i − 1 and i + 1 are full, it has an index s i , representing the number of vertices assigned to the bucket i.
• For every two consecutive empty buckets i and i + 1 in B, it has indices t i,i+1 , x i , and x i+1 . The index t i,i+1 represents the total number of vertices assigned to the buckets i and i + 1. The index x i represents the number of vertices assigned to the buckets i and i + 1 that have at least one neighbor in the bucket i − 1. The index x i+1 represents the number of vertices assigned to the buckets i and i + 1 that have at least one neighbor in the bucket i + 2.
• For every two consecutive buckets i, i + 1 which are jointly full in B, it has indices f i and f i+1 representing the number of vertices assigned to these buckets that have at least one neighbor in the bucket i − 1 (f i ) or in the bucket i + 2 (f i+1 ).
If the vertices in V p have at least one neighbor in the jointly full buckets i − 2 and i − 1, and at least one neighbor in the jointly full buckets i + 1 and i + 2, but have no neighbors in any other buckets, and bucket i is empty in B, then The recursion for the other possibilities where V p has neighbors in two distinct buckets can now easily be deduced. We now consider the cases where V p has only neighbors in one bucket. Again, we only describe some key-cases, from which all other cases can easily be deduced.
If the vertices in V p have only neighbors in the full bucket i − 1, and the buckets i − 2 and i are both empty in B, but the buckets i − 3 and i + 1 are either full or non-existing, then If the vertices in V p have only neighbors in the full bucket i − 1, and the buckets i − 3, i − 2, i, and i + 1 are all empty in B, then If the vertices in V p have only neighbors in the jointly full buckets i and i + 1, and the buckets i − 1 and i + 2 are both empty in B, but the buckets i − 2 and i + 3 are either full in B or non-existing, then .
The final answer (true or false) produced by the algorithm is a disjunction over all table entries whose indices are as follows: p = r,

Remark:
The dynamic programming algorithm in Proposition 3.6 can easily be modified to construct a Cbucket arrangement (from any partial bucket arrangement B satisfying the stated conditions), if one exists.
If the number of buckets is a constant, the following proposition will be crucial in speeding up the procedure for assigning connected components to the right or the left of a bucket filled with a vertex set X. Denote by small(G) the set of all connected components of G with at most √ n vertices and by large (G) the set of all connected components of G with more than √ n vertices. Let small v (G) denote the set of all vertices which are in the connected components belonging to small(G). We now make use of the fact that if there are many small components in G \ X, several of the assignments of the vertices in small v (G \ X) to the buckets are equivalent. Let C be a capacity vector of size n (i.e., i C[i] = n) and let B be a partial C-bucket arrangement of an induced subgraph G ′ of G. Let C ′ be the capacity vector obtained from C by decreasing the capacity C[i] of each bucket i by the number of vertices assigned to the bucket i in B. We say that B produces the capacity vector C ′ .

Exponential Time 2-Approximation Algorithm for Bandwidth
Let G = (V, E) be the input graph. Our algorithm tests all bucket sizes ℓ from 1 to ⌈n/2⌉ until it finds an (n, ℓ)-capacity vector C such that G has a C-bucket arrangement. For a given ℓ, let k = n ℓ denote the number of buckets. Our algorithm uses various strategies depending on the value of k. The case of k = 1 is trivial. If ℓ = ⌈n/2⌉, we have at most two buckets and any partition of the vertex set of G into sets of sizes ℓ and n − ℓ is a valid C-bucket arrangement. If k ≥ 27, Corollary 3.5 gives a running time of O * (1.9737 n ). For all other values of k, we will obtain the running times displayed in Table 1.
Let I k be the set of all integers lying between n/(k − 1) and n/k. The basic idea (as illustrated in Proposition 3.4) is quite simple. The algorithm tries all possible ways of assigning vertices to the middle bucket. Once the vertex set X assigned to the middle bucket is fixed and the algorithm has decided for each connected component of G \ X if the connected component is to be assigned to the buckets to the left or to the right of the middle bucket, the problem breaks into two independent subproblems on buckets which are to the left and to right of the middle bucket. To get the claimed running time, we build upon this idea to design individualized techniques for different k's (between 3 and 26). For each case, if G has at least one C-bucket arrangement for an (n, ℓ)-capacity vector C, then one such arrangement is constructed. We know that if G doesn't have any C-bucket arrangement for an (n, ℓ)-capacity vector C then the bandwidth of G is at least ℓ + 1 (Lemma 3.2), and if it has one then its bandwidth is at most 2ℓ − 1 (Lemma 3.1). If k = 8, 10, or 12, the algorithm uses a left-packed (n, ℓ)-capacity vector C, and otherwise, the algorithm uses a balanced (n, ℓ)-capacity vector C. k = 3. The algorithm goes over all subsets X ⊆ V of cardinality |X| = C[3] ≤ ⌈(n − ℓ)/2⌉ with ℓ ∈ I 3 . X is assigned to the bucket 3. If the remaining vertices can be assigned to the buckets 1 and 2 in a way such that all vertices which are neighbors of the vertices in X (in G) are assigned to the bucket 2, then G has a Cbucket arrangement where C has length 3. The worst-case running time for this case is max ℓ∈I 3 O * ( n |X| ). k = 4 or k = 5. The algorithm goes over all subsets X ⊆ V with |X| = ℓ and ℓ ∈ I k . X is assigned to the bucket 3. Then, we can conclude using the dynamic programming algorithm outlined in Proposition 3.6 (see also the remark following it). The worst-case running time for these cases are max ℓ∈I k O * ( n ℓ ). k = 6. If k = 6, the algorithm goes through all subsets X ⊆ V with |X| = 2ℓ and ℓ ∈ I 6 . X is assigned to the union of buckets 3 and 4 (i.e., some non-specified ℓ vertices from X are assigned to the bucket 3, and the remaining vertices of X are assigned to the bucket 4). Then, we can again conclude by the algorithm outlined in Proposition 3.6. The worst-case running time for this case is max ℓ∈I 6 O * n 2ℓ . k = 7. The algorithm goes through all subsets X ⊆ V with |X| = ℓ and ℓ ∈ I 7 . X is assigned to the bucket 4. For each such X, the algorithm uses Proposition 3.7 to enumerate all possible capacity vectors produced by the partial C-bucket arrangements of G[small v (G \ X) ∪ X] (with X assigned to the bucket 4). This step can be done in O * (3 √ n ) time. There are only polynomially many such (distinct) capacity vectors.
For each of these capacity vector C ′ , the algorithm goes through all choices of assigning each connected component in large(G \ X) to the buckets 1 to 3 or to the buckets 5 to 7. Thus, we obtain two independent subproblems on the buckets 1 to 3 and on the buckets 5 to 7. As the number of number of components in large(G \ X) is at most √ n (as each connected component has at least √ n vertices), going through all possible ways of assigning each connected component in large(G \ X) to the buckets numbered smaller or larger than 4 takes O * (2 √ n ) time. Some of these assignments may turn out to be invalid. For each valid assignment, let V 1 denote the vertex set assigned to the buckets 1 to 3. Then, the vertices of V 1 are assigned to the buckets 1 to 3 as described in the case with 3 buckets with the capacity vector (C ′ [1], C ′ [2], C ′ [3]) and with the additional restriction that all vertices in V 1 which are neighbors of the vertices in X need to be assigned to the bucket 3. The number of vertices in V 1 is at most ⌈(n − ℓ)/2⌉ (as C is balanced). Now the size of bucket 1 is C ′ [1] ≤ ⌈(n − 5ℓ)/2⌉. Let n 1 = ⌈(n − ℓ)/2⌉ and ℓ 1 = ⌈(n − 5ℓ)/2⌉. If V 1 has at least one valid bucket arrangement into 3 buckets (with vertices in V 1 neighboring the vertices in X assigned to the bucket 3), then the above step will construct one in worst-case O * ( n 1 ℓ 1 ) time. The algorithm uses a similar approach for V 2 = V \ (V 1 ∪ X) with the buckets 5 to 7. Since, the algorithm tries out every subset X for bucket 4, the worst-case running time for this case is   Table 1: Running time of the 2-approximation algorithm for Bandwidth according to the number of buckets k = ⌈n/ℓ⌉. I k is the set of all integers lying between n/(k−1) and n/k. The final running time is dominated by the cases of k = 7 and k = 8 (when ℓ is close to n/7). k = 8. The algorithm uses a left-packed (n, ℓ)-capacity vector C for this case. The algorithm goes through all subsets X ⊆ V with |X| = ℓ and ℓ ∈ I 8 . X is assigned to the bucket 4. The remaining analysis is similar to the case with 7 buckets. Buckets 1 to 3 have a joint capacity of 3ℓ (as C is left-packed) and the buckets 5 to 8 have a joint capacity of n − 4ℓ. The worst-case running time for this case is The terms in the max expression come from the running times for the cases with 3 and 4 buckets. k = 9 or k = 11. The algorithm goes through all subsets X ⊆ V with |X| = ℓ and ℓ ∈ I k . X is assigned to the bucket ⌈k/2⌉. As in the previous two cases, Proposition 3.7 is invoked for (with X assigned to the bucket ⌈k/2⌉). For each capacity vector generated by Proposition 3.7, the algorithm looks at every possible way of assigning each connected component in large(G \ X) to the buckets 1 to ⌈k/2⌉ − 1 or to the buckets ⌈k/2⌉ + 1 to k. Each assignment gives rise to two independent subproblemsone on vertices V 1 assigned to the buckets 1 to (k − 1)/2, and one on vertices V 2 assigned to the buckets (k + 3)/2 to k (with vertices in V 1 and V 2 neighboring the vertices in X assigned to the buckets (k − 1)/2 and (k + 3)/2, respectively). The algorithm solves these subproblems recursively as in the cases with 4 or 5 buckets. Let n 1 = ⌈(n − ℓ)/2⌉. Then, the worst-case running times are max ℓ∈I k O * ( n ℓ · 2 O( √ n) · n 1 ℓ ). k = 10 or k = 12. The algorithm uses a left-packed (n, ℓ)-capacity vector C for these cases. The algorithm goes through all subsets X ⊆ V with |X| = ℓ and ℓ ∈ I k . X is assigned to the bucket k/2. The remaining analysis is similar to the previous cases. For k = 10, the worst-case running time is max ℓ∈I 10 O * ( n ℓ · 2 O( √ n) · n/2 ℓ ). For k = 12, the worst-case running time is max ℓ∈I 12 O * ( n ℓ · 2 O( √ n) · max{ 5ℓ ℓ , n−6ℓ 2ℓ }).
13 ≤ k ≤ 26. The algorithm enumerates all subsets X ⊆ V with |X| = ℓ and ℓ ∈ I k . X is assigned to the bucket ⌈k/2⌉. As in the previous cases, Proposition 3.7 is invoked for G[small v (G \ X) ∪ X]. For each capacity vector generated by Proposition 3.7, the algorithm looks at every possible way of assigning each connected component in large(G \ X) to the buckets 1 to ⌈k/2⌉ − 1 or to the buckets ⌈k/2⌉ + 1 to k. Each assignment gives rise to two independent subproblems. For each of these two subproblems, the algorithm proceeds recursively until reaching subproblems with at most 2 consecutive empty buckets, which can be solved by Proposition 3.6 in polynomial time. If k ≤ 23, this recursion has depth 3, giving a running time of .
If 24 ≤ k ≤ 26, the recursion has depth 4, giving a running time of . k ≥ 27. By Proposition 3.4 the running time of the algorithm is bounded in this case by max ℓ∈I k O * n ℓ · n/2 ℓ · 2 4ℓ · 3 n/4 .

Main Result.
Putting together all the above arguments (and using the numerical values from Table 1) we get our main result (Theorem 3.8). The running time is dominated by the cases of k = 7 and k = 8. The algorithm outputs 2ℓ − 1, where ℓ is the smallest integer such that G has a bucket arrangement with an (n, ℓ)-capacity vector. The algorithm requires only polynomial space. If G is disconnected, then the algorithm finds for each connected component G i the smallest ℓ i such that G i has a bucket arrangement corresponding to an (n i , ℓ i )-capacity vector and outputs 2ℓ m − 1, where n i is the number of vertices in G i and ℓ m = max i {ℓ i }.

Conclusion
For finding exact solutions, it is known that many problems (by subexponential time preserving reductions) do not admit subexponential time algorithms under the Exponential Time Hypothesis [14] (a stronger hypothesis than P = NP). The Exponential Time Hypothesis supposes that there is a constant c such that 3-SAT cannot be solved in time O(2 cn ), where n is the number of variables of the input formula. We conjecture that the Bandwidth problem has no subexponential time 2-approximation algorithm, unless the Exponential Time Hypothesis fails.