Blair Sullivan

A major hurdle in large-scale network analysis is that most optimization problems are computationally intractable (NP-hard) on general graphs. Fortunately, real-world networks are far from generic and exhibit many shared structures -- e.g., social networks have clusters/communities, road networks tend to be almost planar, and biological networks are often tree-like. Theoretically, this structure should enable the design of efficient algorithms using tools from parameterized complexity. However, these approaches have historically failed to translate to practice due to unrealistically strong structural assumptions and challenges in implementation. This project aims to help bridge this theory-practice gap using the cross-cutting technique of graph modification alongside a new structural parameter (twin-width). To help achieve broad societal impact, initial efforts will focus on designing algorithms for specific problems in robotics, scientific computing, and algorithmic fairness.