Recovery Algorithms for planted structures in Semi-random models

Abstract

For many NP-hard problems, the analysis of best-known approximation algorithms yields “poor” worst-case guarantees. However, using various heuristics, the problems can be solved (to some extent) in real-life instances. This success can be attributed to the atypicality of worst-case instances in real life, and therefore motivates studying the problem in “easier” instances. Analyzing the problem in Planted solution models and Semi-random models is one such systematic approach along these lines.

In this thesis, we study planted solution models and semi-random models for various graph problems. Given a graph G with n vertices, we consider the task of finding the largest induced subgraph of G with a particular structure. We start by studying the problem where the particular structure is a planar graph. Next, we look at the Odd Cycle Transversal problem or equivalently the problem of finding the largest induced bipartite subgraph. Finally, we study the problem of finding the largest independent set in r-uniform hypergraphs. All these problems are NP-hard and have abysmal worst-case approximation guarantees.

An instance of a planted solution model is constructed by starting with a set of vertices V, and choosing a set S ⊆ V of k vertices, and adding a particular structure to it. Edges between pairs of vertices in S x (V\S) and (V\S) x (V\S) are added independently with probability p. The algorithmic task then is to recover this planted structure. As a special case for all these problems, when the planted structure is an empty graph, the problem reduces to recovering a planted independent set and we dont expect recovery algorithms for k =o(√n).

For the problem of finding the largest induced bipartite subgraph, we give an exact recovery algorithm that works for k = Ω_p(n log n)^1/2. For the problem of finding the maximum independent set in r-uniform hypergraphs, we give an algorithm that works for Ω_p(n^{r-1/r-0.5}). Our results also hold for a natural semi-random model of instances inspired by Feige and Kilian [FK01] model. Our algorithms are based on analyzing continuous relaxations of these problems. We employ techniques from Spectral Graph Theory, Convex Optimization (Linear Programs (LPs) and Semi-Definite Programs (SDPs) relaxations), and Lasserre/Sum-of-Squares hierarchy strengthening of convex relaxations.