is strongly connected.

\[obs:addv\] Let $G$ be a strongly connected graph. For any vertices $v, v' \in V(G)$, $u \notin V(G)$, the graph $G + uv + v'u$ is strongly connected.

We define “types” for vertices outside the vertex cover according to the weights of their incident arcs. This helps us to reduce the number of vertices using the observations above. Recall that we write $w(vu) = \infty$ if $vu \not\in A$.

Let $(G, w)$ be an instance of <span style="font-variant:small-caps;">MinPAC</span> with $w \colon A(G) \to Q$ and $Q = \{ p_1, \dots, p_q \} \in {\mathds{N}}^q$. Let $X = \{ v_1, \dots, v_x \}$ be a vertex cover of $G$. The *vertex cover partition* is the partition $\mathcal{P}$ of vertices in $V(G) \setminus X$ into sets $$\begin{aligned}
    \mathcal{P}_{r_1, \dots, r_{2x}} = \{ u \in V(G) \setminus X \mid \forall i \in [x].\;w(u v_i) = p_{r_i} \wedge w(v_i u) = p_{r_{i+x}}  \},
  \end{aligned}$$ for each $r_1, \dots, r_{2x} \in [q + 1]$. Here we set $p_{q+1} = \infty$.

We initialize $d$ with 0. In our reduction rule, we remove vertices such that, after the reduction is completed, there is at most one vertex in each set of the vertex cover 