is optimal to fully cover a plane. In such cases, we can assume that the *obligatory arcs*, arcs that are in any optimal solution, induce a small number $c$ of strongly connected components as there are many arcs of minimum weight. In , we define obligatory arcs, discuss the connection to grid-like graphs, and present an algorithm that solves <span style="font-variant:small-caps;">MinPAC</span> in linear time when $c$ is a constant.

In \[sec:vcn\], we study <span style="font-variant:small-caps;">MinPAC</span> parameterized by the number of different arc weights and the vertex cover number. For this combined parameter, we present an exponential-size kernel.

In , we describe a linear-time algorithm which reduces any input instance to an equivalent instance with at most $20g - 20$ vertices and $42g - 42$ arcs, where $g$ is the feedback edge number of the underlying undirected graph. The parameter is also motivated by real world applications in which the feedback edge number is small; for instance, sensor networks along waterways (including canals) are expected to have a small number of feedback edges. It follows from our result hat the problem can be solved in polynomial time for $g \in O(\log n)$, that is, for very tree-like input graphs. In terms 