Simultaneous Feedback Edge Set: A Parameterized Perspective

In this paper we consider Simultaneous Feedback Edge Set (Sim-FES) problem. In this problem, the input is an $n$-vertex graph $G$, an integer $k$ and a coloring function ${sf col}: E(G) rightarrow 2^{[alpha]}$ 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. Here, $G_i=(V(G), {ein E(G) mid i in {sf col}(e)})$ and $[alpha]={1,ldots,alpha}$. When $alpha =1$, the problem is polynomial time solvable. We show that for $alpha =3$ Sim-FES is NP-hard by giving a reduction from Vertex Cover on cubic graphs. 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 Sim-FES running in time $O(2^{omega kalpha+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 Sim-FES with $(kalpha)^{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 ${sf col}: E(G) rightarrow 2^{[alpha]}$. The question is whether there is a edge subset $F$ of cardinality at least $q$ in $G$ such that for all $iin [alpha]$, $G[F_i]$ is acyclic. Here, $F_i={e in F mid i in textsf{col}(e)}$. We give an FPT algorithm for running in time $O(2^{omega q alpha}n^{O(1)})$.