Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classes
Petr A. Golovach, Giannos Stamoulis, Dimitrios M. Thilikos
Abstract
The disjoint paths logic, FOL+DP, is an extension of First-Order Logic (FOL) with the extra atomic predicate dpk(x1,y1,…, xk,yk), expressing the existence of internally vertex-disjoint paths between Xi and yi, for i ∈ 1,…, k. This logic can express a wide variety of problems that escape the expressibility potential of FOL. We prove that for every proper minor-closed graph class, model-checking for FOL+DP can be done in quadratic time. We also introduce an extension of FOL+DP, namely the scattered disjoint paths logic, FOL+SDP, where we further consider the atomic predicate s-sdpk(x1,y1,…,xk,yk), demanding that the disjoint paths are within distance bigger than some fixed value s. Using the same technique we prove that model-checking for FOL+SDP can be done in quadratic time on classes of graphs with bounded Euler genus. * The full version of the paper can be accessed at https://arxiv.org/abs/2211.01723
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
6 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Parameterizing the quantification of CMSO: model checking on minor-closed graph classes cites Model Checking Disjoint-Paths Logic on Topological-Minor-Free Graph Classes
- Model Checking Disjoint-Paths Logic on Topological-Minor-Free Graph Classes cites Parameterizing the quantification of CMSO: model checking on minor-closed graph classes
- Parameterizing the quantification of CMSO: model checking on minor-closed graph classes cites A complexity dichotomy for hitting connected minors on bounded treewidth graphs: the chair and the banner draw the boundary
- Parameterizing the quantification of CMSO: model checking on minor-closed graph classes cites Twin-width IV: ordered graphs and matrices
- Parameterizing the quantification of CMSO: model checking on minor-closed graph classes cites Twin-width I: tractable FO model checking
- Model Checking Disjoint-Paths Logic on Topological-Minor-Free Graph Classes cites A complexity dichotomy for hitting connected minors on bounded treewidth graphs: the chair and the banner draw the boundary
- Model Checking Disjoint-Paths Logic on Topological-Minor-Free Graph Classes cites Twin-width IV: ordered graphs and matrices
- Model Checking Disjoint-Paths Logic on Topological-Minor-Free Graph Classes cites Model Checking for Low Monodimensionality Fragments of CMSO on Topological-Minor-Free Graph Classes
- Model Checking for Low Monodimensionality Fragments of CMSO on Topological-Minor-Free Graph Classes cites Model Checking Disjoint-Paths Logic on Topological-Minor-Free Graph Classes
- Model Checking Disjoint-Paths Logic on Topological-Minor-Free Graph Classes cites Twin-width I: tractable FO model checking
- Twin-width II: small classes cites Twin-width I: tractable FO model checking
- Twin-width I: tractable FO model checking cites Twin-width II: small classes
- What Can Be Computed Locally Revisited: First-Order Logic on Sparse Graphs in Distributed Computing cites Twin-width I: tractable FO model checking
- Twin-width IV: ordered graphs and matrices cites Twin-width II: small classes
- Twin-width IV: ordered graphs and matrices cites Twin-width I: tractable FO model checking
- Twin-width I: tractable FO model checking cites Twin-width IV: ordered graphs and matrices
- Model Checking for Low Monodimensionality Fragments of CMSO on Topological-Minor-Free Graph Classes cites Parameterizing the quantification of CMSO: model checking on minor-closed graph classes
- Model Checking for Low Monodimensionality Fragments of CMSO on Topological-Minor-Free Graph Classes cites A complexity dichotomy for hitting connected minors on bounded treewidth graphs: the chair and the banner draw the boundary
- Model Checking for Low Monodimensionality Fragments of CMSO on Topological-Minor-Free Graph Classes cites Twin-width IV: ordered graphs and matrices
- Model Checking for Low Monodimensionality Fragments of CMSO on Topological-Minor-Free Graph Classes cites Twin-width I: tractable FO model checking
Cited by top-tier papers6
- Model Checking Disjoint-Paths Logic on Topological-Minor-Free Graph ClassesNicole Schirrmacher, Sebastian Siebertz, Giannos Stamoulis, Dimitrios M. Thilikos et al.LICS 2024 · 3 citations
- What Can Be Computed Locally Revisited: First-Order Logic on Sparse Graphs in Distributed ComputingLélia Blin, Fedor V. Fomin, Pierre Fraigniaud, Sylvain Gay et al.STOC 2026 · 2 citations
- Polynomial bounds for the Graph Minor Structure TheoremMaximilian Gorsky, Michal T. Seweryn, Sebastian WiederrechtFOCS 2025 · 1 citation
- Parameterizing the quantification of CMSO: model checking on minor-closed graph classesIgnasi Sau, Giannos Stamoulis, Dimitrios M. ThilikosSODA 2025
- Model Checking for Low Monodimensionality Fragments of CMSO on Topological-Minor-Free Graph ClassesIgnasi Sau, Nicole Schirrmacher, Sebastian Siebertz, Giannos Stamoulis et al.LICS 2026
Builds on18
- Twin-width I: tractable FO model checkingÉdouard Bonnet, Eun Jung Kim, Stéphan Thomassé, Rémi WatrigantFOCS 2020 · 82 citations
- Twin-width II: small classesÉdouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé et al.SODA 2021 · 61 citations
- Twin-width IV: ordered graphs and matricesÉdouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, Pierre Simon et al.STOC 2022 · 30 citations
- Rankwidth meets stabilityJaroslav Nesetril, Patrice Ossona de Mendez, Michal Pilipczuk, Roman Rabinovich et al.SODA 2021 · 23 citations
- A complexity dichotomy for hitting connected minors on bounded treewidth graphs: the chair and the banner draw the boundaryJulien Baste, Ignasi Sau, Dimitrios M. ThilikosSODA 2020 · 21 citations
Related papers
- Approximate Evaluation of First-Order Counting QueriesJan Dreier, Peter RossmanithSODA 2021 · 5 citations
- Elementary first-order model checking for sparse graphsJakub Gajarský, Michal Pilipczuk, Marek Sokolowski, Giannos Stamoulis et al.LICS 2024 · 2 citations
- A Logic-based Algorithmic Meta-Theorem for Treedepth: Single Exponential FPT Time and Polynomial SpaceBenjamin Bergougnoux, Vera Chekan, Giannos StamoulisSODA 2026
- Group Order LogicAnatole DahanLICS 2025
- A logic-based algorithmic meta-theorem for mim-widthBenjamin Bergougnoux, Jan Dreier, Lars JaffkeSODA 2023 · 9 citations
