Local Search: Is Brute-Force Avoidable?

1 Introduction

The idea of local search is to improve a solution by searching for a better solution in a neighborhood which is defined in a problem specific way. For example, for the classical TRAVELING SALESPERSON problem, the neighborhood of a tour can be defined as the set of all tours that differ from it in at most k edges, this is called the k-exchange neighborhood [Lin and Kernighan, 1973; Papadimitriou and Steiglitz, 1977]. Another classical example is the MIN-BISECTION problem [Johnson et al., 1988], where for a given graph with 2n vertices and weights on the edges, the task is to partition the vertices into two sets of n vertices such that the sum of the weights of the edges between the sets is minimized. A natural k-exchange neighborhood for this problem would be

Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Yngve Villanger

{fomin,daniello,saket.saurabh,yngvev}

University of Bergen, 5020 Bergen, Norway. @ii.uib.no

the set of partitions that can be obtained from each other by swapping at most k pairs of vertices.

Most of the literature on local search is primarily devoted to experimental studies of different heuristics. The theoretical study of local search has been developing mainly in three directions. The first direction is the study of performance guarantees of local search, i.e. the quality of the solution [Papadimitriou and Steiglitz, 1982; Khanna et al., 1998]. The second direction of the theoretical work is on the asymptotic convergence of local search in probabilistic settings, such as simulated annealing [Aarts and Lenstra, 1997]. The third direction, which is the most relevant to our work, concerns the time required to reach a local optimum. An illustrative example here is the simplex method, which can be seen as a local search algorithm with feasible solutions corresponding to "vertices" of a polytope. The neighbors of a solution are the solutions that can be reached from it by a single "pivot". There can be different rules of choosing a pivot when several neighbors improve a solution. However, for each of the known rules there are examples requiring an exponential number of iterations for reaching the local optimum. Motivated by the fact that many local search algorithms are based on neighborhood structures for which locally optimal solutions are not known to be computable in polynomial time, [Johnson et al., 1988] defined a complexity class PLS which can be seen as an analogue of the class NP for local search problems. Many natural local search problems appear to be PLS-complete. We refer to books [Aarts and Lenstra, 1997; Michiels et al., 2007] for more information on different aspects of local search.

In this paper we take a different twist in the study of local search and endeavor to answer the following natural question. Is there a faster way of searching the k-exchange neighborhood than brute-force? This question is important because the typical running time of a brute-force algorithm is nO(k) , where n is the input length, which becomes a real obstacle in using k-exchange neighborhoods in practice even for sufficiently small values of k. For many years most algorithms searching for improved solution in the k-exchange neighborhood had an nO(k) running time, and thus creating an impression that this cannot be done significantly faster than the brute-force search. But is there mathematical evidence for this common belief? Or maybe for some problems it is possible to search k-exchange neighborhoods in time O(τ(k)nc ), where c is a small constant, which can make local search much more powerful?

An appropriate tool to answer all these questions is parameterized complexity. In the parameterized framework, for decision problems with input size n, and a parameter k, the goal is to design an algorithm with runtime τ(k) · nO(1) , where τ is a function of k alone. Problems having such an algorithm are said to be fixed parameter tractable (FPT). There is also a theory of hardness that allows to identify parameterized problems that are not amenable to such algorithms. The hardness hierarchy is represented by W[i] for i ≥ 1. For an introduction see [Downey and Fellows, 1999].

Relevant results. The parameterized complexity of local search remains unexplored with exceptions that are few and far between. As it was explicitly mentioned by Marx in a recent survey on local search problems [Marx, 2008a]: "So far, there are only a handful of parameterized complexity results in the literature, but they show that this is a fruitful research direction. The fixed-parameter tractability results are somewhat unexpected and this suggests that there are many other such results waiting to be discovered."

The first breakthrough in the area was done by [Marx, 2008b] who proved that finding a local improvement in kexchange neighborhood for TSP is W[1]-hard. Finding klocal optimum is not W[1]-hard for every NP-hard problem. An example of this can be found in the work of [Khuller et al., 2003] who investigated the NP-hard problem of finding a feedback edge set that is incident to the minimum number of vertices. One of the results obtained in [Khuller et al., 2003] is that checking whether it is possible to improve a solution by replacing at most k edges can be done in time O(n2 +nτ (k)), i.e., it is FPT parameterized by k. Very recently, [Krokhin and Marx, 2008] investigated the local search problem for finding a minimum weight assignment for a Boolean constraint satisfaction instance.

Our results. In this paper, we initiate the systematic study of parameterized complexity of local search for different graph problems. We investigate local search for problems on graphs of bounded local treewidth, a wide class of graphs containing planar graphs, graphs embeddable on a surface of bounded genus and graphs of bounded vertex degree. We show that many local search problems become FPT when the input graph is of bounded local treewidth. In particular, we show that finding k-local improvement on graphs of bounded local treewidth is FPT for many natural problems including VERTEX COVER, ODD CYCLE TRANSVERSAL, DOMINATING SET, and r-CENTER. We also show that finding k-local improvement for MAX-CUT, and MIN-BISECTION is FPT for apex-minor-free graphs. All these results are based on the idea of reducing the search in k-exchange neighborhood to searching for an improvement in a ball of small diameter around some vertex in the metric of the input graph. For example, on planar graphs, this approach leads to algorithms with running time O(2O(k) · n2 ) for many of the problems mentioned above. We also extend these results to more general classes of graphs, namely, graphs excluding a fixed graph as a minor. Finally, we show that existence of FPT algorithms is highly unlikely for larger classes of sparse graphs.

We prove that most of the problems remain W[1]-hard on 3degenerated graphs.

2 Preliminaries

Let G = (V, E) be an undirected graph where V (or V (G)) is the set of vertices and E (or E(G)) is the set of edges. We denote the number of vertices by n and the number of edges by m. For a subset V ′ ⊆ V , by G[V ′ ] we mean the subgraph of G induced by V ′ . By N(u) we denote (open) neighborhood of u that is set of all vertices adjacent to u and by N[u] = N(u) ∪ {u}. Similarly, for a subset D ⊆ V , we define N[D] = ∪v∈DN[v]. The distance dG(u, v) between two vertices u and v of G is the length of the shortest path in G from u to v. The diameter of a graph G, denoted by diam(G), is defined to be the maximum length of a shortest path between any pair of vertices of V (G). By an abuse of notation, we define diameter of a graph as the maximum of the diameters of its connected components. For r ≥ 0, the r-neighborhood of a vertex v ∈ V is defined as N rG[v] = {u | dG(v, u) ≤ r}. We also let B(r, v) = N rG[v] and call it a ball of radius r around v. Similarly B(r, A) = ∪v∈AN rG[v] for A ⊆ V (G). Given a weight function w : V → R+ ∪ {0} and A ⊆ V (G), w(A) = ∑u∈A w(u).

Given an edge e = (u, v) of a graph G, the graph G/e is obtained by contracting the edge (u, v); that is, we get G/e by identifying the vertices u and v and removing all the loops and duplicate edges. A minor of a graph G is a graph H that can be obtained from a subgraph of G by contracting edges. A graph class C is minor closed if any minor of any graph in C is also an element of C. A minor closed graph class C is Hminor-free or simply H-free if H /∈ C. A graph H is called an apex graph if the removal of one vertex makes it a planar graph.

A tree decomposition of a (undirected) graph G is a pair (X, T) where T is a tree whose vertices we will call nodes and X = ({Xi | i ∈ V (T)}) is a collection of subsets of V (G) such that (a) ⋃i∈V (T) Xi = V (G), (b) for each edge (v,w) ∈ E(G), there is an i ∈ V (T) such that v,w ∈ Xi, and (c) for each v ∈ V (G) the set of nodes {i | v ∈ Xi} forms a subtree of T. The width of a tree decomposition ({Xi | i ∈ V (T)}, T) equals maxi∈V (T){|Xi| - 1}. The treewidth of a graph G is the minimum width over all tree decompositions of G. We use notation tw(G) to denote the treewidth of a graph G. The definition of treewidth can be generalized to take into account the local properties of G and is called local treewidth [Eppstein, 2000].

Definition 1 (Local tree-width). The local tree-width of a graph G is a function ltwG : N → N which associates to every integer r ∈ N the maximum tree-width of an r-neighborhood of vertices of G, i.e. ltwG(r) = maxv∈V (G){tw(G[N rG(v)])}.

For a function h : N → N we define the graph class Gh such that for each graph G ∈ G , and for each integer r ∈ N, we have ltwG(r) ≤ h(r). We say that a class of graphs G is of bounded local treewidth if G ⊆ Gh for some h : N → N. Well known graph classes of bounded local treewidth are planar graphs, graphs of bounded genus, and graphs of bounded maximum vertex degree. By the result of [Robertson and Seymour, 1986] (see also [Bodlaender, 1998]), h(r) can be chosen as 3r for planar graphs. Similarly [Eppstein, 2000] showed that h(r) can be chosen as cgg(Σ)r for graphs embeddable in a surface Σ, where g(Σ) is the genus of the surface Σ and cg is a constant depending only on g(Σ). [Demaine and Hajiaghayi, 2004] extended this result and showed that for minor closed families of graphs which do not contain some fixed apex graph as a minor, h(r) = O(r).

3 Framework of Study

For many optimization problems defined on graphs, the solution is a subset of vertices or edges of the graph. This is the case for the problems VERTEX COVER, INDEPENDENT SET, and DOMINATING SET to name a few. A problem P is a vertex subset problem (or an edge subset problem) if a feasible solution to P is V ′ ⊆ V (E′ ⊆ E). We use S to denote the set of feasible solutions to a problem P .

For vertex subset (or edge subset) problems, a natural neighborhood function is obtained by exchanging k elements of the current solution. The neighborhood function in which we are interested is called k-exchange neighborhoods (kExN). We elaborate this further for minimization vertexsubset problems. Let w : V → R+ be a weight function. Then the cost function c : S → R+ is defined as ∑v∈s w(v) for all s ∈ S. For a pair of elements s1, s2 ∈ S, let H(s1, s2) denote the Hamming distance that is the size of the set |s1 \ s2|. We say that s′ is neighbor of s with respect to k-ExN if H(s, s′ ) ≤ k. Let N en k (s) denote the set of neighbors of s with respect to k-ExN. Then the generic problem of local search for a vertex subset graph optimization problem P with respect to k-ExN is defined as follows.

k-LOCAL SEARCH P (k-LS-P)

Input: A graph G = (V, E), a weight function w : V → R+, a solution S and an integer k ≥ 0.

Parameter: A positive integer k.

Question: Does there exist a solution T ∈ N en k (S) such that c(T ) < c(S) if P is minimization problem (and c(S) > c(T ) if P is maximization problem)?

In general, an input to parameterized local search problem for a graph optimization problem P consists of five parts: (G = (V,E),w,M, S, k), where S is an initial solution, w : V → R+, M is a distance function defined on the solution space S and k ∈ N is a positive integer. If w is a unit weight function then we ignore w and only have four parts (G = (V,E),M, S, k). Unless otherwise mentioned, we only consider the Hamming distance H in this paper, and hence this term is deleted from the input.

4 FPT Algorithms for k-LS in Graphs of Bounded Local Treewidth

In this section we show that, many local search problems become fixed parameter tractable in graphs of bounded local treewidth.

4.1 Domination Problems

In this section we give an algorithm for the local search variant of a generalization of DOMINATING SET, called the WEIGHTED r-CENTER problem. A subset S ⊆ V is called an r-center if V ⊆ B(r, S). In k-LS-r-CENTER, we are given an undirected graph G = (V, E), with weight function w : V → R+, a r-center S ⊆ V and integers k, r. The problems asks whether there exists a S′ ∈ N en k (S) such that c(S′ ) < c(S). Here k and r are the parameters.

When r = 1 this is the k-LS-DOMINATING SET problem. Our result is based on a combinatorial characterization of changed solutions. We prove that if there is an improved solution that is close to the current solution in the solution space, then there is another improved solution close to the current one in the solution space with the additional property that all changes are concentrated locally in the input graph.

Lemma 1. Let S1 and S2 be r-centers of a weighted graph G = (V,E) with weight function w : V → R+, such that the cardinality of the symmetric difference S1 △S2 is at most p, and c(S1) > c(S2). Then there are sets F1, F2 ⊆ V such that (a) the set S = (S1 \ F1) ∪ F2 is an r-center of G and c(S) < c(S1); (b) |F1 ∪ F2| ≤ p; and (c) there is a vertex z ∈ V such that F1 ∪ F2 is in B(z, 2pr).

Proof. Let X = S1 \ S2 and Y = S2 \ S1. Furthermore, (a) X ∩ Y = ∅ and (b) S1 \ X = S2 \ Y = S1 ∩ S2. This implies that c(S1) = w(S1 \ X) + w(X) > c(S2) = w(S2 \ Y ) + w(Y ), and hence w(X) > w(Y ). Consider the auxiliary graph G∗ = (X∪Y = S1△S2,E′ ), where we give an edge between two vertices u, v ∈ (X∪Y ) if d(u, v) ≤ 2r, that is, the shortest path distance between u and v is at most 2r in G. Let C1, . . . ,Cp be the connected components of G∗ . For every connected component Ci we assign a tuple μ(Ci) = (x, y) where x = w(X ∩ Ci) and y = w(Y ∩ Ci). Since w(X) > w(Y ), there exists a connected component Cj such that x > y in μ(Cj). We claim that we can take S1 \ (X∩Cj)∪(Y ∩Cj) as the desired S, F1 = X∩Cj and F2 = Y ∩Cj.

First, c(S) = w(S1) -w(X ∩Cj) +w(Y ∩Cj) < c(S1), since x > y. Now we show that S is a r-center of G. We know that S1 is a r-center of G and hence only vertices which could be at distance more than r from the vertices of S are those which were distance at most r from the vertices in (X∩ Cj). Let u be a vertex which is at distance more than r from any vertex in S. Then there exists a vertex, say u1 ∈ (X ∩ Cj), such that d(u, u1) ≤ r. Furthermore, S2 is an r-center not containing any of the vertices of (X ∩Cj). Hence, there exists v ∈ Y such that d(u, v) ≤ r. But this implies that d(u1, v) ≤ 2r and hence v ∈ (Y ∩ Cj). This proves that S is an r-center of G. We can select any vertex in X ∩ Cj for z. The size of Cj is at most p and any vertex adjacent in this component are at distance at most 2r in G. Hence, the ball around z of radius 2pr contains all the vertices of F1 ∪ F2; that is, (F1 ∪ F2) ⊆ B(z, 2pr).

We define a generalized form of k-LS-r-CENTER which we call k-LS-GENERALIZED-r-CENTER where apart from S, we are also given a subset T ⊆ S, and we need to find a solution S′ ∈ N en k (S) such that c(S′ ) < c(S) and T ⊆ S′ . So an instance of k-LS-GENERALIZED-r-CENTER looks like (G, w, S, T, k).

Lemma 2. Let G be the class of graphs which is closed under taking induced subgraphs and for which we can solve k-LSGENERALIZED-r-CENTER in time f(ℓ) · |G|O(1) whenever G ∈ G and of diameter at most ℓ. Then k-LS-r-CENTER is FPT for G.

Proof. Let (G,w, S, k) be an instance of k-LS-rCENTER where G ∈ G. Lemma 1 implies that if the given instance is an YES instance then there exists a solution S′ ∈ N en k (S) with c(S′ ) < c(S) and z ∈ S \ S′ such that S △ S′ ⊆ B(z, 4rk).

We go through every vertex v in S as the desired z and do as follows. We do BFS starting at v. Let the layers created by doing BFS on v be Lv0 , Lv1 , . . . , Lvt . We have two cases: either (a) t ≤ 4rk + r or (b) t > 4rk + r. In case (a) we set Tv = ∅ and get (G, w, S, Tv, k) as an instance for k-LSGENERALIZED-r-CENTER. In the other case, we first take 4rk + r layers; that is,

We know that all the changed vertices, those that go out and those that will come in (that is, vertices in the set S△S′ ) are in B(v, 4rk). Let Tv := (S ∩ (∪4rk+r j=4rk+1Lvj )). Furthermore, for v ∈ S, let Sv = S ∩ B(v, 4rk + r). For every v ∈ S, we get the following instance (B(v, 4rk + r),w, Sv, Tv, k) for k-LS-GENERALIZED-r-CENTER. An instance (G,w, S, k) is an YES instance for k-LS-r-CENTER if and only if there exists a v ∈ S for which (B(v, 4rk + r), w, Sv, Tv, k) is an YES instance for k-LS-GENERALIZED-r-CENTER. Since kLS-GENERALIZED-r-CENTER is solvable in time f(4rk + r) · |B(v, 4rk + r)|O(1) for G[B(v, 4rk + r)] for v ∈ S, we have that k-LS-r-CENTER for G is solvable in time f(4rk+ r) · |G|O(1) . This concludes the proof of the lemma.

The proof of the following lemma is similar to the proof for k-LS-r-CENTER from [Demaine et al., 2005a] and we omit it here.

Lemma 3. Let G be the class of graphs of treewidth at most t, then k-LS-GENERALIZED-r-CENTER can be solved in time O((2r +1)t · |G|O(1) ) for graphs G ∈ G.

Theorem 1. Let h : N → N be a given function. Then k-LSr-CENTER can be solved in time O((2r + 1)h(2k) · |G|O(1) ) for graphs G ∈ Gh.

Proof. Let (G,w, S, k) be an instance of k-LS-r-CENTER. Since G ∈ Gh, the treewidth tw(G[B(v, 4rk + r)]) ≤ h(4rk + r) for all v ∈ S. Using Lemma 3 we solve k-LS-GENERALIZED-r-CENTER for instances (B(v, 4rk + r), Sv, Tv, k) for every v ∈ S in time O((2r + 1)h(4rk+r) · |B(v, 4rk + r)|O(1) ). This in combination with Lemma 2 completes the proof.

Let us remark that by Theorem 1, k-LS-r-CENTER is FPT for planar graphs, graphs of bounded genus and graphs of bounded maximum degree.

In the VERTEX COVER problem one seeks for a vertex subset of minimum weight such that every edge has at least one endpoint in this set.

Our algorithm for k-LS-VERTEX COVER is based on the FPT algorithm for k-LS-r-CENTER. In fact, it is possible to give a local search preserving parameterized reduction from k-LS-VERTEX COVER to k-LS-DOMINATING SET that preserves the property of local treewidth. We omit the details here.

Theorem 2. Let h : N → N be a given function such that h(i) ≥ 2 for every i. Then k-LS-VERTEX COVER can be solved in time O(3h(2k) · |G|O(1) ) for graphs G ∈ Gh.

4.2 Odd Cycle Transversal

In the ODD CYCLE TRANSVERSAL problem one seeks for a vertex subset S of minimum weight in a graph, such that every cycle of odd length in the graph contains at lest one vertex from S. In other words, after removal of S, the remaining vertices induce a bipartite graph. This problem is interesting to look at because of the following. All the problems we considered so far have a certain "locality" involved. At first glance ODD CYCLE TRANSVERSAL look like a "non-local" problem . For ease of presentation we only deal with the unweighted case, but weighted cases can be handled in a similar manner. Our algorithm is based on a combinatorial observation, which allows us to construct local search preserving parameterized reduction to k-LS-INDEPENDENT SET. (The MAXIMUM INDEPENDENT SET problem is to find a maximum set of pairwise non-adjacent vertices in a graph.)

Given a graph G = (V,E), we define a new graph ˜G = (V ′ , E′ ) as follows. Let Vi = {ui | u ∈ V }, i ∈ {1, 2}. Take V ′ = V1 ∪ V2 and E′ = {u1u2 | u ∈ V } ∪ {uivi | uv ∈ E, i ∈ {1, 2}}. Given a set T ⊆ V such that G[T] is a bipartite graph with bipartition T1 and T2 then by ˜ T denote the set ˜ T1 = {u1 | u ∈ T1} ∪ ˜ T2 = {u2 | u ∈ T2} in V ′ . The graph ˜G has some interesting properties which we make use of when designing the local search algorithm for ODD CYCLE TRANSVERSAL.

The proofs of the following two lemmas is omitted due to space restrictions. The proof of Lemma 4 is based on a result from [Saurabh, Thesis 2008].

Lemma 4. (G, S, k) is an YES instance of k-LS-INDUCED BIPARTITE SUBGRAPH if and only if ( ˜G, ˜ S, k) is an YES instance of k-LS-INDEPENDENT SET.

Lemma 5. Let h : N → N and g = 2h + 1 be two given functions. If G ∈ Gh, then ˜G ∈ Gg .

By Theorem 2, we have that k-LS-VERTEX COVER is FPT on graphs of bounded local treewidth. Since a set S is a vertex cover of a graph G = (V, E) if and only if V \ S is an independent set, we get that the same result also holds for k-LSINDEPENDENT SET. Combining Theorem 2 with Lemmas 4 and 5, we arrive at the following.

Theorem 3. Let h : N → N be a given function. Then k-LSODD CYCLE TRANSVERSAL and k-LS-INDUCED BIPARTITE SUBGRAPH can be solved in time O(3g(2k) · |G|O(1) ) for graphs G ∈ Gh where g = 2h + 1.

Planar graphs, and more generally, graphs of bounded genus and apex-minor-free graphs, are in Gh for some linear function h, and Theorems 1, 2, and 3 yield the following.

Corollary 1. On apex-minor-free graphs k-LS-r-CENTER is solvable in time rO(k) · |G|O(1) and k-LS-VERTEX COVER, and k-LS-ODD CYCLE TRANSVERSAL are solvable in time 2O(k) · |G|O(1) .

4.3 Graph Partitioning Problems

In this section we look at local search algorithms for graph partitioning problems such as MAX-CUT and MIN- (MAX-) BISECTION. Let G = (V, E) be a given graph and w : E → R+ be a weight function. Then MAX-CUT asks for a partition of V into V1 and V2 such that the total weight of edges (u, v) with u ∈ V1 and v ∈ V2 is maximized whereas in MAX(MIN-) BISECTION the objective is to find a partition of V into V1 and V2 such that (a) |V1| = |V2| = |V |/2 and (b) the total weight of edges (u, v) with u ∈ V1 and v ∈ V2 is maximized (minimized).

We give an algorithm for a local search variant of MINBISECTION. Others follow along similar lines. Given a partition (V1, V2) let E(V1, V2) be the edges with one endpoint in V1 and other in V2, and let c((V1, V2)) = ∑e∈E(V1,V2) w(e). We now define the notion of N en k (V1, V2) for this problem. A partition (V ′ 1 , V ′ 2 ) ∈ Nk(V1, V2) if there exist subsets X ⊆ V1 and Y ⊆ V2 such that (a) |X| = |Y | = r, r ≤ k and (b) V ′ 1 = (V1 \ X) ∪ Y and V ′ 2 = (V2 \ Y ) ∪X.

Theorem 4. Let h : N → N be a given function. Then k-LSMINIMUM-BISECTION, k-LS-MAXIMUM-BISECTION and k-LS-MAXIMUM-CUT can be solved in time O(2h(ck) · |G|O(1) ) for graphs G ∈ Gh such that for every minor H of G, H ∈ Gh. In particular k-LS-MINIMUM-BISECTION is FPT for planar graphs and graphs of bounded genus.

Proof. We give the proof for k-LS-MINIMUM-BISECTION, and the proofs for other problems follow the same arguments. Let (G,w, (V1, V2), k) be the input to k-LS-MINIMUMBISECTION. In the first part of the proof we show that we can solve k-LS-MINIMUM-BISECTION by solving an equivalent problem on graphs of bounded diameter (or bounded treewidth).

Reducing to graphs of bounded treewidth: We start with a BFS starting at a vertex v ∈ V . Let the layers created by doing BFS on v be Lv0 , Lv1 , . . . , Lvt . If t ≤ 6k +10, we move to the second phase of the algorithm. From now onwards we assume that t > 6k + 3. We create thick layers from the above layers: W v i = ⋃3i+2 j=3i Lvj , where i ∈ {0, . . . , s = ⌊ t+1 3 ⌋}. The last thick layer may contain less than 3 layers. Now we make following partition of the vertex set Tq, q ∈ {0, . . . , 2k + 1}. We define Tq = ⋃ Wq+i(2k+2), i ∈ {0, . . . , ⌊ s+1 2k+2 ⌋} . It is clear from the definition of Tq that it partitions the vertex set. If the input is an YES instance then there exists a partition (V ′ 1 , V ′ 2 ) ∈ Nk(V1, V2) such that the total number of vertices which will flip its side (or vertices which will participate in change) is upper bounded by 2k. Using the pigeon hole principle, we conclude that there exist Ta such that it does not contain any of these changed vertices and does not contain Ws. We can find the desired Ta by trying all Tq 's.

Now for every W v i = ⋃3i+2 j=3i Lvj contained in Ta, we remove the vertices of Lv3i+1 (that is, the central layer). Let this set of vertices be called V ′ and the resultant graph be G′ with connected components C1, . . . , Cr. We show that each connected component Ci of G′ has bounded treewidth. More precisely, every connected component Ci of G′ is a subset of at most 6k + 10 layers of the BFS. If we start with G, delete all BFS layers outside of these layers and contract all BFS layers inside of these layers into v we obtain a minor H of G. H has diameter at most 6k + 11, and also H contains Ci as an induced subgraph. Since every minor of G has bounded local treewidth, Ci has bounded treewidth, that is tw(Ci) ≤ h(6k + 10) for every i. The reason for removing central layers from each W v i is that this retains all the edges which could participate in improved cuts, as well as reduces the treewidth of the graph. In certain sense, the first and third layers of vertices in W v i shields the vertices of the middle layer by not participating in change. Notice that since every connected component of G′ has bounded treewidth, G′ itself has also bounded treewidth.

Finding appropriate solutions using Dynamic Programming: Let ˜ V1 = V1 \ V ′ and ˜ V2 = V2 \ V ′ . Furthermore T ′ = Ta \ V ′ . Then there exists (V ′ 1 , V ′ 2 ) ∈ N en k (V1, V2) such that c(V1, V2) > c(V ′ 1 , V ′ 2 ) if and only if there exists ( ˜ V ′ 1 , ˜ V ′ 2 ) ∈ N en k (˜ V1, ˜ V2) such that c(˜ V1, ˜ V2) > c( ˜ V ′ 1 , ˜ V ′ 2 ) and T ′ ∩ ( ˜ V ′ 1 △ ˜ V1) = ∅ (that is, changed vertices should not include any vertex from T ′ ). Searching for ( ˜ V ′ 1 , ˜ V ′ 2 ) reduces to a problem in G′ , a graph of bounded treewidth. We can solve this problem using standard dynamic programming over graphs of bounded treewidth in time 2h(6k+11) · nO(1) . We can also keep appropriate information during dynamic programming to find the desired cut explicitly. This concludes the proof of the theorem.

5 Limits for FPT Algorithms

The results for k-LS variant for various problems considered in the previous sections can be extended for graphs excluding a fixed graph H as a minor in a non-trivial manner. This extension is based on the structural theorem of [Robertson and Seymour, 2003], which provides a description of an H-minor free graph in terms of clique-sum decomposition over almost embeddible graphs. By making use of this decomposition it is possible to replace dynamic programming algorithms from previous section over graphs of bounded treewidth by dynamic programming over "cliquesum decomposition of H-minor graphs". For all our algorithms for k-LS problems for H-minor free graphs, we will eventually reach a stage where we need to solve an "appropriate" problem in graphs of bounded diameter (previously at this step we applied a dynamic programming algorithm over graphs of bounded treewidth). We first obtain a cliquesum decomposition for the input graph G and then do two layer dynamic programming over clique-sum decomposition as done in [Demaine et al., 2005b].Here we use a non trivial modification of the problem to cope with its local search variant. This proof is long and technical, we postpone it for the full version of the paper.

Theorem 5. k-LS-VERTEX COVER, k-LS-r-CENTER, and k-LS-ODD CYCLE TRANSVERSAL are FPT on the class of H-minor free graphs.

Finally, we observe that, in some sense, H-minor free graphs are the most general classes of graphs for which positive results for these local search problems can be expected. We show that for more general classes of sparse graphs many local search problems become W[1]-hard. Thus the existence of k-exchange FPT algorithms for these problems would contradict the widely believed assumption from parameterized complexity, namely FPT ̸=W[1].

A graph G is d-degenerated if every induced subgraph of G has a vertex of degree at most d.

Theorem 6. k-LS-ODD CYCLE TRANSVERSAL is W[1]- hard even when restricted to 2-degenerate graphs. Furthermore, k-LS-INDEPENDENT SET and k-LS-DOMINATING SET are W[1]-hard when restricted to 3-degenerate graphs.

6 Conclusions and Future Directions

In this paper we studied parameterized complexity of local search for different graph problems. We have shown that, one can search k-exchange neighborhood of a solution significantly better than the brute force for many natural problems for general classes of sparse graphs. We also provided hardness proofs that indicate that most of our results can not be further generalized. There are several open questions that need to be resolved. For instance, all our algorithmic results either depend on an observation that allows us to consider small diameter graphs, or are reducible to problems where such an approach is feasible. An important problem for which these techniques do not seem to be applicable is the TRAVELLING SALESMAN PROBLEM. Thus, the main problem we leave open in this paper is to resolve the complexity of the k-LS-TRAVELLING SALESMAN PROBLEM in planar graphs. Finally, one wonders whether running times of the form O(2O(k)n) are the best one can hope for local search problems in planar graphs, or whether algorithms running in time O(2o(k)nc ) could be feasible.