Graphs are mathematical objects that model many complex systems and have become a central element of algorithm design. However, traditional worst-case analysis often yields pessimistic complexity bounds that ignore the typical structure of real-world instances. This thesis studies average-case analysis for various algorithms solving combinatorial optimization problems on graphs. It also investigates the combinatorial structures underlying these problems. These insights lead to a better understanding of the limitations of existing algorithms and provide guidance for developing new algorithmic techniques.

Specifically, my research includes the following problems:

Community Detection on Stochastic Block Models (SBM).?Consider a graph in which each vertex belongs to a hidden community, and the probability of an edge between any pair of vertices depends solely on the community assignments of the two vertices. The goal is to recover the community partition from the observed graph. We show that a semidefinite programming (SDP) relaxation designed for exact recovery in symmetric SBMs cannot be directly extended to asymmetric SBMs, and we provide geometric intuition explaining this limitation.

Sum of Leaf Weights in the Minimum Spanning Tree.?Let G be a complete graph in which each edge weight is sampled independently from the Uniform(0,1) distribution, and let T be the minimum spanning tree of G. Define a?leaf edge?as an edge of T that is incident to a leaf of T. We establish tight bounds on the expected sum of the weights of all leaf edges, together with the concentration around it. These results substantially improve the state-of-the-art bounds for several variants of the minimum spanning tree problem, including the probabilistic minimum spanning tree (PMST).

Probabilistic Minimum Spanning Tree (PMST).?Given a graph in which each vertex is present independently with probability p, the goal is to find an?a priori?spanning tree T that minimizes the expected total length after deleting edges while preserving connectivity among the vertices that remain present. We establish new upper and lower bounds on the expected length of the optimal a priori spanning tree.