Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Polynomial Kernel for Interval Vertex Deletion

Polynomial Kernel for Interval Vertex Deletion Given a graph G and an integer k, the Interval Vertex Deletion (IVD) problem asks whether there exists a subset S⊆ V(G) of size at most k such that G-S is an interval graph. This problem is known to be NP-complete (according to Yannakakis at STOC 1978). Originally in 2012, Cao and Marx showed that IVD is fixed parameter tractable: they exhibited an algorithm with running time 10k nO(1). The existence of a polynomial kernel for IVD remained a well-known open problem in parameterized complexity. In this article, we settle this problem in the affirmative. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Algorithms (TALG) Association for Computing Machinery

Polynomial Kernel for Interval Vertex Deletion

Download PDF
68 pages

Loading next page...
 
/lp/association-for-computing-machinery/polynomial-kernel-for-interval-vertex-deletion-0f9yllQuNW

References

References for this paper are not available at this time. We will be adding them shortly, thank you for your patience.

Publisher
Association for Computing Machinery
Copyright
Copyright © 2023 Copyright held by the owner/author(s). Publication rights licensed to ACM.
ISSN
1549-6325
eISSN
1549-6333
DOI
10.1145/3571075
Publisher site
See Article on Publisher Site

Abstract

Given a graph G and an integer k, the Interval Vertex Deletion (IVD) problem asks whether there exists a subset S⊆ V(G) of size at most k such that G-S is an interval graph. This problem is known to be NP-complete (according to Yannakakis at STOC 1978). Originally in 2012, Cao and Marx showed that IVD is fixed parameter tractable: they exhibited an algorithm with running time 10k nO(1). The existence of a polynomial kernel for IVD remained a well-known open problem in parameterized complexity. In this article, we settle this problem in the affirmative.

Journal

ACM Transactions on Algorithms (TALG) – Association for Computing Machinery

Published: Apr 15, 2023

Keywords: Interval Vertex Deletion

References

  • A faster FPT algorithm and a smaller kernel for block graph vertex deletion
    [,
  • Feedback vertex set inspired kernel for chordal vertex deletion
    [,
  • Feedback vertex set inspired kernel for chordal vertex deletion
    [,
  • Simultaneous feedback vertex set: A parameterized perspective
    [,
  • A unified approach to approximating resource allocation and scheduling
    [,
  • On problems without polynomial kernels
    [,
  • On generalized graphs
    [,
  • Graph Classes: A Survey
    [,
  • Linear recognition of almost interval graphs
    [,
  • Unit interval editing is fixed-parameter tractable
    [,
  • Interval deletion is fixed-parameter tractable
    [,
  • Chordal editing is fixed-parameter tractable
    [,
  • Parameterized Algorithms
    [,
  • Open problems from Workshop on Kernels
    [,
  • Kernelization of packing problems
    [,
  • Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
    [,
  • Graph Theory (4th ed
    [,
  • Fundamentals of Parameterized Complexity
    [,
  • New limits to classical and quantum instance compression
    [,
  • Parameterized Complexity Theory
    [,
  • Preprocessing subgraph and minor problems: When does a small vertex cover help? Journal of Computer and System Sciences 80, 2 (2014), 468–495
    [,
  • Planar f-deletion: Approximation, kernelization and optimal FPT algorithms
    [,
  • Efficient computation of representative families with applications in parameterized and exact algorithms
    [,
  • Kernelization methods for fixed-parameter tractability
    [,
  • Infeasibility of instance compression and succinct PCPs for NP
    [,
  • A unified approximation algorithm for node-deletion problems
    [,
  • Incidence matrices and interval graphs
    [,
  • Algorithmic Graph Theory and Perfect Graphs
    [,
  • Invitation to data reduction and problem kernelization
    [,
  • A completeness theory for polynomial (turing) kernelization
    [,
  • Weak compositions and their applications to polynomial lower bounds for kernelization
    [,
  • The Power of Data Reduction: Kernels for Fundamental Graph Problems
    [,
  • A near-optimal planarization algorithm
    [,
  • Approximation and kernelization for chordal vertex deletion
    [,
  • Approximation and kernelization for chordal vertex deletion
    [,
  • Approximation and kernelization for chordal vertex deletion
    [,
  • Unit interval vertex deletion: Fewer vertices are relevant
    [,
  • Incidence matrices, interval graphs and seriation in archeology
    [,
  • A polynomial kernel for block graph deletion
    [,
  • Linear kernels and single-exponential algorithms via protrusion decompositions
    [,
  • Recent developments in kernelization: A survey
    [,
  • Representative sets and irrelevant vertices: New tools for kernelization
    [,
  • Linear Algebra and Its Applications
    [,
  • Representation of a finite graph by a set of intervals on the real line
    [,
  • The node-deletion problem for hereditary properties is NP-complete
    [,
  • Kernelization—Preprocessing with a guarantee
    [,
  • A characterization of perfect graphs
    [,
  • On the hardness of approximating minimization problems
    [,
  • A parameterized view on matroid optimization problems
    [,
  • Chordal deletion is fixed-parameter tractable
    [,
  • Invitation to Fixed-Parameter Algorithms
    [,
  • Matroid Theory
    [,
  • Node- and edge-deletion NP-complete problems
    [,