A polynomial kernel for bipartite permutation vertex deletion

DOI10.1007/S00453-022-01040-9OpenAlexW3215419002MaRDI QIDQ2093571FDOQ2093571

Authors: Jan Derbisz, Lawqueen Kanesh, Jayakrishnan Madathil, Abhishek Sahu, Saket Saurabh, Shaily Verma 

Publication date: 27 October 2022

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-022-01040-9

Recommendations

• A polynomial kernel for distance-hereditary vertex deletion
• A polynomial kernel for distance-hereditary vertex deletion
• A Polynomial Kernel for Proper Interval Vertex Deletion
• A polynomial kernel for block graph deletion
• A polynomial kernel for block graph deletion
• Polynomial Kernel for Interval Vertex Deletion
• A polynomial kernel for \textsc{Proper Interval Vertex Deletion}
• Polynomial kernels for deletion to classes of acyclic digraphs
• Polynomial kernels for deletion to classes of acyclic digraphs
• Vertex deletion into bipartite permutation graphs

zbMATH Keywords

kernelizationbipartite permutation graphbicliques

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Fundamentals of parameterized complexity
• Title not available (Why is that?)
• Graph Classes: A Survey
• On problems without polynomial kernels
• The node-deletion problem for hereditary properties is NP-complete
• A unified approximation algorithm for node-deletion problems
• Modular decomposition and transitive orientation
• Parametrized complexity theory.
• Kernelization -- preprocessing with a guarantee
• Recent developments in kernelization: a survey
• Parameterized algorithms
• Title not available (Why is that?)
• Node-and edge-deletion NP-complete problems
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• Infeasibility of instance compression and succinct PCPs for NP
• Bipartite permutation graphs
• On the hardness of approximating minimization problems
• New limits to classical and quantum instance compression
• Chordal deletion is fixed-parameter tractable
• Kernelization of packing problems
• Title not available (Why is that?)
• Unit interval vertex deletion: fewer vertices are relevant
• A Polynomial Kernel for Proper Interval Vertex Deletion
• Linear structure of bipartite permutation graphs and the longest path problem
• A completeness theory for polynomial (Turing) kernelization
• Feedback vertex set inspired kernel for chordal vertex deletion
• Approximation and kernelization for chordal vertex deletion
• Interval vertex deletion admits a polynomial kernel
• Vertex deletion into bipartite permutation graphs

Cited In (4)

• A polynomial kernel for distance-hereditary vertex deletion
• A Polynomial Kernel for Proper Interval Vertex Deletion
• Polynomial Kernel for Interval Vertex Deletion
• A polynomial kernel for block graph deletion

This page was built for publication: A polynomial kernel for bipartite permutation vertex deletion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2093571)