Twin-width. I: Tractable FO model checking

DOI10.1145/3486655MaRDI QIDQ5066940zbMATH OpenOpenAlexWikidataFDO

Authors Édouard Bonnet, Eun Jung Kim, Rémi Watrigant, Stéphan Thomassé

Publication date 31 March 2022

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2004.14789

zbMATH Keywords

fixed-parameter tractabilitycontraction sequenceFO model checking

Mathematics Subject Classification ID

Computer science (68-XX)

Recommendations

• Twin-width II: small classes
• Twin-width can be exponential in treewidth
• Tree-Width for First Order Formulae
• Tree-width for first order formulae
• Faster existential FO model checking on posets

Cited in

(44)

• Grouped domination parameterized by vertex cover, twin cover, and beyond
• Bounds on the Twin-Width of Product Graphs
• On the thinness of trees
• Lacon-, Shrub- and Parity-Decompositions: Characterizing Transductions of Bounded Expansion Classes
• Functionality of box intersection graphs
• Treewidth versus clique number. II: Tree-independence number
• Parity permutation pattern matching
• Graphs of bounded twin-width are quasi-polynomially \(\chi \)-bounded
• Twin-width can be exponential in treewidth
• Twin-width and transductions of proper \(k\)-mixed-thin graphs
• Hypergraphs with polynomial representation: introducing \(r\)-splits
• Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs
• Twin-width. II: Small classes
• Grouped domination parameterized by vertex cover, twin cover, and beyond
• Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs
• Parity permutation pattern matching
• On \(( n , m )\)-chromatic numbers of graphs with bounded sparsity parameters
• Transducing paths in graph classes with unbounded shrubdepth
• Planar graph with twin-width seven
• Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs
• Mini-workshop: Permutation patterns. Abstracts from the mini-workshop held January 28 -- February 2, 2024
• Edge-cut width: an algorithmically driven analogue of treewidth based on edge cuts
• Stack-number is not bounded by queue-number
• \(\boldsymbol{(\alpha, \beta )}\)-Modules in Graphs
• Counting subgraphs in somewhere dense graphs
• Neighbourhood complexity of graphs of bounded twin-width
• Twin-width. III: Max independent set, min dominating set, and coloring
• Twin-width of random graphs
• Stable graphs of bounded twin-width
• The splitting power of branching programs of bounded repetition and CNFs of bounded width
• Treelike decompositions for transductions of sparse graphs
• A meta-theorem for distributed certification
• Model checking on interpretations of classes of bounded local cliquewidth
• Bounds for the twin-width of graphs
• Complexity of maker-breaker games on edge sets of graphs
• Vertex-minors of graphs: a survey
• Sparse graphs with bounded induced cycle packing number have logarithmic treewidth
• Twin-width of graphs with tree-structured decompositions
• Graph product structure for \(h\)-framed graphs
• Twin-width and transductions of proper \(k\)-mixed-thin graphs
• Twin-width and polynomial kernels
• A meta-theorem for distributed certification
• A SAT approach to twin-width
• Tree-width for first order formulae

This page was built for publication: Twin-width. I: Tractable FO model checking

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5066940)