Parameterized Graph Algorithms and Their Role in Static Program Analysis

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering


PhD Thesis Defence


Title: "Parameterized Graph Algorithms and Their Role in Static Program 
Analysis"

By

Miss Giovanna KOBUS CONRADO


Abstract:

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.


Date:                   Wednesday, 16 July 2025

Time:                   5:00pm - 7:00pm

Venue:                  Room 5501
                        Lifts 25/26

Chairman:               Prof. Jidong ZHAO (CIVL)

Committee Members:      Prof. Pedro SANDER (Supervisor)
                        Dr. Amir GOHARSHADY (Co-supervisor, Oxford)
                        Dr. Sunil ARYA
                        Dr. Lionel PARREAUX
                        Dr. Maximilian Alexander NITZSCHNER (MATH)
                        Prof. Jean-François Raskin (ULB)