Name
Abstract | ||
|---|---|---|
Many local search algorithms are based on searching in the k-exchange neighborhood. This is the set of solutions that can be obtained from the current solution by exchanging at most k elements. As a rule of thumb, the larger k is, the better are the chances of finding an improved solution. However, for inputs of size n, a naïve brute-force search of the k-exchange neighborhood requires nO(k) time, which is not practical even for very small values of k. We show that for several classes of sparse graphs, like planar graphs, graphs of bounded vertex degree and graphs excluding some fixed graph as a minor, an improved solution in the k-exchange neighborhood for many problems can be found much more efficiently. Our algorithms run in time O(τ (k) ċ nc), where τ is a function depending on k only and c is a constant independent of k. We demonstrate the applicability of this approach on different problems like r-CENTER, VERTEX COVER, ODD CYCLE TRANSVERSAL, MAX-CUT, and MIN-BISECTION. In particular, on planar graphs, all our algorithms searching for a k- local improvement run in time O(2O(k) ċ n2), which is polynomial for k = O(log n). We also complement the algorithms with complexity results indicating that--brute force search is unavoidable--in more general classes of sparse graphs. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.jcss.2011.10.003 | Journal of Computer and System Sciences |
Keywords | DocType | Volume |
sparse graph,improved solution,k-exchange neighborhood,larger k,planar graph,brute-force avoidable,brute force search,time o,brute-force search,current solution,local search,k element,local search algorithm,vertex cover,parameterized complexity,functional dependency,rule of thumb | Conference | 78 |
Issue | ISSN | Citations |
3 | 0022-0000 | 19 |
PageRank | References | Authors |
0.69 | 35 | 6 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michael R. Fellows | 1 | 4138 | 319.37 |
| Frances A. Rosamond | 2 | 684 | 34.52 |
| Fedor V. Fomin | 3 | 3139 | 192.21 |
| Daniel Lokshtanov | 4 | 1438 | 110.05 |
| Saket Saurabh | 5 | 2023 | 179.50 |
| Yngve Villanger | 6 | 592 | 37.08 |