Finding near-optimal independent sets at scale

Sebastian Lamm (), Peter Sanders (), Christian Schulz (), Darren Strash () and Renato F. Werneck ()
Additional contact information
Sebastian Lamm: Karlsruhe Institute of Technology (KIT)
Peter Sanders: Karlsruhe Institute of Technology (KIT)
Christian Schulz: Karlsruhe Institute of Technology (KIT)
Darren Strash: Colgate University

Journal of Heuristics, 2017, vol. 23, issue 4, No 2, 207-229

Abstract: Abstract The maximum independent set problem is NP-hard and particularly difficult to solve in sparse graphs, which typically take exponential time to solve exactly using the best-known exact algorithms. In this paper, we present two new novel heuristic algorithms for computing large independent sets on huge sparse graphs, which are intractable in practice. First, we develop an advanced evolutionary algorithm that uses fast graph partitioning with local search algorithms to implement efficient combine operations that exchange whole blocks of given independent sets. Though the evolutionary algorithm itself is highly competitive with existing heuristic algorithms on large social networks, we further show that it can be effectively used as an oracle to guess vertices that are likely to be in large independent sets. We then show how to combine these guesses with kernelization techniques in a branch-and-reduce-like algorithm to compute high-quality independent sets quickly in huge complex networks. Our experiments against a recent (and fast) exact algorithm for large sparse graphs show that our technique always computes an optimal solution when the exact solution is known, and it further computes consistent results on even larger instances where the solution is unknown. Ultimately, we show that identifying and removing vertices likely to be in large independent sets opens up the reduction space—which not only speeds up the computation of large independent sets drastically, but also enables us to compute high-quality independent sets on much larger instances than previously reported in the literature.

Keywords: Maximum independent set problem; Minimum vertex cover problem; Evolutionary/genetic algorithms; Heuristic algorithms; Local search; Kernelization (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10732-017-9337-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joheur:v:23:y:2017:i:4:d:10.1007_s10732-017-9337-x

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-017-9337-x

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().