In this work, we design algorithms for two fundamentally important and classical graph problems in the planted setting. Both of these problems are NP-hard and the bounds known from the algorithmic front are either not fully understood, or not much progress can be made because of tight lower bounds. Thus it is natural to consider semi-random models for these problems. These models are inspired from the seminal paper of Feige and Killian [FK01] and have been studied in numerous follow-up works with the latest ones by Steinhardt, and McKenzie et al. [Ste17, MMT20]. The construction of our instance starts with an empty graph, then an arbitrary set of vertices (S) is chosen and either a dense graph or a clique (or an independent set) is planted on it, the subgraph on S x V-S is a random graph, while the subgraph on V-S might be a random, arbitrary, or some special graph (depending on the model). Our algorithms are based on rounding semi-definite programs and our primary focus is on recovering (completely or partially) the planted structure (S) with high probability (over the randomness of the input). We give algorithms that exploit the geometry of the corresponding vectors (from the SDP) and are easy to design/analyse.
The two problems which we study are:
1. Densest k-Subgraph/Clique
Given an undirected graph G, the Densest k-Subgraph problem (DkS) asks to compute a subset S of V of cardinality k such that the weight of edges inside S is maximized. This is a fundamental NP-hard problem whose approximability, inspite of many decades of research, is yet to be settled. There is a significant gap between the best known worst-case approximation factor of this problem [BCC+10] and the hardness of approximation for it (assuming the Exponential Time Hypothesis) [Man17]. We ask what are some easier instances of this problem? We propose some natural semi-random models of instances with a planted dense subgraph, and study approximation algorithms for computing the densest subgraph in them. There are many such random and semi-random models which have been studied in the literature [BCC+10, Ame15, HWX16, BA19 etc.].
2. Independent Set in Hypergraphs
The independent set problem in graphs poses the following question: given a graph, and a subset of vertices such that any two 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], the clique problem instead of its complement, the independent set problem). The independent set problem is relatively well understood and by the famous result of Håstad [Hås99], the lower and upper bounds of this problem are tight. Hypergraphs are a natural extension of graphs, where each edge is formed across a tuple of distinct vertices. For a graph, each tuple has a size, two. To the best of our knowledge, semi-random models on hypergraphs have not been studied so far. Studying classical problems like these on hypergraphs is naturally of theoretical as well as practical interest. We study the algorithmic problems studied in McKenzie et al. [MMT20] and develop algorithms for them in the case of hypergraphs.
Note: This is joint work with Anand Louis and Rameesh Paul. Both of these e-prints will be up on arXiv soon.
Speaker Bio: Yash Khanna is a third (and final) year M.Tech (Research) student in the Theory Group of CSA, IISc Bangalore. His research interests include Algorithms and Complexity. He previously graduated from BITS Pilani.
-----------------
Zoom meeting link : https://zoom.us/j/98132227553?pwd=K2cyQllKVjExdUhlRm0vc0ZHcEt0Zz09
