WalkSAT is Linear on Random 2-SAT

Authors:

Abstract
In an influential article, Papadimitriou [ On selecting a satisfying truth assignment, in Proceedings of the 32nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 1991, pp. 163–169] proved that a local search algorithm called WalkSAT finds a satisfying assignment of a satisfiable 2-CNF with [Formula: see text] variables in [Formula: see text] expected time. Variants of the WalkSAT algorithm have become a mainstay of practical SAT solving (see, e.g., [Hoos and Stützle, J. Autom. Reason., 24 (2000), pp. 421–481]). In the present article, we analyze the expected running time of WalkSAT on random 2-SAT instances. Answering a question raised by Alekhnovich and Ben-Sasson [ SIAM J. Comput., 36 (2007) pp. 1248–1263], we show that WalkSAT runs in linear expected time for all clause/variable densities up to the random 2-SAT satisfiability threshold.
Funding Information
  • Deutsche Forschungsgemeinschaft (CO 646/3, CO 646/5, CO 646/6)
  • Deutsche Forschungsgemeinschaft (CO 646/6)
  • Deutsche Forschungsgemeinschaft (491453517)
  • Deutsche Forschungsgemeinschaft (411362735)

This publication has 22 references indexed in Scilit: