Existential second-order logic over graphs: parameterized complexity

DOI10.4230/LIPICS.IPEC.2023.3MaRDI QIDQ6926207zbMATH OpenFDO

Authors Max Bannach, Florian Chudigiewitsch, Till Tantau

Publication date 24 September 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.IPEC.2023.3

zbMATH Keywords

existential second-order logicfixed-parameter tractabilityparallel algorithmsdescriptive complexitygraph problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68Wxx) Parameterized complexity, tractability and kernelization (68Q27)

Cites work

• scientific article; zbMATH DE number 3474957 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• Computational Complexity
• Computing kernels in parallel: lower and upper bounds
• Existential second-order logic over graphs: a complete complexity-theoretic classification
• Existential second-order logic over graphs: charting the tractability frontier
• Existential second-order logic over graphs: parameterized complexity
• Existential second-order logic over strings
• Fast parallel fixed-parameter algorithms via color coding
• Graph structure and monadic second-order logic. A language-theoretic approach
• Improved depth lower bounds for small distance connectivity
• On the parameterized complexity of graph modification to first-order logic properties
• Parametrized complexity theory.
• Some lower bounds in parameterized \(\mathrm{AC}^0\)
• Weak Second‐Order Arithmetic and Finite Automata

Cited in

(2)

• On the descriptive complexity of vertex deletion problems
• Existential second-order logic over graphs: parameterized complexity

This page was built for publication: Existential second-order logic over graphs: parameterized complexity

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