On the parameterized complexity of graph modification to first-order logic properties
From MaRDI portal
Publication:2300624
DOI10.1007/s00224-019-09938-8zbMath1434.68208arXiv1805.04375OpenAlexW2963662357WikidataQ127491553 ScholiaQ127491553MaRDI QIDQ2300624
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
Graph theory (including graph drawing) in computer science (68R10) Descriptive complexity and finite models (68Q19) Parameterized complexity, tractability and kernelization (68Q27)
Related Items (4)
Streaming deletion problems parameterized by vertex cover ⋮ Streaming deletion problems Parameterized by vertex cover ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Chordless Cycle Packing Is Fixed-Parameter Tractable
Cites Work
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- A kernelization algorithm for \(d\)-hitting set
- On problems without polynomial kernels
- The node-deletion problem for hereditary properties is NP-complete
- Which problems have strongly exponential complexity?
- Two edge modification problems without polynomial kernels
- The complexity of first-order and monadic second-order logic revisited
- On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
- Incompressibility of \(H\)-free edge modification problems
- Parametrized complexity theory.
- Edge-Deletion Problems
- Faster decision of first-order graph properties
- Kernelization Lower Bounds by Cross-Composition
- Descriptive Complexity, Canonisation, and Definable Graph Structure Theory
- Existential second-order logic over graphs
- Parameterized Algorithms
- The classical decision problem.
This page was built for publication: On the parameterized complexity of graph modification to first-order logic properties
