but any maximal matching (which can be found in linear time) gives a factor-2 approximation. We present a partial kernelization (unbounded weights) with respect to $q + x$, where $x$ is the size of a given vertex cover. Afterwards, we strengthen this result to a proper polynomial kernel (with a worse but still polynomial running time).

\[thm:VCKern\] Let $I = (G, w)$ be a <span style="font-variant:small-caps;">MinPAC</span>-instance where $w \colon A(G) \to Q$ and $Q \in {\mathds{N}}^q$. Given $I$ and a vertex cover $X$ for $G$ of size $x$, one can compute an instance $I'$ of <span style="font-variant:small-caps;">MinPAC</span> with at most ${(q + 1)^{2 x} + x}$ vertices and a value $d \in {\mathds{N}}$ such that $\operatorname{OPT}(I) = \operatorname{OPT}(I') + d$ in $O(\min(\{ x, \log_q n \}) \cdot n + m)$ time.

In order to prove , we first observe that there are some conditions under which a vertex can be included or removed without losing the strong connectivity. Notably, we use to remove “twin” vertices.

\[obs:remv\] Let $G$ be a strongly connected graph with $u \in V(G)$. If there exists a vertex $u' \in V(G)$ with $N^+_G(u) \subseteq N^+_G(u')$ and $N^-_G(u) \subseteq N^-_G(u')$, the graph $G[V(G) \setminus \{ u \}]$ 