2026-07-20T14:34:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6856 2024-03-06T10:39:02Z ddc:004 open_access

Strong Parameterized Deletion: Bipartite Graphs Rai, Ashutosh Ramanujan, M. S. fixed parameter tractable bipartite-editing recursive understanding The purpose of this article is two fold: (a) to formally introduce a stronger version of graph deletion problems; and (b) to study this version in the context of bipartite graphs. Given a family of graphs F, a typical instance of parameterized graph deletion problem consists of an undirected graph G and a positive integer k and the objective is to check whether we can delete at most k vertices (or k edges) such that the resulting graph belongs to F. Another version that has been recently studied is the one where the input contains two integers k and l and the objective is to check whether we can delete at most k vertices and l edges such that the resulting graph belongs to F. In this paper, we propose and initiate the study of a more general version which we call strong deletion. In this problem, given an undirected graph G and positive integers k and l, the objective is to check whether there exists a vertex subset S of size at most k such that each connected component of G-S can be transformed into a graph in F by deleting at most l edges. In this paper we study this stronger version of deletion problems for the class of bipartite graphs. In particular, we study Strong Bipartite Deletion, where given an undirected graph G and positive integers k and l, the objective is to check whether there exists a vertex subset S of size at most k such that each connected component of G-S can be made bipartite by deleting at most l edges. While fixed-parameter tractability when parameterizing by k or l alone is unlikely, we show that this problem is fixed-parameter tractable (FPT) when parameterized by both k and l. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ashutosh Rai and M. S. Ramanujan 2016 Is Part Of LIPIcs, Volume 65, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2016.21 urn:nbn:de:0030-drops-68561 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2016.21 eng https://creativecommons.org/licenses/by/3.0/legalcode