Robust Algorithms for Recovering Planted r-Colorable Graphs

Abstract

The planted clique problem is a fundamental problem in the study of algorithms and has been extensively studied in various random and semirandom models. It is known that a clique planted in a random graph can be efficiently recovered if the size of the clique is above the conjectured computational threshold of Ω_p(√(n)). A natural question that arises then is: what other planted structures can be efficiently recovered? In this work, we investigate this question by considering random planted and semirandom models for the r-coloring problem. In our model, a subset S ⊆ V of size k is chosen, and an arbitrary r-colorable graph is planted on the subgraph induced by S. Edges between pairs in V ∖ S are added independently with probability p, and an adversary may add arbitrary edges between S and V ∖ S. Our main result is a polynomial-time algorithm that recovers most of the vertices of the planted r-colorable graph when k ≥ c r √(n/p), for some constant c. The key technical contribution is a novel semidefinite programming (SDP) relaxation and a rounding algorithm. Our algorithm is also robust to the presence of a monotone adversary that can insert edges within V ∖ S.