Agrawal, Akanksha ;
Krithika, R. ;
Lokshtanov, Daniel ;
Mouawad, Amer E. ;
Ramanujan, M. S.
On the Parameterized Complexity of Simultaneous Deletion Problems
Abstract
For a family of graphs F, an nvertex graph G, and a positive integer k, the FDeletion problem asks whether we can delete at most k vertices from G to obtain a graph in F. FDeletion generalizes many classical graph problems such as Vertex Cover, Feedback Vertex Set, and Odd Cycle Transversal. A (multi) graph G = (V, \cup_{i=1}^{\alpha} E_{i}), where the edge set of G is partitioned into \alpha color classes, is called an \alphaedgecolored graph. A natural extension of the FDeletion problem to edgecolored graphs is the Simultaneous (F_1, \ldots, F_\alpha)Deletion problem. In the latter problem, we are given an \alphaedgecolored graph G and the goal is to find a set S of at most k vertices such that each graph G_i  S, where G_i = (V, E_i) and 1 \leq i \leq \alpha, is in F_i. Recently, a subset of the authors considered the aforementioned problem with F_1 = \ldots = F_\alpha being the family of all forests. They showed that the problem is fixedparameter tractable when parameterized by k and \alpha, and can be solved in O(2^{O(\alpha k)}n^{O(1)})
time. In this work, we initiate the investigation of the complexity of Simultaneous (F_1, \ldots, F_\alpha)Deletion with different families of graphs. In the process, we obtain a complete characterization of the parameterized complexity of this problem when one or more of the F_i's is the class of bipartite graphs and the rest (if any) are forests.
We show that if F_1 is the family of all bipartite graphs and each of F_2 = F_3 = \ldots = F_\alpha is the family of all forests then the problem is fixedparameter tractable
parameterized by k and \alpha. However, even when F_1 and F_2 are both the family of all bipartite graphs, then the Simultaneous (F_1, F_2)Deletion} problem itself is already W[1]hard.
BibTeX  Entry
@InProceedings{agrawal_et_al:LIPIcs:2018:8412,
author = {Akanksha Agrawal and R. Krithika and Daniel Lokshtanov and Amer E. Mouawad and M. S. Ramanujan},
title = {{On the Parameterized Complexity of Simultaneous Deletion Problems}},
booktitle = {37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)},
pages = {9:19:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770552},
ISSN = {18688969},
year = {2018},
volume = {93},
editor = {Satya Lokam and R. Ramanujam},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8412},
URN = {urn:nbn:de:0030drops84128},
doi = {10.4230/LIPIcs.FSTTCS.2017.9},
annote = {Keywords: parameterized complexity, feedback vertex set, odd cycle transversal, edgecolored graphs, simultaneous deletion}
}
12.02.2018
Keywords: 

parameterized complexity, feedback vertex set, odd cycle transversal, edgecolored graphs, simultaneous deletion 
Seminar: 

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

Issue date: 

2018 
Date of publication: 

12.02.2018 