Simultaneous Feedback Edge Set: A Parameterized Perspective

Abstract

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 $\mathsf{col}:E(G)\to 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 \mathsf{col}(e)\})$ and $[\alpha ]=\{1,\dots ,\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 $\mathsf{col}:E(G)\to 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 \text{col}(e)\}$. We give an FPT algorithm for running in time $O(2^{\omega q\alpha }{n}^{O(1)})$.

A preliminary version of this paper will appear in the proceedings of ISAAC 2016