Polynomial Kernel for Interval Vertex Deletion
type: Item
instance of: scholarly article
title: Polynomial Kernel for Interval Vertex Deletion
DOI: 10.1145/3571075
author: Akanksha Agrawal
author: Daniel Lokshtanov
author: Pranabendu Misra
author: Saket Saurabh
author: Meirav Zehavi
published in: ACM Transactions on Algorithms
publication date: 2023-10-23T00:00:00Z
Mathematics Subject Classification ID: 68-XX
zbMATH DE Number: 7753162
zbMATH Keywords: interval vertex deletion
zbMATH Keywords: kernelization
zbMATH Keywords: polynomial kernel
zbMATH Keywords: parameterized complexity
MaRDI profile type: MaRDI publication profile
cites work: A Faster FPT Algorithm and a Smaller Kernel for Block Graph Vertex Deletion
cites work: Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion
cites work: Simultaneous Feedback Vertex Set
cites work: A unified approach to approximating resource allocation and scheduling
cites work: On problems without polynomial kernels
cites work: On generalized graphs
cites work: Graph Classes: A Survey
cites work: Linear Recognition of Almost Interval Graphs
cites work: Unit interval editing is fixed-parameter tractable
cites work: Interval Deletion Is Fixed-Parameter Tractable
cites work: Chordal editing is fixed-parameter tractable
cites work: Parameterized Algorithms
cites work: Q5743378
cites work: Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
cites work: Q3577833
cites work: Fundamentals of parameterized complexity
cites work: New Limits to Classical and Quantum Instance Compression
cites work: Parametrized complexity theory.
cites work: Preprocessing subgraph and minor problems: when does a small vertex cover help?
cites work: Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
cites work: Infeasibility of instance compression and succinct PCPs for NP
cites work: A unified approximation algorithm for node-deletion problems
cites work: Incidence matrices and interval graphs
cites work: Q3328583
cites work: A completeness theory for polynomial (Turing) kernelization
cites work: Q5743381
cites work: A Near-Optimal Planarization Algorithm
cites work: Approximation and Kernelization for Chordal Vertex Deletion
cites work: Unit interval vertex deletion: fewer vertices are relevant
cites work: Incidence matrices, interval graphs and seriation in archeology
cites work: A polynomial kernel for block graph deletion
cites work: Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
cites work: Q4967164
cites work: Representation of a finite graph by a set of intervals on the real line
cites work: The node-deletion problem for hereditary properties is NP-complete
cites work: Kernelization – Preprocessing with a Guarantee
cites work: A characterization of perfect graphs
cites work: On the hardness of approximating minimization problems
cites work: A parameterized view on matroid optimization problems
cites work: Chordal deletion is fixed-parameter tractable
cites work: Q5710169
cites work: Q5484515
cites work: Node-and edge-deletion NP-complete problems
Wikidata QID: Q130951152
Recommended article: A Polynomial Kernel for Proper Interval Vertex Deletion
Recommended article: Interval Vertex Deletion Admits a Polynomial Kernel
Recommended article: A polynomial kernel for distance-hereditary vertex deletion
Recommended article: A Polynomial Kernel for Line Graph Deletion
Recommended article: Q5363781
Recommended article: A polynomial kernel for block graph deletion
Recommended article: A polynomial kernel for bipartite permutation vertex deletion
Recommended article: Quadratic vertex kernel for split vertex deletion
description: scientific article; zbMATH DE number 7753162