Parameterized Graph Algorithms and Their Role in Static Program Analysis

Parameterized complexity is a branch of complexity theory that allows us to analyze the relationship between an algorithm’s runtime and specific characteristics of its input, beyond its size. This enables the creation of algorithms that perform efficiently when the input displays certain properties, rather than having the complexity always be bounded by the worst-case scenario. In particular, classically hard graph problems may become tractable when the graph given as an input exhibits certain structural properties. Many graphs encountered in real-world applications possess some of these properties, which means we can develop exact algorithms that solve traditionally difficult problems efficiently in practice. One setting where this approach proves itself particularly useful is static analysis. Static analysis refers to program analysis done prior to program execution, with goals such as improving performance, minimizing memory usage, or detecting potential errors and vulnerabilities. Many graphs derived from program analysis, such as graphs representing the control of information, control of data, or function calls, exhibit exploitable properties such as low treewidth or low tree-depth. In this thesis, I show how to use parameterization to speed up static analyses. I introduce novel algorithms and present extensive experimental data that show this approach can significantly improve existing methods for analyzing programs.