This working group will develop new theoretically grounded approaches to practical problems on graphs and networks using the arsenal of graph structure theory and algorithms (treewidth, minors, fixed-parameter tractability, approximation algorithms, etc.).

Our approach is to combine the expertise of a mix of junior and senior researchers from three disciplines: mathematics (graph theory), computer science (fixed-parameter and approximation algorithms), and applied network analysis (social networks, power grid, bioinformatics, etc.). During this research cluster, we will identify specific practically motivated problems, and tackle the key associated mathematical challenges, with a goal of ultimately encouraging broader adoption of graph-structure-based tools in the computational community. This goal is particularly important given the emergence of vast quantities of relational data (a.k.a. networks) and increased need for analysis via scalable algorithms.

We face several challenges in making graph structure techniques applicable to real-world network analysis. First, many of the algorithms currently involve incredibly large constants (e.g., in their dependence on an excluded minor), so a natural goal is to improve or replace the relevant components with more reasonable dependencies. Second, we do not know which real-world networks fall into one or more of the mathematical graph classes where structural techniques are applicable. This problem can be tackled mathematically, through generative models, or experimentally, raising several questions about how to test whether specific graphs belong to parametrically defined classes. This problem becomes even more interesting when one considers that real-world networks are generally noisy, which means that the observed graph may have extra edges that place it outside the desired class, even if the intrinsic network satisfies the necessary conditions. For graphs that are "nearly" within a tractable graph class, can we detect which parts need modification to apply the efficient algorithms, and bound the effect of these modifications on the computed solution? We are excited by the new theoretical challenges raised by these practical questions, as well as the potential for significantly impacting the computability of many quantities of interest on real-world graphs.