Fixed-point definability and polynomial time on chordal graphs and line graphs

DOI10.1007/978-3-642-15025-8_17MaRDI QIDQ3586010zbMATH OpenOpenAlexFDO

Authors Martin Grohe

Publication date 3 September 2010

Published in Fields of Logic and Computation (Search for Journal in Brave)

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

zbMATH Keywords

descriptive complexity theoryfixed-point logic

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Abstract: The question of whether there is a logic that captures polynomial time was formulated by Yuri Gurevich in 1988. It is still wide open and regarded as one of the main open problems in finite model theory and database theory. Partial results have been obtained for specific classes of structures. In particular, it is known that fixed-point logic with counting captures polynomial time on all classes of graphs with excluded minors. The introductory part of this paper is a short survey of the state-of-the-art in the quest for a logic capturing polynomial time. The main part of the paper is concerned with classes of graphs defined by excluding induced subgraphs. Two of the most fundamental such classes are the class of chordal graphs and the class of line graphs. We prove that capturing polynomial time on either of these classes is as hard as capturing it on the class of all graphs. In particular, this implies that fixed-point logic with counting does not capture polynomial time on these classes. Then we prove that fixed-point logic with counting does capture polynomial time on the class of all graphs that are both chordal and line graphs.

Recommendations

• Capturing polynomial time using modular decomposition
• scientific article; zbMATH DE number 7204318
• Capturing polynomial time using modular decomposition
• scientific article; zbMATH DE number 7080199
• Fixed-point definability and polynomial time on graphs with excluded minors

Cites work

• scientific article; zbMATH DE number 3679848 (Why is no real title available?)
• scientific article; zbMATH DE number 3474957 (Why is no real title available?)
• scientific article; zbMATH DE number 3575612 (Why is no real title available?)
• scientific article; zbMATH DE number 1254648 (Why is no real title available?)
• scientific article; zbMATH DE number 1324669 (Why is no real title available?)
• scientific article; zbMATH DE number 612169 (Why is no real title available?)
• scientific article; zbMATH DE number 979011 (Why is no real title available?)
• scientific article; zbMATH DE number 1392292 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• A restricted second order logic for finite structures
• Almost Everywhere Equivalence of Logics in Finite Model Theory
• An extension of fixpoint logic with a symmetry-based choice construct
• An optimal lower bound on the number of variables for graph identification
• Approximating clique-width and branch-width
• Bisimulation-invariant PTIME and higher-dimensional \(\mu\)-calculus
• Canonization for two variables and puzzles on the square
• Characterizations of derived graphs
• Choiceless polynomial time
• Computer Science Logic
• Definability hierarchies of generalized quantifiers
• Elements of finite model theory.
• Expressive equivalence of least and inflationary fixed-point logic
• Finite model theory and its applications.
• Fixed-point definability and polynomial time on graphs with excluded minors
• Fixed-point extensions of first-order logic
• From Invariants to Canonization in Parallel
• Generalized Quantifiers and Logical Reducibilities
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• Languages that Capture Complexity Classes
• On a new high dimensional Weisfeiler-Lehman algorithm
• On highly closed cellular algebras and highly closed isomorphisms
• On logics with two variables
• On polynomial time computation over unordered structures
• Planar Graphs: Logical Complexity and Parallel Isomorphism Tests
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• Procedural languages for database queries and updates
• Relational queries computable in polynomial time
• Sequential abstract-state machines capture sequential algorithms
• Structure and complexity of relational queries
• Testing Graph Isomorphism in Parallel by Playing a Game
• The expressive power of finitely many generalized quantifiers
• The strong perfect graph theorem
• The structure of claw-free graphs
• Upper bounds to the clique width of graphs

Cited in

(5)

• Fixed-point definability and polynomial time on graphs with excluded minors
• On fixed-point logic with counting
• Strong simulation: capturing topology in graph pattern matching
• Capturing polynomial time using modular decomposition
• Fixed-Point Definability and Polynomial Time

This page was built for publication: Fixed-point definability and polynomial time on chordal graphs and line graphs

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