Close relatives (of Feedback Vertex Set), revisited

At IPEC 2020, Bergougnoux, Bonnet, Brettell, and Kwon showed that a number of problems related to the classic Feedback Vertex Set (FVS) problem do not admit a $2^{o(k\log k)}\cdot n^{\mathcal{O}(1)}$-time algorithm on graphs of treewidth at most $k$, assuming the Exponential Time Hypothesis. This contrasts with the $3^k\cdot k^{\mathcal{O}(1)}\cdot n$-time algorithm for FVS using the Cut&Count technique. During their live talk at IPEC 2020, Bergougnoux et al.~posed a number of open questions, which we answer in this work.

• Subset Even Cycle Transversal, Subset Odd Cycle Transversal, Subset Feedback Vertex Set can be solved in time $2^{\mathcal{O}(k\log k)}\cdot n$ in graphs of treewidth at most $k$. This matches a lower bound for Even Cycle Transversal of Bergougnoux et al.~and improves the polynomial factor in some of their upper bounds.
• Subset Feedback Vertex Set and Node Multiway Cut can be solved in time $2^{\mathcal{O}(k\log k)}\cdot n$, if the input graph is given as a clique-width expression of size $n$ and width $k$.
• Odd Cycle Transversal can be solved in time $4^k \cdot k^{$\mathcal{O}$(1)} \cdot n$iftheinputgraphisgivenasaclique-widthexpressionofsize$n$andwidth$k$\mathrm{.}Furthermore,theexistenceofaconstant$\varepsilon > 0$ and an algorithm performing this task in time $(4-\varepsilon)^k \cdot n^{$\mathcal{O}$(1)}$ would contradict the Strong Exponential Time Hypothesis.