Deciding first-order properties of locally tree-decomposable structures
From MaRDI portal
first-order logiclocalitymodel checkingparameterized complexityplanar graphsquery evaluationtree-width
Decidability of theories and sets of sentences (03B25) Basic properties of first-order languages and structures (03C07) Trees (05C05) Structural characterization of families of graphs (05C75) Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60)
Abstract: We introduce the concept of a class of graphs, or more generally, relational structures, being locally tree-decomposable. There are numerous examples of locally tree-decomposable classes, among them the class of planar graphs and all classes of bounded valence or of bounded tree-width. We also consider a slightly more general concept of a class of structures having bounded local tree-width. We show that for each property P of structures that is definable in first-order logic and for each locally tree-decomposable class C of graphs, there is a linear time algorithm deciding whether a given structure A in C has property P. For classes C of bounded local tree-width, we show that for every kge 1 there is an algorithm that solves the same problem in time O(n^{1+(1/k)}) (where n is the cardinality of the input structure).
Recommendations
Cited in
(76)- Characterising bounded expansion by neighbourhood complexity
- FO model checking on geometric graphs
- A gentle introduction to applications of algorithmic metatheorems for space and circuit classes
- Algorithmic meta-theorems for restrictions of treewidth
- Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
- The complexity of first-order and monadic second-order logic revisited
- An existential locality theorem
- Fixed-parameter tractable distances to sparse graph classes
- Local 2-separators
- A basic parameterized complexity primer
- FPT Suspects and Tough Customers: Open Problems of Downey and Fellows
- Large Induced Subgraphs via Triangulations and CMSO
- On the complexity of connection games
- Efficient First-Order Model-Checking Using Short Labels
- Computing thejth solution of a first-order query
- The Parameterized Complexity of k-Flip Local Search for SAT and MAX SAT
- On the Parameterised Intractability of Monadic Second-Order Logic
- Locally finite properties of data structures and their computation
- Parameterized complexity of finding small degree-constrained subgraphs
- Editing graphs to satisfy degree constraints: a parameterized approach
- Model-checking hierarchical structures
- An optimal construction of Hanf sentences
- scientific article; zbMATH DE number 1231505 (Why is no real title available?)
- The parameterized complexity of \(k\)-flip local search for SAT and MAX SAT
- Faster decision of first-order graph properties
- Practical algorithms for MSO model-checking on tree-decomposable graphs
- scientific article; zbMATH DE number 2086422 (Why is no real title available?)
- scientific article; zbMATH DE number 1405654 (Why is no real title available?)
- First-order interpretations of bounded expansion classes
- Gaifman normal forms for counting extensions of first-order logic
- Reducing CMSO model checking to highly connected graphs
- Recovering sparse graphs
- A Retrospective on (Meta) Kernelization
- An Experimental Study of the Treewidth of Real-World Graph Data
- FO model checking of geometric graphs
- Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions)
- Graph editing problems with extended regularity constraints
- scientific article; zbMATH DE number 969067 (Why is no real title available?)
- Junction Tree Factored Particle Inference Algorithm for Multi-Agent Dynamic Influence Diagrams
- Testing first-order properties for subclasses of sparse graphs
- Uniform Constraint Satisfaction Problems and Database Theory
- Parameterized Graph Editing with Chosen Vertex Degrees
- First-Order Model-Checking in Random Graphs and Complex Networks
- An algorithmic meta-theorem for graph modification to planarity and FOL
- Enumeration for FO Queries over Nowhere Dense Graphs
- Finding large degree-anonymous subgraphs is hard
- Lacon-, Shrub- and Parity-Decompositions: Characterizing Transductions of Bounded Expansion Classes
- Parameterized Counting and Cayley Graph Expanders
- A survey of parameterized algorithms and the complexity of edge modification
- Compact labelings for efficient first-order model-checking
- Dominating set is fixed parameter tractable in claw-free graphs
- Model checking on interpretations of classes of bounded local cliquewidth
- Complexity of maker-breaker games on edge sets of graphs
- Solving a family of multivariate optimization and decision problems on classes of bounded expansion
- Model checking disjoint-paths logic on topological-minor-free graph classes
- An algorithmic meta-theorem for graph modification to planarity and FOL
- Compound logics for modification problems
- Twin-width. IV: Ordered graphs and matrices
- Fine-grained meta-theorems for vertex integrity
- Generalized model-checking over locally tree-decomposable classes
- \(\mathcal{H}\)-clique-width and a hereditary analogue of product structure
- Twin-width of graphs on surfaces
- Advances in algorithmic meta theorems (invited paper)
- The parameterized complexity of k-edge induced subgraphs
- First order logic on pathwidth revisited again
- Solving partial dominating set and related problems using twin-width
- On the treewidth of dynamic graphs
- Faster approximation schemes and parameterized algorithms on (odd-)H-minor-free graphs
- On finding short resolution refutations and small unsatisfiable subsets
- Quickly deciding minor-closed parameters in general graphs
- Polynomial time approximation schemes and parameterized complexity
- Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth
- Linearity of grid minors in treewidth with applications through bidimensionality
- On the fixed-parameter tractability of parameterized model-checking problems
- Homomorphism preservation on quasi-wide classes
- The parameterized complexity of editing graphs for bounded degeneracy
This page was built for publication: Deciding first-order properties of locally tree-decomposable structures
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3196630)
