Proves fine-grained nearly ETH-tight bounds for Courcelle's theorem depending on treewidth t and the number of first-order and second-order variables in each quantifier alternation block of the MSO formula.
Optimal Dynamic Program for r-Domination Problems over Tree Decompositions , booktitle =
3 Pith papers cite this work. Polarity classification is still indexing.
3
Pith papers citing it
fields
cs.DS 3years
2026 3verdicts
UNVERDICTED 3representative citing papers
Improved (O(pw), Δ)-LDD for pathwidth-pw digraphs and O(tw log n) integrality gap for directed sparsest-cut LP on treewidth-tw graphs via refined quasipartition analysis.
Provides algorithms and complexity results for the δ-Dispersion and δ-Covering problems on bounded-treewidth graphs for integer, rational, and irrational distances.
citing papers explorer
-
Fine-Grained Bounds for Courcelle's Theorem
Proves fine-grained nearly ETH-tight bounds for Courcelle's theorem depending on treewidth t and the number of first-order and second-order variables in each quantifier alternation block of the MSO formula.
-
Directed Low Diameter Decomposition for Structured Digraphs
Improved (O(pw), Δ)-LDD for pathwidth-pw digraphs and O(tw log n) integrality gap for directed sparsest-cut LP on treewidth-tw graphs via refined quasipartition analysis.
-
Independence and Domination on Bounded-Treewidth Graphs: Integer, Rational, and Irrational Distances
Provides algorithms and complexity results for the δ-Dispersion and δ-Covering problems on bounded-treewidth graphs for integer, rational, and irrational distances.