A New Algorithm for the Robust Semi-random Independent Set Problem

We study the independent set problem in a semi-random model proposed by Feige and Kilian. This model selects a graph with a planted independent set of size k and then allows an adversary to modify a large fraction of edges: the subgraph induced by the complement of the independent set can be modified arbitrarily, and the adversary may add (but not delete) edges from the independent set to its complement. In particular, the adversary can create a graph in which the initial planted independent set is not the largest independent set. Feige and Kilian presented a randomized algorithm, which with high probability recovers an independent set of size at least k (which may not be the planted one) when k = αn where α is a constant, and the probability of a random edge p > (1 + ǫ) ln n/αn. Steinhardt studied a restriction of this model in which the adversary is not allowed to add edges from the planted independent set to its complement, and focused on the problem of finding the planted independent set. He develops an algorithm that, given a random "seed" vertex in the planted independent set, finds the planted independent set provided that k = Ω(n 2/3 log n 1/3 ) in the p = 1/2 regime. Equivalently, by guessing the seed, the algorithm is able to output a list of at most n independent sets of size k such that one of them is the planted one.

We give a new deterministic algorithm in the Feige-Kilian model that finds an independent set of size at least .99k provided that the planted set has size k = Ω(n 2/3 /p 1/3 ), and finds a list of independent sets, one of which is the planted one provided that k = Ω(n 2/3 /p). This improves on the algorithm of Feige and Kilian by working for smaller k if p = Ω(1/n 1/3 ), and improves on the algorithm of Steinhardt by working for slightly smaller k and by working against a stronger adversarial model. The ability to find a good approximation of the largest independent set is new when p < ln n/k.