  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)})$.
