Combinatorial Optimization Problems on Sparse Random Graphs

A significant portion of Discrete Mathematics and Theoretical Computer Science is dedicated to developing algorithms for efficiently solving Combinatorial Optimization Problems (COPs). Unfortunately, unless P equals NP, many important COPs, have hard instances that witness the inability of algorithms to solve these problems in polynomial time. To address the complexity of CPOs, researchers often turn to their average-case analysis. The underlying philosophy of average-case analysis is that real-world problem instances are generally not adversarial. That is, the deliberately crafted scenarios used to demonstrate that an algorithm can potentially be slow are rare. Therefore, the objective shifts from designing algorithms that efficiently solve every possible instance to creating ones that are effective for the most commonly encountered instances. In the context of graph theory, this translates to studying these problems in the realm of random graphs. The goal of this project is to investigate classical COPs on sparse random graphs, whose behavior is not sufficiently understood, offering insights into their behavior and potential solutions in more typical, real-world scenarios. COPs on sparse random graphs have also been studied in a diverse range of fields, including Probabilistic and Extremal Combinatorics, Random Graphs, Theoretical Computer Science, and Statistical Physics.