Local search: Is brute-force avoidable?

Michael Fellows, Fedor Fomin, Daniel Lokshtanov, Frances Rosamond, Saket Saurabh, Y Villanger

    Research output: Contribution to journalArticle

    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, including 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 only on k and c is a constant independent of k and n. We demonstrate the applicability of this approach on a variety of problems including 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 complement these fixed-parameter tractable algorithms for k-local search with parameterized intractability results indicating that brute-force search is unavoidable in more general classes of graphs. 
    Original languageEnglish
    Pages (from-to)707-719
    Number of pages13
    JournalJournal of Computer and System Sciences
    Volume78
    Issue number3
    DOIs
    Publication statusPublished - May 2012

    Fingerprint Dive into the research topics of 'Local search: Is brute-force avoidable?'. Together they form a unique fingerprint.

  • Cite this

    Fellows, M., Fomin, F., Lokshtanov, D., Rosamond, F., Saurabh, S., & Villanger, Y. (2012). Local search: Is brute-force avoidable? Journal of Computer and System Sciences, 78(3), 707-719. https://doi.org/10.1016/j.jcss.2011.10.003