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