Abstract
In a recent article Agrawal et al. (STACS 2016) studied a simultaneous variant of the classic Feedback Vertex Set problem, called Simultaneous Feedback Vertex Set (SimFVS). In this problem the input is an nvertex graph G, an integer k and a coloring function col : E(G) > 2^[alpha] , and the objective is to check whether there exists a vertex subset S of cardinality at most k in G such that for all i in [alpha], G_i  S is acyclic. Here, G_i = (V (G), {e in E(G)  i in col(e)}) and [alpha] = {1,...,alpha}. In this paper we consider the edge variant of the problem, namely, Simultaneous Feedback Edge Set (SimFES). In this problem, the input is same as the input of SimFVS and the objective is to check whether there is an edge subset S of cardinality at most k in G such that for all i in [alpha], G_i  S is acyclic. Unlike the vertex variant of the problem, when alpha = 1, the problem is equivalent to finding a maximal spanning forest and hence it is polynomial time solvable. We show that for alpha = 3 SimFES is NPhard by giving a reduction from Vertex Cover on cubicgraphs. The same reduction shows that the problem does not admit an algorithm of running time O(2^o(k) n^O(1)) unless ETH fails. This hardness result is complimented by an FPT algorithm for SimFES running in time O(2^((omega k alpha) + (alpha log k)) n^O(1)), where omega is the exponent in the running time of matrix multiplication. The same algorithm gives a polynomial time algorithm for the case when alpha = 2. We also give a kernel for SimFES with (k alpha)^O(alpha) vertices. Finally, we consider the problem Maximum Simultaneous Acyclic Subgraph. Here, the input is a graph G, an integer q and, a coloring function col : E(G) > 2^[alpha] . The question is whether there is a edge subset F of cardinality at least q in G such that for all i in [alpha], G[F_i] is acyclic. Here, F_i = {e in F  i in col(e)}. We give an FPT algorithm for Maximum Simultaneous Acyclic Subgraph running in time O(2^(omega q alpha) n^O(1) ). All our algorithms are based on parameterized version of the Matroid Parity problem.
BibTeX  Entry
@InProceedings{agrawal_et_al:LIPIcs:2016:6776,
author = {Akanksha Agrawal and Fahad Panolan and Saket Saurabh and Meirav Zehavi},
title = {{Simultaneous Feedback Edge Set: A Parameterized Perspective}},
booktitle = {27th International Symposium on Algorithms and Computation (ISAAC 2016)},
pages = {5:15:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770262},
ISSN = {18688969},
year = {2016},
volume = {64},
editor = {SeokHee Hong},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6776},
URN = {urn:nbn:de:0030drops67767},
doi = {10.4230/LIPIcs.ISAAC.2016.5},
annote = {Keywords: parameterized complexity, feedback edge set, alphamatroid parity}
}
Keywords: 

parameterized complexity, feedback edge set, alphamatroid parity 
Collection: 

27th International Symposium on Algorithms and Computation (ISAAC 2016) 
Issue Date: 

2016 
Date of publication: 

07.12.2016 