Prof. Meirav Zehavi

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 (SIM-FVS). In this problem the input is an n-vertex graph G, an integer k and a coloring function col : E(G) → 2^[α], 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 ∈ [α], G_i - S is acyclic. Here, G_i = (V (G), {e ∈ E(G) | i ∈ col(e)}) and [α] = {1, . . . , α}. In this paper we consider the edge variant of the problem, namely, SIMULTANEOUS FEEDBACK EDGE SET (SIM-FES). In this problem, the input is same as the input of SIM-FVS 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 ∈ [α], G_i - S is acyclic. Unlike the vertex variant of the problem, when α = 1, the problem is equivalent to finding a maximal spanning forest and hence it is polynomial time solvable. We show that for α = 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^{ωkα+α log log k}n^O(1)), where ω is the exponent in the running time of matrix multiplication. The same algorithm gives a polynomial time algorithm for the case when α = 2. We also give a kernel for SIM-FES with (kα)^O(α) vertices. Finally, we consider the problem MAXIMUM SIMULTANEOUS ACYCLICSUBGRAPH. Here, the input is a graph G, an integer q and, a coloring function col : E(G) → 2^[α]. The question is whether there is a edge subset F of cardinality at least q in G such that for all i ∈ [α], G[F_i] is acyclic. Here, F_i = {e ∈ F | i ∈ col(e)}. We give an FPT algorithm for MAXIMUM SIMULTANEOUS ACYCLIC SUBGRAPH running in time O(2^ωqαn^O(1)). All our algorithms are based on parameterized version of the MATROID PARITY problem.