Fine-Grained Bounds for Courcelle's Theorem

26^th May 2026, 13:00
Fahad Panolan
University of Leeds

Abstract

Courcelle's theorem states that there exists an algorithm that takes as input an n-vertex graph G of treewidth at most t and an MSO formula phi, and determines whether G satisfies phi f(phi,t) n. It is folklore that the function f contains a tower of exponentials whose height depends as a linear function of the number of quantifier alternations of the input formula phi. A classic reduction of Frick and Grohe shows that, assuming the Exponential Time Hypothesis (ETH), the linear growth of the height of the tower is unavoidable. Nevertheless, there is still a huge gap between existing upper and lower bounds -- after all, there is quite a difference between a single exponential and a double exponential running time. In this talk, we discuss a fine-grained version of Courcelle's theorem with nearly ETH-tight dependence on the treewidth t and the quantifier structure of MSO formula phi.

This is joint work with Daniel Lokshtanov (University of California Santa Barbara) , Saket Saurabh (Institute of Mathematical Sciences), Jie Xue (New York University Shanghai), and Meirav Zehavi (Ben-Gurion University).

Biography

Fahad Panolan is a lecturer at the School of Computer Science, University of Leeds. His research interest is theoretical computer science with a specialisation in parameterised algorithms and complexity. Before joining the University of Leeds, he was an assistant professor at the Indian Institute of Technology Hyderabad. He completed PhD from The Instititute of Mathematical Science, Chennai, in 2015.