Deletion to scattered graph classes. I: Case of finite number of graph classes
From MaRDI portal
Publication:6133645
Abstract: Graph-modification problems, where we modify a graph by adding or deleting vertices or edges or contracting edges to obtain a graph in a {it simpler} class, is a well-studied optimization problem in all algorithmic paradigms including classical, approximation and parameterized complexity. Specifically, graph-deletion problems, where one needs to delete a small number of vertices to make the resulting graph to belong to a given non-trivial hereditary graph class, captures several well-studied problems including {sc Vertex Cover}, {sc Feedback Vertex Set}, {sc Odd Cycle Transveral}, {sc Cluster Vertex Deletion}, and {sc Perfect Deletion}. Investigation into these problems in parameterized complexity has given rise to powerful tools and techniques. We initiate a study of a natural variation of the problem of deletion to {it scattered graph classes}. We want to delete at most vertices so that in the resulting graph, each connected component belongs to one of a constant number of graph classes. As our main result, we show that this problem is fixed-parameter tractable (FPT) when the deletion problem corresponding to each of the finite number of graph classes is known to be FPT and the properties that a graph belongs to any of the classes is expressible in Counting Monodic Second Order (CMSO) logic. While this is shown using some black box theorems in parameterized complexity, we give a faster FPT algorithm when each of the graph classes has a finite forbidden set.
Recommendations
- Parameterized complexity of deletion to scattered graph classes
- Deletion to scattered graph classes. II: Improved FPT algorithms for deletion to pairs of graph classes
- Parameterized complexity of vertex deletion into perfect graph classes
- Parameterized complexity of vertex deletion into perfect graph classes
- Parameterized vertex deletion problems for hereditary graph classes with a block property
Cites work
- Algorithmic graph theory and perfect graphs
- An improved parameterized algorithm for the minimum node multiway cut problem
- Bivariate complexity analysis of \textsc{Almost Forest Deletion}
- Chordal editing is fixed-parameter tractable
- Deletion to scattered graph classes. II: Improved FPT algorithms for deletion to pairs of graph classes
- Discovering archipelagos of tractability for constraint satisfaction and counting
- Easy problems for tree-decomposable graphs
- FPT algorithms to compute the elimination distance to bipartite graphs and more
- Faster FPT algorithms for deletion to pairs of graph classes
- Faster deterministic \textsc{Feedback Vertex Set}
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Generalized pseudoforest deletion: algorithms and uniform kernel
- Graph theory
- Hitting selected (odd) cycles
- Interval deletion is fixed-parameter tractable
- Linear time parameterized algorithms for subset feedback vertex set
- Node-Deletion Problems on Bipartite Graphs
- Parameterized algorithms
- Parameterized complexity of vertex deletion into perfect graph classes
- Parameterized graph separation problems
- Parameterized tractability of multiway cut with parity constraints
- Reducing CMSO model checking to highly connected graphs
- Saving critical nodes with firefighters is FPT
- Strong parameterized deletion: bipartite graphs
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- The node-deletion problem for hereditary properties is NP-complete
- Treewidth computation and extremal combinatorics
- Wheel-Free Deletion Is W[2]-Hard
Cited in
(3)
This page was built for publication: Deletion to scattered graph classes. I: Case of finite number of graph classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6133645)
