12 papers
Model Checking for Low Monodimensionality Fragments of CMSO on Topological-Minor-Free Graph Classes
Ignasi Sau, Nicole Schirrmacher, Sebastian Siebertz +3
Algorithmic meta-theorems explain the tractability of large classes of computational problems by linking logical expressibility with structural graph properties. While extensions o…
Finding irrelevant vertices in linear time on bounded-genus graphs
Petr A. Golovach, Stavros G. Kolliopoulos, Giannos Stamoulis +1
The irrelevant vertex technique provides a powerful tool for the design of parameterized algorithms for a wide variety of problems on graphs. A common characteristic of these probl…
Model Checking Disjoint-Paths Logic on Topological-Minor-Free Graph Classes
Nicole Schirrmacher, Sebastian Siebertz, Giannos Stamoulis +2
Disjoint-paths logic, denoted +, extends first-order logic () with atomic predicates , expressing…
Catching Rats in -minor-free Graphs
Maximilian Gorsky, Giannos Stamoulis, Dimitrios M. Thilikos +1
We show that every -minor-free graph that also excludes a -grid as a minor has treewidth/branchwidth bounded from above by a function that is linear in $k…
A Logic-based Algorithmic Meta-Theorem for Treedepth: Single Exponential FPT Time and Polynomial Space
Benjamin Bergougnoux, Vera Chekan, Giannos Stamoulis
For a graph , the parameter treedepth measures the minimum depth among all forests , called elimination forests, such that is a subgraph of the ancestor-descendant closur…
Elementary first-order model checking for sparse graphs
Jakub Gajarský, MichaÅ Pilipczuk, Marek SokoÅowski +2
It is known that for subgraph-closed graph classes the first-order model checking problem is fixed-parameter tractable if and only if the class is nowhere dense [Grohe, Kreutzer, S…