of parameterized complexity, this gives us a partial (weights left unbounded) kernelization of <span style="font-variant:small-caps;">MinPAC</span> with respect to the feedback edge number. Using an existing weight-shrinking technique [@BBFNN], we also provide a “full” polynomial-size kernel with respect to the feedback edge number.

Finally, in we derive hardness results for <span style="font-variant:small-caps;">PAC</span>, the decision version of <span style="font-variant:small-caps;">MinPAC</span>. We show that even if the input graph has only binary weights and is almost a DAG (a directed acyclic graph with one additional arc), <span style="font-variant:small-caps;">PAC</span> parameterized by the solution cost is W\[2\]-hard. This is in sharp contrast to the FPT result for the parameter feedback edge number.

#### Preliminaries.

For $a \in {\mathds{N}}$, we abbreviate $\{1, \dots, a\}$ by $[a]$. Throughout this work, we assume that a graph is directed unless stated otherwise. For a graph $G = (V, A)$, we write $V(G)$ to denote $V$ and $A(G)$ to denote $A$. We abbreviate arcs $(u,v) \in A$ by $uv$. We denote by $G[V']$ the subgraph induced by $V'\subseteq V(G)$. We use $G + vu$ to denote $(V(G) \cup \{ v, u \}, A(G) \cup \{ vu \})$ and $G - vu$ to denote $(V(G), A(G) \setminus \{ vu \})$. For a 