A quartic kernel for pathwidth-one vertex deletion
From MaRDI portal
Abstract: The pathwidth of a graph is a measure of how path-like the graph is. Given a graph G and an integer k, the problem of finding whether there exist at most k vertices in G whose deletion results in a graph of pathwidth at most one is NP- complete. We initiate the study of the parameterized complexity of this problem, parameterized by k. We show that the problem has a quartic vertex-kernel: We show that, given an input instance (G = (V, E), k); |V| = n, we can construct, in polynomial time, an instance (G', k') such that (i) (G, k) is a YES instance if and only if (G', k') is a YES instance, (ii) G' has O(k^{4}) vertices, and (iii) k' leq k. We also give a fixed parameter tractable (FPT) algorithm for the problem that runs in O(7^{k} k cdot n^{2}) time.
Recommendations
- An improved FPT algorithm and a quadratic kernel for pathwidth one vertex deletion
- An improved FPT algorithm and quadratic kernel for pathwidth one vertex deletion
- Kernel bounds for structural parameterizations of pathwidth
- An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion
- An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion
Cites work
- A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
- A Cubic Kernel for Feedback Vertex Set
- A cubic kernel for feedback vertex set and loop cutset
- A partial k-arboretum of graphs with bounded treewidth
- A quartic kernel for pathwidth-one vertex deletion
- An \(\mathcal O(2^{O(k)}n^{3})\) FPT algorithm for the undirected feedback vertex set problem
- An improved FPT algorithm and quadratic kernel for pathwidth one vertex deletion
- Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
- Faster fixed parameter tractable algorithms for finding feedback vertex sets
- Graph bandwidth of weighted caterpillars
- Graph minors. I. Excluding a forest
- Graph minors. II. Algorithmic aspects of tree-width
- scientific article; zbMATH DE number 512804 (Why is no real title available?)
- scientific article; zbMATH DE number 512967 (Why is no real title available?)
- scientific article; zbMATH DE number 2203240 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- Obstruction set isolation for the gate matrix layout problem
- ON DISJOINT CYCLES
- On feedback vertex set new measure and new structures
- Parameterized and Exact Computation
- Subexponential parameterized algorithms
- The Bandwidth of Caterpillars with Hairs of Length 1 and 2
- The node-deletion problem for hereditary properties is NP-complete
- The NP-completeness of the bandwidth minimization problem
- The Proper Interval Colored Graph problem for caterpillar trees
- The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel
- Treewidth. Computations and approximations
- Treewidth: Characterizations, Applications, and Computations
Cited in
(22)- An improved FPT algorithm and a quadratic kernel for pathwidth one vertex deletion
- Faster deterministic algorithms for \textsc{Co-path Packing} and \textsc{Co-path/cycle Packing}
- Preprocessing for outerplanar vertex deletion: an elementary kernel of quartic size
- Faster algorithm for pathwidth one vertex deletion
- Modifying a graph using vertex elimination
- An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion
- Parameterized complexity of Eulerian deletion problems
- Kernel bounds for structural parameterizations of pathwidth
- Finite integer index of pathwidth and treewidth
- A quartic kernel for pathwidth-one vertex deletion
- An improved FPT algorithm and quadratic kernel for pathwidth one vertex deletion
- Parameterized complexity of Eulerian deletion problems
- A linear kernel for co-path/cycle packing
- Deleting vertices to bound path length
- An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion
- Quadratic vertex kernel for split vertex deletion
- Parameterized Complexity of Vertex Splitting to Pathwidth at Most 1
- Smaller kernels for two vertex deletion problems
- Parameterized complexity of vertex splitting to pathwidth at most 1
- Efficient constant-factor approximate enumeration of minimal subsets for monotone properties with weight constraints
- Approximately interpolating between uniformly and non-uniformly polynomial kernels
- Highly connected Steiner subgraph: parameterized algorithms and applications to hitting set problems
This page was built for publication: A quartic kernel for pathwidth-one vertex deletion
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3057625)
