Fixed-parameter tractable distances to sparse graph classes
From MaRDI portal
Publication:2408199
Abstract: We show that for various classes C of sparse graphs, and several measures of distance to such classes (such as edit distance and elimination distance), the problem of determining the distance of a given graph G to C is fixed-parameter tractable. The results are based on two general techniques. The first of these, building on recent work of Grohe et al. establishes that any class of graphs that is slicewise nowhere dense and slicewise first-order definable is FPT. The second shows that determining the elimination distance of a graph G to a minor-closed class C is FPT.
Recommendations
Cites work
- Deciding first-order properties of locally tree-decomposable structures
- Editing graphs to satisfy degree constraints: a parameterized approach
- Editing to a connected graph of given degrees
- Finite Model Theory on Tame Classes of Structures
- Fixed-parameter algorithms for cluster vertex deletion
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Fixed-parameter tractability, definability, and model-checking
- Graph editing problems with extended regularity constraints
- Graph Isomorphism Parameterized by Elimination Distance to Bounded Degree
- Graph minors. XX: Wagner's conjecture
- Homomorphism preservation on quasi-wide classes
- scientific article; zbMATH DE number 5764786 (Why is no real title available?)
- scientific article; zbMATH DE number 1324669 (Why is no real title available?)
- scientific article; zbMATH DE number 1007358 (Why is no real title available?)
- scientific article; zbMATH DE number 1161563 (Why is no real title available?)
- scientific article; zbMATH DE number 1432797 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- Kernelization using structural parameters on sparse graph classes
- On the fixed-parameter tractability of parameterized model-checking problems
- Parameterized and Exact Computation
- Parameterized coloring problems on chordal graphs
- Parameterized complexity of finding regular induced subgraphs
- Parametrized complexity theory.
- Sparsity. Graphs, structures, and algorithms
- Strongly regular graphs, partial geometries and partially balanced designs
Cited in
(27)- Graph extensions, edit number and regular graphs
- Measuring what matters: a hybrid approach to dynamic programming with treewidth
- Discrete density comonads and graph parameters
- FPT algorithms to compute the elimination distance to bipartite graphs and more
- Approximating the distance to properties in bounded-degree and general sparse graphs
- Recovering sparse graphs
- A fixed-parameter tractable algorithm for elimination distance to bounded degree graphs
- Parameterized complexity of elimination distance to first-order logic properties
- Elimination Distance to Bounded Degree on Planar Graphs
- scientific article; zbMATH DE number 6784973 (Why is no real title available?)
- Block elimination distance
- Block elimination distance
- Kernelization for feedback vertex set via elimination distance to a forest
- On the Parameterized Complexity of Clique Elimination Distance
- First-order Logic with Connectivity Operators
- Kernelization for feedback vertex set via elimination distance to a forest
- A survey of parameterized algorithms and the complexity of edge modification
- Backdoor DNFs
- Elimination distance to bounded degree on planar graphs preprint
- Faster parameterized algorithms for modification problems to minor-closed classes
- Kernelization dichotomies for hitting subgraphs under structural parameterizations
- Approximately interpolating between uniformly and non-uniformly polynomial kernels
- Towards exact structural thresholds for parameterized complexity
- Compound logics for modification problems
- An FPT algorithm for elimination distance to bounded degree graphs
- An overview of universal obstructions for graph parameters
- Obstructions for partitioning into forests and outerplanar graphs
This page was built for publication: Fixed-parameter tractable distances to sparse graph classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2408199)
