Preprocessing vertex-deletion problems: characterizing graph properties by low-rank adjacencies
From MaRDI portal
Abstract: We consider the -free Deletion problem parameterized by the size of a vertex cover, for a range of graph properties . Given an input graph , this problem asks whether there is a subset of at most vertices whose removal ensures the resulting graph does not contain a graph from as induced subgraph. Many vertex-deletion problems such as Perfect Deletion, Wheel-free Deletion, and Interval Deletion fit into this framework. We introduce the concept of characterizing a graph property by low-rank adjacencies, and use it as the cornerstone of a general kernelization theorem for -Free Deletion parameterized by the size of a vertex cover. The resulting framework captures problems such as AT-Free Deletion, Wheel-free Deletion, and Interval Deletion. Moreover, our new framework shows that the vertex-deletion problem to perfect graphs has a polynomial kernel when parameterized by vertex cover, thereby resolving an open question by Fomin et al. [JCSS 2014]. Our main technical contribution shows how linear-algebraic dependence of suitably defined vectors over implies graph-theoretic statements about the presence of forbidden induced subgraphs.
Recommendations
- scientific article; zbMATH DE number 7759295
- Rank reduction of directed graphs by vertex and edge deletions
- Tight running time lower bounds for vertex deletion problems
- On structural parameterizations of the bounded-degree vertex deletion problem
- On structural parameterizations of the bounded-degree vertex deletion problem
- A parameterized algorithm for bounded-degree vertex deletion
- Rank reduction of oriented graphs by vertex and edge deletions
- On the Complexity of Singly Connected Vertex Deletion
- On the complexity of singly connected vertex deletion
- Approximating Node-Deletion Problems for Matroidal Properties
Cites work
- (Meta) kernelization
- A Polynomial Kernel for Diamond-Free Editing
- A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion
- Approximation and kernelization for chordal vertex deletion
- Binomial Coefficients Modulo a Prime
- Compression via Matroids
- Data reduction for graph coloring problems
- Fundamentals of parameterized complexity
- Graph Classes: A Survey
- How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
- Interval vertex deletion admits a polynomial kernel
- Kernelization Lower Bounds by Cross-Composition
- Kernelization. Theory of parameterized preprocessing
- Linear-time kernelization for feedback vertex set
- On cutwidth parameterized by vertex cover
- Optimal data reduction for graph coloring using low-degree polynomials
- Parameterized algorithmics and computational experiments for finding 2-clubs
- Parameterized algorithms
- Parameterized algorithms and data reduction for the short secluded s‐t‐path problem
- Parameterized complexity of vertex deletion into perfect graph classes
- Partially Ordered Sets
- Polynomial kernelization for removing induced claws and diamonds
- Polynomial kernels for hitting forbidden minors under structural parameterizations
- Preprocessing subgraph and minor problems: when does a small vertex cover help?
- Recognizing graphs without asteroidal triples
- Sparsity. Graphs, structures, and algorithms
- The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel
- The node-deletion problem for hereditary properties is NP-complete
- The strong perfect graph theorem
- Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
- Transitiv orientierbare Graphen
- Two-layer planarization parameterized by feedback edge set
- Wheel-Free Deletion Is W[2]-Hard
Cited in
(4)
This page was built for publication: Preprocessing vertex-deletion problems: characterizing graph properties by low-rank adjacencies
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2119402)
