Sublinear-Time Algorithms for Tournament Graphs

摘要

We show that a random walk on a tournament on n vertices finds either a sink or a 3-cycle in expected time O (n~(1/2) · log n · log~* n~(1/2)), that is, sublinear both in the size of the description of the graph as well as in the number of vertices. This result is motivated by the search of a generic algorithm for solving a large class of search problems called Local Search, LS. LS is defined by us as a generalisation of the well-known class PLS.