Robust Algorithms for recovering planted structures in Semi-random instances

Abstract

In this thesis, we study algorithms for three fundamental graph problems. These are NP-hard problems which have not been understood completely as there is a signifiicant gap between the algorithmic and the hardness fronts or the hardness factor in the worst-case is pretty large. Thus it is natural to study them in random and semi-random models. This falls under the area of "Beyond worst-case Analysis". We describe these problems now.

In the first part, we study the Densest k-subgraph problem (DkS). Given an undirected graph G, the DkS problem asks to compute a set S \subseteq V of cardinality S \leq k such that the weight of edges inside S is maximized. This is a fundamental NP-hard problem whose approximability, in spite of many decades of research, is yet to be settled. We study this problem in models of instances with a planted dense graph and algorithms to recover it.

In the second part, we study the Planted Clique problem, i.e., plant a clique instead of an arbitrary dense subgraph in a semi-random model. This model generalizes some of the above models but we get much stronger guarantees of recovery for this special subcase.

And finally in the third part, we study the Independent Set problem in r-uniform hypergraphs (r \geq 2), which poses the following question: given a hypergraph, and a subset of vertices such that any r vertices of the set do not have an edge between them. The maximization version of this problem features as one of the Karp's original twenty-one NP-complete problems [Kar72].

Our semi-random models are inspired from the Feige-Kilian model [FK01]. This is a well known model and has been studied along with its many variants in the works of Steinhardt [Ste17], McKenzie et al. [MMT20], etc. for a variety of graph problems including graph coloring [CO07], graph partitioning problems [MMV12, MMV14, MNS16, LV18, LV19], independent set problem [FK01, Ste17, CSV17, MMT20] etc. to name a few. Random and semi-random models of instances have been studied for the Densest k-subgraph problem and the Planted Clique problem (along with its many variants) in the works of [McS01, BCC+10, Ame15, HWX16b, BA19] etc.

All of our algorithms are based on rounding a semidefinite program (SDP). Our goal is to study these hard problems in semi-random models which helps us identify some "easier" instances where we can design approximation algorithms with "good" factors (say as compared to the worst-case models). Moreover, our algorithm recovers a "significant" part of the planted solution for a large range of parameters of these models.