When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2017.9
URN: urn:nbn:de:0030-drops-84128
URL: https://drops.dagstuhl.de/opus/volltexte/2018/8412/
 Go to the corresponding LIPIcs Volume Portal

### On the Parameterized Complexity of Simultaneous Deletion Problems

 pdf-format:

### Abstract

For a family of graphs F, an n-vertex graph G, and a positive integer k, the F-Deletion problem asks whether we can delete at most k vertices from G to obtain a graph in F. F-Deletion 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 \alpha-edge-colored graph. A natural extension of the F-Deletion problem to edge-colored graphs is the Simultaneous (F_1, \ldots, F_\alpha)-Deletion problem. In the latter problem, we are given an \alpha-edge-colored 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 fixed-parameter 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 fixed-parameter 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:1--9:14},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-055-2},
ISSN =	{1868-8969},
year =	{2018},
volume =	{93},
editor =	{Satya Lokam and R. Ramanujam},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},