pith. sign in

arxiv: 2607.02033 · v1 · pith:7DPG6YASnew · submitted 2026-07-02 · 💻 cs.DS · cs.LO

Fine-Grained Bounds for Courcelle's Theorem

Daniel Lokshtanov , Fahad Panolan , Saket Saurabh , Jie Xue , Meirav Zehavi This is my paper

Pith reviewed 2026-07-03 04:06 UTC · model grok-4.3

classification 💻 cs.DS cs.LO
keywords Courcelle's theoremmonadic second-order logictreewidthfine-grained complexityExponential Time Hypothesisquantifier alternationsmodel checking
0
0 comments X

The pith

Courcelle's theorem admits a fine-grained algorithm whose dependence on quantifier structure nearly matches the ETH lower bound.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that model checking an MSO formula φ on a graph of treewidth at most t can be solved in time f(φ, t) · n where the function f tracks the number of first-order and second-order variables inside each quantifier alternation block of φ. This refines the classic Courcelle result, whose tower-of-exponentials height grows only with the number of alternations, and brings the upper bound close to the Frick-Grohe ETH lower bound that already rules out any improvement in tower height. A reader cares because the new dependence distinguishes formulas that have few variables per block from those that do not, giving a sharper prediction of when the algorithm is practical. The result therefore replaces a coarse classification by alternation depth with a more accurate accounting of variable load per block.

Core claim

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).

What carries the argument

Dynamic programming on a tree decomposition whose state is sized according to the counts of first-order and second-order variables appearing inside each quantifier alternation block of the input MSO formula.

If this is right

  • The height of the exponential tower remains linear in the number of alternation blocks, yet the size of each level is governed by the variable counts inside those blocks.
  • Formulas whose quantifier blocks contain only a constant number of variables admit algorithms whose dependence on t is singly exponential rather than doubly exponential.
  • Any future improvement that reduces the tower height for a fixed variable-count signature would contradict ETH.
  • The same refined parameterization immediately yields tighter bounds for every MSO-expressible problem previously handled by the coarse Courcelle statement.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same block-wise variable counting may let other logical meta-theorems on bounded-width graphs be sharpened in the same way.
  • Implementations of MSO solvers could monitor the variable counts of the input formula and switch to cheaper subroutines when blocks are small.
  • If the measure is preserved by standard reductions, the technique could be lifted to clique-width or other width parameters.

Load-bearing premise

The variable-count-per-block measure used to build the new algorithm is the same measure that appears in the Frick-Grohe ETH lower bound.

What would settle it

An explicit reduction from 3-SAT to an MSO formula on treewidth-t graphs in which the per-block variable counts do not produce the tower height predicted by the lower bound would falsify the claimed near-tightness.

Figures

Figures reproduced from arXiv: 2607.02033 by Daniel Lokshtanov, Fahad Panolan, Jie Xue, Meirav Zehavi, Saket Saurabh.

Figure 1
Figure 1. Figure 1: Dependency of the time complexity of our algorithms on various parameters. [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Illustration of construction of base tree [PITH_FULL_IMAGE:figures/full_fig_p015_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Subtree to replace the node t To satisfy the additional condition mentioned above, we create a formula ψset(W1, . . . Ws) such that ψset(W1, . . . Ws) is true if and only if the following is true. For any node a, let b1, . . . , bs be the binary representation of id(a). Then, the formula ψset(W1, . . . Ws) is true if and only if for any vertex a and j ′ ∈ [s], a ∈ Wj ′ only when bj ′ = 1. This formula is a… view at source ↗
Figure 4
Figure 4. Figure 4: Illustration of construction of tree T in Lemma 5.5 • R = {rt}. • EN = {f1, . . . , fm} • EP is the set of children of nodes in EN. • P is the union of the set of children of Ui over all i. That is, P = {Ci,j : i ∈ [α], j ∈ [ℓi ]}. • N = {vi,j,a : i ∈ [α], j ∈ [ℓi ], a ∈ Vi} • I = {idi,j,a : i ∈ [α], j ∈ [ℓi ], a ∈ Vi} • For each q ∈ [3], Qq = {ci,j,a : a is colored with q in the proper coloring ci,j of G[… view at source ↗
Figure 5
Figure 5. Figure 5: Subtree to replace the node t ϕid ≡ id(d) = id(d ′ ) ϕbit ≡ c ∈ 0 ⇔ c ′ ∈ 0 ϕvalid ≡ (con({d, c}, {a}) ∧ (con({d ′ , c′ }, {a ′ }) ∧ adj(a, z) ∧ adj(a ′ , y) The formula ϕvalid is true if and only if a and a ′ are children of z and y, respectively, d and c are children of a, and d ′ and c ′ are children of a ′ . The formula ϕbit is true if and only if they both encode the same bit. Clearly, the formula in … view at source ↗
Figure 6
Figure 6. Figure 6: Illustration of T and T ′ Notice that |ψ| = O(|ϕ|+k+s) = O(|ϕ|+k+t). Now we prove the correctness of the reduction. Suppose ϕ is satisfiable and let β be a satisfying assignment. Now we need an assignments to v1, . . . , vk and w1, . . . , ws such that ψ is true under the assignment. Let us assign aj to wj for all j ∈ [s]. For each i ∈ [k], let ui be the vertex in B such that the following holds. For each … view at source ↗
Figure 7
Figure 7. Figure 7: Graph Ti Tℓ+1 T2 Tℓ+1 T1 T2 Tℓ+1 [PITH_FULL_IMAGE:figures/full_fig_p072_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Illustration of T ′′ 72 [PITH_FULL_IMAGE:figures/full_fig_p072_8.png] view at source ↗
read the original 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 $\phi$, and determines whether $G$ satisfies $\phi$ in time $f(\phi,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 $\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 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 $\phi$ (specifically, the number of first order and second order variables in each quantifier alternation block).

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper claims to prove a fine-grained version of Courcelle's theorem for MSO model checking on graphs of treewidth t, with running time f(φ, t) · n where f depends on t and the precise quantifier structure of φ (specifically, the number of first-order and second-order variables in each alternation block), and shows these bounds are nearly tight under ETH via comparison to the Frick-Grohe lower bound.

Significance. If the central claim holds, the result would substantially refine the complexity landscape for Courcelle's theorem beyond the known tower-height dependence, giving a more precise and practically relevant parameterization. The explicit use of ETH for near-tightness is a positive feature, as is the focus on variable counts per block rather than just alternation depth.

major comments (2)
  1. [Lower-bounds section (adaptation of Frick-Grohe)] The load-bearing claim of near-ETH-tightness requires that the upper-bound parameterization (FO/SO variable counts per alternation block) aligns exactly with the instances produced by the Frick-Grohe reduction. The manuscript must contain an explicit argument (likely in the lower-bounds section) showing that the reduction can be adapted or instantiated to produce formulas with independently prescribed numbers of FO and SO variables in each block without weakening the ETH-hardness; the abstract provides no such detail and the full text must verify this alignment.
  2. [Upper-bound construction] Upper-bound construction (likely §4 or the main algorithmic section): the dynamic-programming or automata construction must be shown to achieve a dependence on the per-block variable counts that matches the lower bound up to sub-exponential factors in t; any looseness in how the block structure is encoded into the state space would undermine the fine-grained tightness claim.
minor comments (2)
  1. The abstract would benefit from a one-sentence statement of the main theorem (including the precise form of f(φ, t)) rather than a high-level description only.
  2. [Preliminaries] Notation for the quantifier-block measure (number of FO vs. SO variables) should be introduced with a formal definition early in the preliminaries to avoid ambiguity when comparing upper and lower bounds.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful and constructive report. The comments help clarify the presentation of our fine-grained bounds. We address each major comment below.

read point-by-point responses

  1. Referee: [Lower-bounds section (adaptation of Frick-Grohe)] The load-bearing claim of near-ETH-tightness requires that the upper-bound parameterization (FO/SO variable counts per alternation block) aligns exactly with the instances produced by the Frick-Grohe reduction. The manuscript must contain an explicit argument (likely in the lower-bounds section) showing that the reduction can be adapted or instantiated to produce formulas with independently prescribed numbers of FO and SO variables in each block without weakening the ETH-hardness; the abstract provides no such detail and the full text must verify this alignment.

    Authors: We agree that an explicit alignment argument strengthens the lower-bound section. In Section 5 we adapt the Frick-Grohe construction by building each quantifier block from independent sets of first-order variables (for vertex selection) and second-order variables (for edge-set quantification) whose cardinalities are chosen freely while preserving the linear-size formula and the ETH reduction from 3-SAT. The number of alternations remains unchanged, so the hardness carries over directly. We will insert a short dedicated paragraph (and a small diagram) in the revised Section 5 that states this independence explicitly. revision: yes

  2. Referee: [Upper-bound construction] Upper-bound construction (likely §4 or the main algorithmic section): the dynamic-programming or automata construction must be shown to achieve a dependence on the per-block variable counts that matches the lower bound up to sub-exponential factors in t; any looseness in how the block structure is encoded into the state space would undermine the fine-grained tightness claim.

    Authors: Section 4 presents a dynamic-programming algorithm on tree decompositions whose state at each bag is the set of all possible assignments to the first-order and second-order variables appearing in the current quantifier block. The state-space size is therefore bounded by a function whose dominant term is determined exactly by the per-block variable counts (roughly 2^{O(v_{FO} + v_{SO})} per bag, with the tower height governed by the number of blocks). This yields a running time whose dependence on t and the block-wise variable numbers matches the ETH lower bound up to factors of the form 2^{o(t)} (arising from standard treewidth techniques such as nice decompositions). The block structure is processed sequentially, so no extra exponential factors in t are introduced. We will add a short lemma in the revised Section 4 that isolates this state-size calculation to make the matching explicit. revision: yes

Circularity Check

0 steps flagged

No circularity; upper bound and ETH comparison are independent

full rationale

The paper derives a new fine-grained upper bound for Courcelle's theorem, parameterized by treewidth t and the per-block counts of FO/SO variables in the MSO formula φ. The claimed near-ETH-tightness is obtained by direct comparison to the external Frick-Grohe lower bound (different authors), which is invoked only as an existing result rather than re-derived or fitted inside the paper. No equation reduces the claimed f(φ,t) to a self-defined quantity, no prediction is obtained by fitting a subset of the target data, and no load-bearing step relies on a self-citation chain. The derivation is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Based solely on the abstract, the only external assumption invoked for tightness is ETH; no free parameters or invented entities are mentioned.

axioms (1)
  • domain assumption Exponential Time Hypothesis (ETH)
    Invoked to establish that the linear dependence of tower height on quantifier alternations is unavoidable, and to claim near-tightness of the new bounds.

pith-pipeline@v0.9.1-grok · 5752 in / 1197 out tokens · 36548 ms · 2026-07-03T04:06:31.771819+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

81 extracted references · 20 canonical work pages

  1. [1]

    Borie and R

    Richard B. Borie and R. Gary Parker and Craig A. Tovey , title =. Algorithmica , volume =. 1992 , url =. doi:10.1007/BF01758777 , timestamp =

    work page doi:10.1007/bf01758777 1992

  2. [2]

    Elementary first-order model checking for sparse graphs , year =

    Gajarsk\'. Elementary first-order model checking for sparse graphs , year =. Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science , articleno =. doi:10.1145/3661814.3662094 , abstract =

    work page doi:10.1145/3661814.3662094

  3. [3]

    Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=

    Beating brute force for (quantified) satisfiability of circuits of bounded treewidth , author=. Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2018 , organization=

    2018

  4. [4]

    Optimal Dynamic Program for r-Domination Problems over Tree Decompositions , booktitle =

    Glencora Borradaile and Hung Le , editor =. Optimal Dynamic Program for r-Domination Problems over Tree Decompositions , booktitle =. 2016 , url =. doi:10.4230/LIPICS.IPEC.2016.8 , timestamp =

    work page doi:10.4230/lipics.ipec.2016.8 2016

  5. [5]

    Doklady Akademii Nauk SSSR , volume=

    The impossibility of an algorithm for the decision problem for finite domains (Russian) , author=. Doklady Akademii Nauk SSSR , volume=

  6. [6]

    SIAM Journal on Computing , volume=

    A c^k n 5-approximation algorithm for treewidth , author=. SIAM Journal on Computing , volume=. 2016 , publisher=

    2016

  7. [7]

    SIAM Journal on Computing , number=

    A single-exponential time 2-approximation algorithm for treewidth , author=. SIAM Journal on Computing , number=. 2023 , publisher=

    2023

  8. [8]

    ACM Transactions on Algorithms (TALG) , volume=

    Fully polynomial-time parameterized computations for graphs and matrices of low treewidth , author=. ACM Transactions on Algorithms (TALG) , volume=. 2018 , publisher=

    2018

  9. [9]

    50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) , volume=

    First Order Logic on Pathwidth Revisited Again , author=. 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) , volume=. 2023 , organization=

    2023

  10. [10]

    Electronic Notes in Theoretical Computer Science , volume=

    A practical approach to Courcelle's theorem , author=. Electronic Notes in Theoretical Computer Science , volume=. 2009 , publisher=

    2009

  11. [11]

    Annals of pure and applied logic , volume=

    The complexity of first-order and monadic second-order logic revisited , author=. Annals of pure and applied logic , volume=. 2004 , publisher=

    2004

  12. [12]

    The monadic second-order logic of graphs. I. Recognizable sets of finite graphs , author=. Information and computation , volume=. 1990 , publisher=

    1990

  13. [13]

    Information Processing Letters , volume=

    Optimal time bounds for some proximity problems in the plane , author=. Information Processing Letters , volume=. 1992 , publisher=

    1992

  14. [14]

    , author=

    On the relative complexities of some geometric problems. , author=. Proceedings of the 7th Canadian Conference on Computational Geometry (CCCG) , volume=

  15. [15]

    A near linear time constant factor approximation for

    Indyk, Piotr , booktitle=. A near linear time constant factor approximation for. 2007 , organization=

    2007

  16. [16]

    March, William B and Ram, Parikshit and Gray, Alexander G , booktitle=. Fast

  17. [17]

    Truly optimal

    Le, Hung and Solomon, Shay , journal=. Truly optimal. 2022 , publisher=

    2022

  18. [18]

    Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    Euclidean spanners in high dimensions , author=. Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2013 , organization=

    2013

  19. [19]

    Proceedings of the 27th Annual ACM Symposium on Theory of Computing (STOC) , pages=

    Euclidean spanners: short, thin, and lanky , author=. Proceedings of the 27th Annual ACM Symposium on Theory of Computing (STOC) , pages=

  20. [20]

    de Berg, Mark and Bodlaender, Hans L and Kisfaludi-Bak, S. An. Proceedings of the 59th Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2018 , organization=

    2018

  21. [21]

    Nearly linear time approximation schemes for

    Arora, Sanjeev , booktitle=. Nearly linear time approximation schemes for. 1997 , organization=

    1997

  22. [22]

    Polynomial time approximation schemes for

    Arora, Sanjeev , booktitle=. Polynomial time approximation schemes for. 1996 , organization=

    1996

  23. [23]

    Proceedings of the 35th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    Euclidean Bottleneck Steiner Tree is Fixed-Parameter Tractable , author=. Proceedings of the 35th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2024 , organization=

    2024

  24. [24]

    How to find Steiner minimal trees in

    Smith, Warren D , journal=. How to find Steiner minimal trees in. 1992 , publisher=

    1992

  25. [25]

    On the history of the

    Brazil, Marcus and Graham, Ronald L and Thomas, Doreen A and Zachariasen, Martin , journal=. On the history of the. 2014 , publisher=

    2014

  26. [26]

    16th Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    Closest-point problems , author=. 16th Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 1975 , organization=

    1975

  27. [27]

    Discrete & Computational Geometry , volume=

    Euclidean minimum spanning trees and bichromatic closest pairs , author=. Discrete & Computational Geometry , volume=. 1991 , publisher=

    1991

  28. [28]

    Vaidya, Pravin M , journal=. An. 1989 , publisher=

    1989

  29. [29]

    SIAM Journal on Applied Mathematics , volume=

    Minimum covers of fixed cardinality in weighted graphs , author=. SIAM Journal on Applied Mathematics , volume=. 1971 , publisher=

    1971

  30. [30]

    Proceedings of the American Mathematical Society , volume=

    An algorithm for a minimum cover of a graph , author=. Proceedings of the American Mathematical Society , volume=

  31. [31]

    2019 , school=

    A 4/3-approximation for Minimum Weight Edge Cover , author=. 2019 , school=

    2019

  32. [32]

    Applied mathematical modelling , volume=

    Fuzzy minimum weight edge covering problem , author=. Applied mathematical modelling , volume=. 2008 , publisher=

    2008

  33. [33]

    Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC) , pages=

    Deterministic, near-linear -approximation algorithm for geometric bipartite matching , author=. Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC) , pages=

  34. [34]

    Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    A divide-and-conquer algorithm for min-cost perfect matching in the plane , author=. Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 1998 , organization=

    1998

  35. [35]

    SIAM Journal on Computing , volume=

    On locality-sensitive orderings and their applications , author=. SIAM Journal on Computing , volume=. 2020 , publisher=

    2020

  36. [36]

    Discrete & Computational Geometry , volume=

    Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications , author=. Discrete & Computational Geometry , volume=. 2020 , publisher=

    2020

  37. [37]

    Journal of the ACM , volume=

    Fibonacci heaps and their uses in improved network optimization algorithms , author=. Journal of the ACM , volume=. 1987 , publisher=

    1987

  38. [38]

    Proceedings of the XI Encuentros de Geometria Computacional , pages=

    Faster algorithms for computing distances between one-dimensional point sets , author=. Proceedings of the XI Encuentros de Geometria Computacional , pages=. 2005 , publisher=

    2005

  39. [39]

    32nd International Symposium on Algorithms and Computation (ISAAC) , year=

    Exact and Approximation Algorithms for Many-To-Many Point Matching in the Plane , author=. 32nd International Symposium on Algorithms and Computation (ISAAC) , year=

  40. [40]

    Semantic web , volume=

    A machine learning approach for product matching and categorization , author=. Semantic web , volume=. 2018 , publisher=

    2018

  41. [41]

    Applied Intelligence , volume=

    Data mining-based approach for ontology matching problem , author=. Applied Intelligence , volume=. 2020 , publisher=

    2020

  42. [42]

    Japanese Conference on Discrete and Computational Geometry , pages=

    The geometry of musical rhythm , author=. Japanese Conference on Discrete and Computational Geometry , pages=. 2004 , organization=

    2004

  43. [43]

    , author=

    A Comparison of Rhythmic Similarity Measures. , author=. ISMIR , year=

  44. [44]

    Journal of Combinatorial Theory, Series B , volume=

    An efficient algorithm for minimum-weight bibranching , author=. Journal of Combinatorial Theory, Series B , volume=. 1998 , publisher=

    1998

  45. [45]

    Mudabir Kabir Asathulla and Sanjeev Khanna and Nathaniel Lahn and Sharath Raghvendra , title =

  46. [46]

    Agarwal , title =

    Sharath Raghvendra and Pankaj K. Agarwal , title =. Journal of the ACM , volume =

  47. [47]

    arXiv preprint arXiv:1904.05184 , year=

    A fast and efficient algorithm for many-to-many matching of points with demands in one dimension , author=. arXiv preprint arXiv:1904.05184 , year=

    work page arXiv 1904

  48. [48]

    arXiv preprint arXiv:1904.03015 , year=

    A faster algorithm for the limited-capacity many-to-many point matching in one dimension , author=. arXiv preprint arXiv:1904.03015 , year=

    work page arXiv 1904

  49. [49]

    Fatemeh Rajabi. An. Algorithmica , volume =

  50. [50]

    S. M. Ferdous and Alex Pothen and Arif Khan , editor =. New Approximation Algorithms for Minimum Weighted Edge Cover , booktitle =

  51. [51]

    Souvaine and Godfried Toussaint , title =

    Justin Colannino and Mirela Damian and Ferran Hurtado and Stefan Langerman and Henk Meijer and Suneeta Ramaswami and Diane L. Souvaine and Godfried Toussaint , title =. Graphs and Combinatorics , volume =

  52. [52]

    Acta informatica , volume=

    Distance measures for point sets and their computation , author=. Acta informatica , volume=. 1997 , publisher=

    1997

  53. [53]

    SIAM Journal on Computing , volume=

    Geometry helps in matching , author=. SIAM Journal on Computing , volume=. 1989 , publisher=

    1989

  54. [54]

    Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , organization=

    Approximation Algorithms for Bipartite and Non-Bipartite Matching in the Plane , author=. Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , organization=

  55. [55]

    Variants of the

    Kuhn, Harold W , journal=. Variants of the. 1956 , publisher=

    1956

  56. [56]

    SIAM Journal on Computing , volume=

    Faster scaling algorithms for network problems , author=. SIAM Journal on Computing , volume=. 1989 , publisher=

    1989

  57. [57]

    Hopcroft, John E and Karp, Richard M , journal=. An n^. 1973 , publisher=

    1973

  58. [58]

    Proceedings of the 6th Annual International Conference on Computational Biology , pages=

    The restriction scaffold problem , author=. Proceedings of the 6th Annual International Conference on Computational Biology , pages=

  59. [59]

    Mathematical Programming , volume=

    Vertex packings: structural properties and algorithms , author=. Mathematical Programming , volume=. 1975 , publisher=

    1975

  60. [60]

    Greedy Spanners in

    Le, Hung and Than, Cuong , booktitle=. Greedy Spanners in. 2022 , organization=

    2022

  61. [61]

    Fomin and Lukasz Kowalik and Daniel Lokshtanov and D

    Marek Cygan and Fedor V. Fomin and Lukasz Kowalik and Daniel Lokshtanov and D. Parameterized Algorithms , publisher =

  62. [62]

    Approximation algorithms for

    Baker, Brenda S , journal=. Approximation algorithms for. 1994 , publisher=

    1994

  63. [63]

    Theoretical Computer Science , volume=

    Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization , author=. Theoretical Computer Science , volume=. 2014 , publisher=

    2014

  64. [64]

    Hitting minors on bounded treewidth graphs. I. General upper bounds , author=. SIAM Journal on Discrete Mathematics , volume=. 2020 , publisher=

    2020

  65. [65]

    2012 IEEE 53rd Annual Symposium on Foundations of Computer Science , pages=

    Planar F-deletion: Approximation, kernelization and optimal FPT algorithms , author=. 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science , pages=. 2012 , organization=

    2012

  66. [66]

    Slightly Superexponential Parameterized Problems , journal =

    Daniel Lokshtanov and D. Slightly Superexponential Parameterized Problems , journal =. 2018 , url =. doi:10.1137/16M1104834 , timestamp =

    work page doi:10.1137/16m1104834 2018

  67. [67]

    Known Algorithms on Graphs of Bounded Treewidth Are Probably Optimal , journal =

    Daniel Lokshtanov and D. Known Algorithms on Graphs of Bounded Treewidth Are Probably Optimal , journal =. 2018 , url =. doi:10.1145/3170442 , timestamp =

    work page doi:10.1145/3170442 2018

  68. [68]

    Hartmann and D

    Tim A. Hartmann and D. Independence and Domination on Bounded-Treewidth Graphs: Integer, Rational, and Irrational Distances , booktitle =. 2025 , url =. doi:10.4230/LIPICS.STACS.2025.44 , timestamp =

    work page doi:10.4230/lipics.stacs.2025.44 2025

  69. [69]

    Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness , booktitle =

    Baris Can Esmer and Jacob Focke and D. Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness , booktitle =. 2024 , url =. doi:10.4230/LIPICS.ICALP.2024.34 , timestamp =

    work page doi:10.4230/lipics.icalp.2024.34 2024

  70. [70]

    Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs , booktitle =

    Jacob Focke and D. Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs , booktitle =. 2023 , url =. doi:10.1137/1.9781611977554.CH140 , timestamp =

    work page doi:10.1137/1.9781611977554.ch140 2023

  71. [71]

    Marek Cygan and Jesper Nederlof and Marcin Pilipczuk and Michal Pilipczuk and Johan M. M. van Rooij and Jakub Onufry Wojtaszczyk , title =. 2022 , url =. doi:10.1145/3506707 , timestamp =

    work page doi:10.1145/3506707 2022

  72. [72]

    Problems Parameterized by Treewidth Tractable in Single Exponential Time:

    Michal Pilipczuk , editor =. Problems Parameterized by Treewidth Tractable in Single Exponential Time:. Mathematical Foundations of Computer Science 2011 - 36th International Symposium,. 2011 , url =. doi:10.1007/978-3-642-22993-0\_47 , timestamp =

    work page doi:10.1007/978-3-642-22993-0 2011

  73. [73]

    Algorithmica , volume =

    Michael Lampis , title =. Algorithmica , volume =. 2012 , url =. doi:10.1007/S00453-011-9554-X , timestamp =

    work page doi:10.1007/s00453-011-9554-x 2012

  74. [74]

    Michael Lampis , title =. Log. Methods Comput. Sci. , volume =. 2014 , url =. doi:10.2168/LMCS-10(1:18)2014 , timestamp =

    work page doi:10.2168/lmcs-10(1:18)2014 2014

  75. [75]

    First Order Logic on Pathwidth Revisited Again , booktitle =

    Michael Lampis , editor =. First Order Logic on Pathwidth Revisited Again , booktitle =. 2023 , url =. doi:10.4230/LIPICS.ICALP.2023.132 , timestamp =

    work page doi:10.4230/lipics.icalp.2023.132 2023

  76. [76]

    Kernelizing

    Jakub Gajarsk. Kernelizing. Log. Methods Comput. Sci. , volume =. 2015 , url =. doi:10.2168/LMCS-11(1:19)2015 , timestamp =

    work page doi:10.2168/lmcs-11(1:19)2015 2015

  77. [77]

    Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics , booktitle =

    Robert Ganian , editor =. Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics , booktitle =. 2011 , url =. doi:10.1007/978-3-642-28050-4\_21 , timestamp =

    work page doi:10.1007/978-3-642-28050-4 2011

  78. [78]

    to appear in SODA 2026 , eprint=

    A Logic-based Algorithmic Meta-Theorem for Treedepth: Single Exponential FPT Time and Polynomial Space , author=. to appear in SODA 2026 , eprint=

    2026

  79. [79]

    On the Parameterised Intractability of Monadic Second-Order Logic , booktitle =

    Stephan Kreutzer , editor =. On the Parameterised Intractability of Monadic Second-Order Logic , booktitle =. 2009 , url =. doi:10.1007/978-3-642-04027-6\_26 , timestamp =

    work page doi:10.1007/978-3-642-04027-6 2009

  80. [80]

    Proceedings of the 25th Annual

    Stephan Kreutzer and Siamak Tazari , title =. Proceedings of the 25th Annual. 2010 , url =. doi:10.1109/LICS.2010.39 , timestamp =

    work page doi:10.1109/lics.2010.39 2010

Showing first 80 references.