MSO transduction recovers the laminar tree from a laminar set system, resolving Courcelle's question and enabling MSO constructions for modular, split, and bi-join decompositions.
Makowsky, and Udi Rotics
6 Pith papers cite this work, alongside 788 external citations. Polarity classification is still indexing.
6
Pith papers citing it
788
external citations · OpenAlex
citation-role summary
other 1
citation-polarity summary
roles
other 1polarities
unclear 1representative citing papers
Establishes tight n^{Theta(k^{d-1})} runtime bounds for d-Clique Packing parameterized by clique-width under ETH for fixed d >= 3.
Full complexity classification for three b- and fall-coloring problems in H-free graphs plus a separation showing b-Chromatic Number can be NP-hard while Tight b-Chromatic Number is P-time solvable for some H.
Fair MSO1 problems are W[1]-hard parameterized by cluster vertex deletion in general, but admit FPT algorithms under a sufficient condition that includes fair feedback vertex set, vertex cover, dominating set, and odd cycle transversal.
The paper defines FO Cost-Value Decision for token-sliding discovery and proves FPT and W[1]-hardness results for Partial Vertex Cover Discovery across various graph classes.
The paper overviews universal obstructions as a unifying framework for graph parameters, surveys existing results across many parameters, and offers some unifying classification results.
citing papers explorer
-
The role of counting quantifiers in laminar set systems
MSO transduction recovers the laminar tree from a laminar set system, resolving Courcelle's question and enabling MSO constructions for modular, split, and bi-join decompositions.
-
Tight bounds for clique-packing parameterized by clique-width
Establishes tight n^{Theta(k^{d-1})} runtime bounds for d-Clique Packing parameterized by clique-width under ETH for fixed d >= 3.
-
Optimal b-Colourings and Fall Colourings in $H$-Free Graphs
Full complexity classification for three b- and fall-coloring problems in H-free graphs plus a separation showing b-Chromatic Number can be NP-hard while Tight b-Chromatic Number is P-time solvable for some H.
-
Fair Vertex Problems Parameterized by Cluster Vertex Deletion
Fair MSO1 problems are W[1]-hard parameterized by cluster vertex deletion in general, but admit FPT algorithms under a sufficient condition that includes fair feedback vertex set, vertex cover, dominating set, and odd cycle transversal.
-
FO Value Discovery and Partial Vertex Cover Discovery
The paper defines FO Cost-Value Decision for token-sliding discovery and proves FPT and W[1]-hardness results for Partial Vertex Cover Discovery across various graph classes.
-
An Overview of Universal Obstructions for Graph Parameters
The paper overviews universal obstructions as a unifying framework for graph parameters, surveys existing results across many parameters, and offers some unifying classification results.