2026-07-22T16:12:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15406 2024-03-06T10:55:40Z ddc:004 open_access

A Polynomial Kernel for Bipartite Permutation Vertex Deletion Kanesh, Lawqueen Madathil, Jayakrishnan Sahu, Abhishek Saurabh, Saket Verma, Shaily kernelization bipartite permutation graph bicliques In a permutation graph, vertices represent the elements of a permutation, and edges represent pairs of elements that are reversed by the permutation. In the Permutation Vertex Deletion problem, given an undirected graph G and an integer k, the objective is to test whether there exists a vertex subset S ⊆ V(G) such that |S| ≤ k and G-S is a permutation graph. The parameterized complexity of Permutation Vertex Deletion is a well-known open problem. Bożyk et al. [IPEC 2020] initiated a study towards this problem by requiring that G-S be a bipartite permutation graph (a permutation graph that is bipartite). They called this the Bipartite Permutation Vertex Deletion (BPVD) problem. They showed that the problem admits a factor 9-approximation algorithm as well as a fixed parameter tractable (FPT) algorithm running in time 𝒪(9^k |V(G)|⁹). And they posed the question {whether BPVD admits a polynomial kernel.} We resolve this question in the affirmative by designing a polynomial kernel for BPVD. In particular, we obtain the following: Given an instance (G,k) of BPVD, in polynomial time we obtain an equivalent instance (G',k') of BPVD such that k' ≤ k, and |V(G')|+|E(G')| ≤ k^{𝒪(1)}. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Lawqueen Kanesh and Jayakrishnan Madathil and Abhishek Sahu and Saket Saurabh and Shaily Verma 2021 Is Part Of LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2021.23 urn:nbn:de:0030-drops-154065 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.23 eng https://creativecommons.org/licenses/by/4.0/legalcode