On the parameterized complexity of graph modification to first-order logic properties

DOI10.1007/S00224-019-09938-8MaRDI QIDQ2300624zbMATH OpenOpenAlexWikidataFDO

Authors Fedor V. Fomin, Dimitrios M. Thilikos, Petr A. Golovach

Publication date 27 February 2020

Published in Theory of Computing Systems (Search for Journal in Brave)

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

zbMATH Keywords

descriptive complexityfirst-order logicgraph modificationkernelizationparameterized complexity

Mathematics Subject Classification ID

Descriptive complexity and finite models (68Q19) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Abstract: We consider the problems of deciding whether an input graph can be modified by removing/adding at most k vertices/edges such that the result of the modification satisfies some property definable in first-order logic. We establish a number of sufficient and necessary conditions on the quantification pattern of the first-order formula phi for the problem to be fixed-parameter tractable or to admit a polynomial kernel.

Recommendations

• Parameterized complexity of elimination distance to first-order logic properties
• On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
• On the (Non-)existence of Polynomial Kernels for P l -free Edge Modification Problems
• Two edge modification problems without polynomial kernels
• Two edge modification problems without polynomial kernels

Cites work

• A kernelization algorithm for \(d\)-hitting set
• Descriptive Complexity, Canonisation, and Definable Graph Structure Theory
• Edge-Deletion Problems
• Existential second-order logic over graphs: charting the tractability frontier
• Faster decision of first-order graph properties
• Fundamentals of parameterized complexity
• scientific article; zbMATH DE number 3474957 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Incompressibility of \(H\)-free edge modification problems
• Kernelization Lower Bounds by Cross-Composition
• On problems without polynomial kernels
• On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
• Parameterized algorithms
• Parametrized complexity theory.
• The classical decision problem.
• The complexity of first-order and monadic second-order logic revisited
• The node-deletion problem for hereditary properties is NP-complete
• Two edge modification problems without polynomial kernels
• Which problems have strongly exponential complexity?

Cited in

(11)

• Streaming deletion problems parameterized by vertex cover
• The limits of decidability for first order logic on CPDA graphs
• First-Order Logic on CPDA Graphs
• Parameterized complexity of elimination distance to first-order logic properties
• An algorithmic meta-theorem for graph modification to planarity and FOL
• Chordless Cycle Packing Is Fixed-Parameter Tractable
• Streaming deletion problems Parameterized by vertex cover
• A survey of parameterized algorithms and the complexity of edge modification
• Trimming forests is hard (unless they are made of stars)
• Existential second-order logic over graphs: parameterized complexity
• On the descriptive complexity of vertex deletion problems

This page was built for publication: On the parameterized complexity of graph modification to first-order logic properties

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