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), \{ e\in 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 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 Sim-FES 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 ${ \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 $i\in [\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)})$.
Categories: cs.DS