{"ID":5675310,"CreatedAt":"2026-07-03T01:40:09.565152011Z","UpdatedAt":"2026-07-07T01:06:03.009715918Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.02033","arxiv_id":"2607.02033","title":"Fine-Grained Bounds for Courcelle's Theorem","abstract":"Courcelle's theorem states that there exists an algorithm that takes as input a graph $G$ of treewidth at most $t$ and a MSO formula $φ$, and determines whether $G$ satisfies $φ$ in time $f(φ,t) \\cdot n$. It is folklore that the 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 $φ$. 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 addition, this only gives us a very coarse understanding in the time complexity of Courcelle's theorem. In this paper, we prove a fine-grained version of Courcelle's theorem with nearly ETH-tight dependence on the treewidth parameter $t$ and the quantifier structure of $φ$ (specifically, the number of first order and second order variables in each quantifier alternation block).","short_abstract":"Courcelle's theorem states that there exists an algorithm that takes as input a graph $G$ of treewidth at most $t$ and a MSO formula $φ$, and determines whether $G$ satisfies $φ$ in time $f(φ,t) \\cdot n$. It is folklore that the the function $f$ contains a tower of exponentials whose height depends as a linear function...","url_abs":"https://arxiv.org/abs/2607.02033","url_pdf":"https://arxiv.org/pdf/2607.02033v1","authors":"[\"Daniel Lokshtanov\",\"Fahad Panolan\",\"Saket Saurabh\",\"Jie Xue\",\"Meirav Zehavi\"]","published":"2026-07-02T11:00:35Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.LO\"]","methods":"[]","has_code":false}