文章基本信息

标题：Strong Parameterized Deletion: Bipartite Graphs
本地全文：下载
作者：Ashutosh Rai ; M. S. Ramanujan
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：65
页码：21:1-21:14
DOI：10.4230/LIPIcs.FSTTCS.2016.21
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：fixed parameter tractable; bipartite-editing; recursive understanding