A Study of Stability of Discrete Graph Optimization Problems

In my final year at IIT Madras, I worked with Prof. Raghavendra Rao, on stable instances of graph algorithms. Stability is promising since real-life graph datasets in many algorithms tend to occur with a certain degree of stability to perturbations, unlike worst-case graph instances. Thus, we conducted a comprehensive literature review of previous research on stability and then analyzed stable instances of Christofides’ algorithm for the Traveling Salesman Problem (TSP) under different stability conditions. We managed to identify improved approximation bounds for stable instances of the algorithm with 2 different definitions of stability. Later, we also covered approximation algorithms and conducted analyses of almost stable instances in random graphs for the vertex cover problem.