Creating Robust and Fair Graph Structures for Connectivity and Clustering
For researchers and practitioners in graph algorithms and data analysis, this work provides foundational advances in fault-tolerant reachability and fair clustering, though the results are incremental in nature.
This thesis addresses robustness to failures in directed graphs by constructing the first non-trivial dual fault-tolerant pairwise reachability preservers, achieving size O(n^{4/3}|P|^{1/3}). It also tackles fairness in clustering by developing approximation algorithms for fair consensus clustering and introducing closest fair clustering, with improved guarantees for fair correlation clustering and the first streaming algorithm for fair consensus clustering using logarithmic memory.
Graph algorithms are central to large-scale applications such as navigation systems, social networks, and data analysis platforms. This thesis studies two important challenges in such systems: robustness to failures and fairness in clustering outcomes. In the first part, we investigate fault-tolerant reachability preservers in directed graphs. We present the first non-trivial constructions of dual fault-tolerant pairwise reachability preservers that remain resilient to two edge or vertex failures, achieving a sparse construction of size $O(n^{4/3}|\mathcal{P}|^{1/3})$. In the second part, we study fair clustering algorithms that ensure balanced representation of protected groups. We develop approximation algorithms for fair consensus clustering and introduce the framework of closest fair clustering, establishing hardness results and efficient algorithms for multi-group settings. Building on this framework, we obtain improved guarantees for fair correlation clustering and design the first streaming algorithm for fair consensus clustering using only logarithmic memory. Together, these results contribute toward the design of graph algorithms that are both robust and socially responsible.