Title: Optimal Hardness of Online Algorithms for Large Common Induced Subgraphs
Abstract: I will discuss the problem of efficiently finding large common induced subgraphs of two independent Erdős--Rényi random graphs $G_1, G_2 \sim G(n,1/2)$. I will show a simple greedy algorithm that obtains a solution that has size half of the optimum. I will then show that no online algorithm can find solutions larger than half-optimal with probability bounded away from 0. Together, these results provide evidence that this problem exhibits a computation-to-optimization gap. This is based on joint work with David Gamarnik and Gabe Schoenbach.
Reza Gheissari
Email