NSF-BSF: Small: AF: Towards a Unified Theory of Spanners

Graphs are abstract objects that model entities, represented by vertices, and relationships between them, represented by edges. Graphs are found in numerous applications, such as the Internet, social networks, transportation networks, wireless and sensor networks, and they are often massive in size. Accordingly, coping with massive graphs is a pressing challenge of the current time.

A principled approach for dealing with massive graphs is to compress big input graphs into compact subgraphs, called spanners, that approximate all pairwise distances to within some user-defined error parameter. The compactness, coupled with distance-preserving properties, make spanners useful in various application domains, such as distributed computing, approximation algorithms, wireless network design, logistics and planning.

This project aims to develop new algorithms for constructing spanners that achieve optimal trade-offs between the most fundamental compactness measures and the distance error parameter. Along with the scientific goals, the investigator includes an education plan that takes advantage of the practical relevance of this project to attract and train graduate and undergraduate students with diverse backgrounds.

This project focuses on two directions. The first direction seeks to improve the state-of-the-art spanner constructions via a unified framework, applicable to a wide range of settings. Specifically, the investigator aims at identifying common technical and conceptual barriers arising in multiple settings and computational models, and developing general tools and techniques to address these barriers.

This will provide theoretical tools to connect and transfer results from one setting to another. The second direction focuses on achieving truly optimal tradeoffs between the distance error parameter and the most fundamental compactness measures, including the number of edges and/or total edge length, for various graph families. Moreover, as part of this research, the investigator is identifying graph families that share similar sets of structural properties, focusing on graph families that are important for practical applications, and then developing techniques that exploit such structural properties to provide better spanner constructions for these applications.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.