A New Algorithm for the Robust Semi-random Independent Set Problem
Theo McKenzie, Hermish Mehta, Luca Trevisan · Society for Industrial and Applied Mathematics eBooks · 2019
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 = an where a is a constant, and the probability of a random edge p > (1 + ϵ) ln n/αn. 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 = Ω(n2/3/p1/3), and finds a list of independent sets, one of which is the planted one provided that k = Ω(n2/3/p). This improves on the algorithm of Feige and Kilian by working for smaller k if p = Ω(1/n1/3), and improves on an 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.