partition.

\[red:vcr\] Let $\mathcal{P}_{r_1, \dots, r_{2x}}$ be a set of the vertex cover partition with $|\mathcal{P}_{r_1, \dots, r_{2x}}| > 1$. Delete an arbitrary vertex $u \in \mathcal{P}_{r_1, \dots, r_{2x}}$ and increase $d$ by $\min_{i \in [x]} p_{r_i}$.

Note that since the input graph is strongly connected, the increase in $d$ in is at most $\max_{i \in [q]} p_i < \infty$.

is correct.

Let $I = (G, w)$ be an instance of <span style="font-variant:small-caps;">MinPAC</span> and let $I'= (G', w')$ be the instance obtained by deleting vertex $u$ in a set $\mathcal{P}_{r_1, \dots, r_{2x}}$ of the vertex cover partition for $G$, as specified in . We show that $\operatorname{OPT}(I) = \operatorname{OPT}(I') +  \min_{i \in [x]} p_{r_i}$.

Let $H$ be an optimal solution of $I$. Since $|\mathcal{P}_{r_1, \dots, r_{2x}}| > 1$, there exists a vertex $u' \in \mathcal{P}_{r_1, \dots, r_{2x}} \setminus \{ u \}$. We can assume without loss of generality that $\max_{uv \in A(H)} w(uv) \le \max_{(u'v) \in A(H)} w(u'v)$ holds: if it does not hold, we can exchange the role of $u$ and $u'$ in $H$ without changing the cost of the solution, that is, we can update $H$ to $H'$ with $$\begin{aligned}
    A(H') := {}& \{vv' \mid vv' \in A(H) 