A polynomial kernel for bipartite permutation vertex deletion

DOI10.1007/S00453-022-01040-9MaRDI QIDQ2093571zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

kernelizationbipartite permutation graphbicliques

Mathematics Subject Classification ID

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

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

Cites work

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

Cited in

(9)

• Vertex deletion into bipartite permutation graphs
• A polynomial kernel for distance-hereditary vertex deletion
• A Polynomial Kernel for Proper Interval Vertex Deletion
• Vertex deletion into bipartite permutation graphs
• Polynomial Kernel for Interval Vertex Deletion
• A polynomial kernel for bipartite permutation vertex deletion
• A polynomial kernel for deletion to the scattered class of cliques and trees
• Kernel for proper Helly circular-arc vertex deletion: smaller and simpler via graph isomorphism
• 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)