Rai, Ashutosh ;
Ramanujan, M. S.
Strong Parameterized Deletion: Bipartite Graphs
Abstract
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 GS 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 GS can be made bipartite by deleting at most l edges. While fixedparameter tractability when parameterizing by k or l alone is unlikely, we show that this problem is fixedparameter tractable (FPT) when parameterized by both k and l.
BibTeX  Entry
@InProceedings{rai_et_al:LIPIcs:2016:6856,
author = {Ashutosh Rai and M. S. Ramanujan},
title = {{Strong Parameterized Deletion: Bipartite Graphs}},
booktitle = {36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
pages = {21:121:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770279},
ISSN = {18688969},
year = {2016},
volume = {65},
editor = {Akash Lal and S. Akshay and Saket Saurabh and Sandeep Sen},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6856},
URN = {urn:nbn:de:0030drops68561},
doi = {10.4230/LIPIcs.FSTTCS.2016.21},
annote = {Keywords: fixed parameter tractable, bipartiteediting, recursive understanding}
}
10.12.2016
Keywords: 

fixed parameter tractable, bipartiteediting, recursive understanding 
Seminar: 

36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)

Issue date: 

2016 
Date of publication: 

10.12.2016 