LAUSR

Agrawal et al. (ACM Trans Comput Theory 10(4):18:1–18:25, 2018. https://doi.org/10.1145/3265027 ) studied a simultaneous variant of the classic F eedback V ertex S et problem, called S imultaneous F eedback V ertex S et (S im -FVS). Here, we consider the edge variant of the problem, namely, S imultaneous F eedback E dge S et (S im -FES). In this problem, the input is an n -vertex graph G , a positive integer k , and a coloring function col : $$E(G) \rightarrow 2^{[\alpha ]}$$ E ( G ) → 2 [ α ] , and the objective is to check whether there is an edge subset S of cardinality k in G such that for each $$i \in [\alpha ]$$ i ∈ [ α ] , $$G_i - S$$ G i - S is acyclic. Unlike the vertex variant of the problem, when $$\alpha =1$$ α = 1 , the problem is equivalent to finding a maximal spanning forest and hence it is polynomial time solvable. We show that for $$\alpha =3$$ α = 3 , S im -FES is NP-hard, and does not admit an algorithm of running time $$2^{o(k)}n^{{{\mathcal {O}}}(1)}$$ 2 o ( k ) n O ( 1 ) unless ETH fails. This hardness result is complimented by an FPT algorithm for S im -FES running in time $$2^{\omega k \alpha +\alpha \log k} n^{{{\mathcal {O}}}(1)}$$ 2 ω k α + α 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$$ α = 2 . We also give a kernel for S im -FES with $$(k\alpha )^{{\mathcal {O}}(\alpha )}$$ ( k α ) O ( α ) vertices. Finally, we consider a “dual” version of the problem called M aximum S imultaneous A cyclic S ubgraph and give an FPT algorithm with running time $$2^{\omega q \alpha }n^{{\mathcal {O}}(1)}$$ 2 ω q α n O ( 1 ) , where q is the number of edges in the output subgraph.