Boundaried Kernelization via Representative Sets

Motivated by the question of whether the global matroid-based techniques of Kratsch and Wahlström [13] can also be adapted for local preprocessing, we study the same problems in the boundaried setting. We are able to strengthen several results to polynomial boundaried kernelizations.

The main idea lies in the power of the gammoids and the resulting cut covers $Z$ which contain the vertices of an exponential number of min-cut queries. While Kratsch and Wahlström applied this on gammoids with sources being the terminal set, or an approximate odd cycle transversal, we additionally put in the boundary vertices as sources. As a result, this family of min-cut queries whose optimal answers are all covered by $Z$, contain in particular all possible combinations needed in order to complete an optimal global solution for any forced behavior of the boundary vertices in the solution. For instance, in $s$-multiway cut, where the solution is a vertex set $X$ such that each of the $s$ given terminals $t\in T$ is contained in its own component in $G-X$, we are able to preserve an optimal solution for every choice of putting any boundary vertex either into the solution, the component of some terminal, or some unrelated component. Or in odd cycle transversal, where $G-X$ has to be a bipartite graph, the set $Z$ contains the local part of an optimal solution for every choice of putting $B$ vertices in the solution or one of the two parts of the bipartite graph $G-X$.

Note however for the problem $s$-multiway cut, that, for $G_B$ being the local graph, $T_G$ a set of terminals among $G$-vertices, and $H_B,T_H$ the rest of the global graph with the remaining terminals among the $H$-vertices, if we allow $T_H$ to also contain $B$-vertices, this forces us to be able to adapt to any pair of the boundary vertices to be terminals, and thus we need to store at least some information about the disjoint path sets between any such pair. Since the sizes of these path sets are not bounded, this means that we need to be able to store an unbounded amount of information, which directly rules out any effective preprocessing.

So, the slightly restricted case that we are referring to in Theorem 1 is that we forbid the terminal-part $T_H$ that is unknown for the kernelization, to contain any boundary vertices. This restriction is enough in order to obtain a boundaried kernelization, and it fits with the concept of local kernelization because the terminals in $B$ are known in that setting. (That being said, in general, it is appealing to push to the most general setting for getting a polynomial boundaried kernelization. This includes having the preprocessing be fully independent of possible glued graphs $H_B$.)

Most closely related is the already mentioned work on meta-kernelization via protrusion replacement (subgraphs with constant treewidth and constant boundary size). Inherently, the machinery for that does not lead to any polynomial size bounds, and that is not to be expected. Generally, the perspective of boundaried graphs is essential for dynamic programming on path and tree decompositions (cf. [4]). In that setting, there is no hope for polynomial boundaried kernelizations because it would generalize the (likely) infeasible case of problems parameterized by path/treewidth regarding polynomial kernelization. Instead, our settings have more restrictive structure than small treewidth (as is usual for polynomial kernelization) and we obtain polynomial size bounds.

Fomin et al. [6] use a different form of protrusion for (connected) dominating set[$k$] where they require constant boundary size and a constant local solution size. It is used very differently than our (parameter) local cost, but is certainly reminiscent. Clearly, a small or constant local cost is a natural quality of interest amongst more explicit structural parameters like the size of modulators.

Work by Jansen and Kratsch [10] for preprocessing the feasibility problem of integer linear programs showed how to shrink subsystems with constant boundary size and either constant treewidth or total unimodularity to size polynomial in the domain. This predates the present notion of boundaried kernelization, like protrusion-replacement, but similarly does not yield size polynomial in the boundary size.

We give preliminaries regarding graph problems and boundaried kernelization in Section 2 and restate the tools from representative sets for matroids in Section 3. In Sections 4, 5, 6, and 7 we describe the randomized polynomial boundaried kernelizations for $s$-multiway cut[local solution], deletable terminal multiway cut[local solution], odd cycle transversal[local solution], and vertex cover[oct], respectively. Finally, we conclude in Section 8. Throughout the paper, we denote results by $\star$, if the corresponding proof is omitted and to be found in the full version [2].

We use the usual notion of decision and optimization problems as well as standard graph theoretic notation mostly following Diestel [5]. Our graphs are finite, simple, undirected, loopless, and unweighted, unless explicitly stated otherwise. A mixed graph contains both directed and undirected edges. For a vertex set $V^{\prime }\subseteq V(G)$, we denote by $N_{G,V^{\prime }}(v)$ the set of neighbors of $v$ that are contained in $V^{\prime }$, i.e., $N_{G,V^{\prime }}(v):=N_G(v)\cap V^{\prime }$. For vertex set $W\subseteq V(G)$, we extend this notion to $N_{G,V^{\prime }}(W)$.

A (vertex) annotated graph is a tuple $(G,𝒯)$, where $G$ is an undirected graph and $𝒯$ itself is a tuple of subsets of $V(G)$. A decision or optimization problem on (annotated) graphs consists of instances encoding (annotated) graphs, respectively. A problem on graphs, i.e., without annotation $𝒯$, is also called a pure graph problem. We define the pure graph optimization problems vertex cover and odd cycle transversal in the usual way.

A set $S\subseteq V(G)$ is called a (multiway) cut for a graph $G$ and a set $T=\{t_1,\mathrm{\dots },t_k\}\subseteq V(G)$ of given terminals if in graph $G^{\prime }=G-S$ for every pair $u,v\in T$ there is no path between $u$ and $v$ in $G-S$. More generally, if we are given graph $G$ and a tuple of terminal sets $𝒯=(T_1,\mathrm{\dots },T_k)$, then a cut for $(G,𝒯)$ is a set $S\subseteq V(G)$ such that for any $i\ne j\in [k]$ and any $u\in T_i,v\in T_j$ there is no path between $u$ and $v$ in $G-S$. We remark that unless stated otherwise, a cut $S$ might intersect the set $T$ of terminals, respectively the set ${\bigcup }_{T\in 𝒯}T$ in the general case. A set $S\subseteq V(G)$ is said to be closest to some set $T\subseteq V$ in $G$ if $S$ is the unique $(T,S)$-min cut in $G$, and hence, there exist $|S|$-many vertex-disjoint paths from $T$ to $S$. A $T$-closest cut between $T$ and $S$ is a $(T,S)$-min cut that is closest to $T$. Kratsch and Wahlström [13] describe a simple efficient algorithm for computing a $T$-closest cut. In the minimization problem $s$-multiway cut the value of a solution $x$ for undirected graph $G$ and set $T=\{t_1,\mathrm{\dots },t_s\}$ of terminals, is equal to $|S|$ if $x$ encodes a cut $S$ for $(G,T)$, which is furthermore disjoint from $T$, and $+\mathrm{\infty }$ otherwise. In contrast to this, in the minimization problem deletable terminal multiway cut we are given an arbitrarily large set $T$ of terminals, but now $x$ is allowed to encode a cut $S$ for $(G,T)$ which might intersect the terminal set $T$, in which case the value of $x$ is also equal to $|S|$.

A parameterized problem is a set $Q\subseteq {\mathrm{\Sigma }}^{\ast }\times \mathbb{N}$. For a tuple $(x,\mathrm{\ell })\in {\mathrm{\Sigma }}^{\ast }\times \mathbb{N}$ the number $\mathrm{\ell }$ is called the parameter. For a problem $\mathrm{\Pi }$ (decision or optimization) and minimization problem $\rho$ we define the structurally parameterized problem $\mathrm{\Pi }[\rho ]$, for which it holds that $(x,s,\mathrm{\ell })\in \mathrm{\Pi }[\rho ]$ if and only if $s$ is a feasible solution of value at most $\mathrm{\ell }$ for $\rho$ on $x$ and: (i) for $\mathrm{\Pi }$ being a decision problem, $x\in \mathrm{\Pi }$; (ii) for $\mathrm{\Pi }$ being a minimization problem, $x=(x^{\prime },k)$ for some $k\in \mathbb{N}$ and ${\mathrm{OPT}}_{\mathrm{\Pi }}(x^{\prime })\le k$; (iii) for $\mathrm{\Pi }$ being a maximization problem, $x=(x^{\prime },k)$ and ${\mathrm{OPT}}_{\mathrm{\Pi }}(x^{\prime })\ge k$.

A kernelization for a parameterized problem $Q$ is a polynomial-time algorithm $𝒜$ which is given as input an instance $(x,\mathrm{\ell })$ and outputs an equivalent instance $(x^{\prime },{\mathrm{\ell }}^{\prime })$, i.e., $(x,\mathrm{\ell })\in Q\iff (x^{\prime },{\mathrm{\ell }}^{\prime })\in Q$, such that $|x^{\prime }|$ and ${\mathrm{\ell }}^{\prime }$ are upper bounded by $f(\mathrm{\ell })$ for some computable function $f$. The function $f$ is called the size of the kernelization $𝒜$, and if $f$ is polynomially bounded, then $𝒜$ is called a polynomial kernelization. If there is a probability that the output instance $(x^{\prime },{\mathrm{\ell }}^{\prime })$ is not equivalent to $(x,\mathrm{\ell })$, then $𝒜$ is called a randomized kernelization. In our cases, the error probability will be upper bounded by $𝒪(2^{-\mathrm{\Theta }(|x|)})$. The output instance $(x^{\prime },{\mathrm{\ell }}^{\prime })$ is called a kernel of $(x,\mathrm{\ell })$ and we say that the problem $Q$ admits a (randomized) (polynomial) kernel, if there exists a (randomized) (polynomial) kernelization for $Q$.

A boundaried graph is a special kind of annotated graph $G_B=(G,B)$, where we call $G$ the underlying graph and $B$ the boundary. We define the earlier mentioned problems on boundaried graphs in the same way as on their underlying graphs, i.e., we ignore the boundary for these problems. For two boundaried graphs $G_B,H_C$ we define the operation of gluing these graphs together, denoted by $G_B\oplus H_C$, which results in a new boundaried graph with boundary $B\cup C$ and consisting of the disjoint union of the vertex and edge sets of $G$ and $H$, under the identification of the vertices in $B\cap C$. Throughout this paper we will tacitly assume that $V(G)$ and $V(H)$ intersect exactly at $B\cap C$, in which case the underlying graph of $G_B\oplus H_C$ can simply be seen as the union of each the vertex sets and the edge sets of $G$ and $H$. Clearly, graph gluing is commutative and associative.

Based on regular graph gluing, we additionally define gluing of boundaried graphs with additional vertex annotations, which we will call (vertex) annotated boundaried graphs: For two such annotated boundaried graphs $(G_B,T_1,\mathrm{\dots },T_r)$ and $(H_C,U_1,\mathrm{\dots },U_r)$ for some $r\in \mathbb{N}$ and with $V(G)\cap V(H)\subseteq B\cap C$, the result of $(G_B,T_1,\mathrm{\dots },T_r)\oplus (H_C,U_1,\mathrm{\dots },U_r)$ is the annotated boundaried graph $(G_B\oplus H_C,W_1,\mathrm{\dots },W_r)$ where $W_i=T_i\cup U_i$ for every $i\in [r]$.

We say that the instances $(G_B,𝒯)$ and $(G_B^{\prime },{𝒯}^{\prime })$ are gluing equivalent with respect to an optimization problem $\mathrm{\Pi }$ on annotated graphs and boundary $B$, denoted as $(G_B,𝒯){\equiv }_{\mathrm{\Pi },B}(G_B^{\prime },{𝒯}^{\prime })$, if there exists some constant $\mathrm{\Delta }\in \mathbb{Z}$ such that for every boundaried graph $H_B$ and tuple $𝒰$ of $V(H)$-subsets, it holds that ${\mathrm{OPT}}_{\mathrm{\Pi }}((G_B,𝒯)\oplus (H_B,𝒰))={\mathrm{OPT}}_{\mathrm{\Pi }}((G_B^{\prime },{𝒯}^{\prime })\oplus (H_B,𝒰))+\mathrm{\Delta }$. If $\mathrm{\Pi }$ and $B$ are clear from context, we will omit them and write $\equiv$ instead. The optimization problem $\mathrm{\Pi }$ has finite integer index if the number of equivalence classes of ${\equiv }_{\mathrm{\Pi },B}$ is upper bounded by some function $f(|B|)$. We refer to the full version of the paper for definitions of gluing equivalence and finite index for $\mathrm{\Pi }$ being a decision problem.

Let $\mathrm{\Pi }$ be an optimization or decision problem and $\rho$ a minimization problem, both on annotated graphs. A boundaried kernelization for the parameterized problem $\mathrm{\Pi }[\rho ]$ is a polynomial-time algorithm $𝒜$ which is given as input an annotated boundaried graph $(G_B,𝒯)$ and feasible solution $s$ for $\rho$ on $(G_B,𝒯)$ together with the value $\mathrm{\ell }$ of $s$; and $𝒜$ outputs an annotated boundaried graph $(G_B^{\prime },{𝒯}^{\prime })$, such that $(G_B^{\prime },{𝒯}^{\prime })$ is gluing equivalent to $(G_B,𝒯)$ and the size of $(G_B^{\prime },{𝒯}^{\prime })$ is bounded by $f(|B|+\mathrm{\ell })$ for some computable function $f$. Additionally, if $\mathrm{\Pi }$ is an optimization problem, then $𝒜$ also needs to output the offset $\mathrm{\Delta }$ by which the optimum value for $(G_B,𝒯)\oplus (H_B,𝒰)$ differs from that for $(G_B^{\prime },{𝒯}^{\prime })\oplus (H_B,𝒰)$ for any boundaried graph $H_B$ and tuple $𝒰$ of $V(H)$-subsets. Analogously to (regular) kernelization, we define the size of $𝒜$ and the notions of a (randomized) (polynomial) boundaried kernelization and kernel. By minor adaptation of a result by Antipov and Kratsch [1, Lemma 4] and under the assumption that $\mathrm{\Pi }$ and $\rho$ are $\mathrm{𝖭𝖯}$-optimization problems, the existence of a (randomized) (polynomial) boundaried kernelization for parameterized problem $\mathrm{\Pi }[\rho ]$ also implies the existence of a (randomized) (polynomial) kernelization for $\mathrm{\Pi }[\rho ]$. Additionally we define a boundaried kernelization for $\mathrm{\Pi }[\text{local solution}]$ to be a boundaried kernelization for $\mathrm{\Pi }$ parameterized by itself, i.e., the input is an annotated boundaried graph $(G_B,𝒯)$ and a feasible solution $s$ for $\mathrm{\Pi }$ on $(G_B,𝒯)$, together with the value $\mathrm{\ell }$ of $s$.

We will construct boundaried kernelization by the use of reduction rules. We say that a reduction rule is gluing safe, if it gets as input an instance $(G_B,𝒯)$ and outputs a gluing equivalent instance $(G_B^{\prime },{𝒯}^{\prime })$ and the corresponding shift $\mathrm{\Delta }$ in solution value, if $\mathrm{\Pi }$ is an optimization problem and $\mathrm{\Delta }\ne 0$.

Let $G_B$ denote the graph before applying the reduction rule, and $G_B^{\prime }$ the result thereof. Let $H_B$ be the graph for gluing. Let $T_G$ be the given set of terminals for $G$ (resp. for $G^{\prime }$), and $T_H\subseteq V(H)\setminus B$ the set of terminals given together with $H_B$. Let $T=T_G\cup T_H$ and assume without loss of generality that $|T|=s$. If , we can add isolated terminals to $H$, while $|T|>s$ directly leads to $(G_B\oplus H_B,T)$ having no feasible solution. Likewise, we can assume that no two terminals are adjacent. Let $s_G=|T_G|$ and assume some arbitrary ordering of the terminals, such that the vertices of $T_G$ can be denoted by $t_1,\mathrm{\dots },t_{s_G}$ and those from $T_H$ by $t_{s_G+1},\mathrm{\dots },t_s$.

Let $Y^{\prime }$ be a multiway cut for $T$ in $G_B^{\prime }\oplus H_B$. Since $Y^{\prime }$ does not contain any bypassed vertices, it follows from Lemma 8 that $Y^{\prime }$ is a multiway cut for $T$ in $G_B\oplus H_B$.

Let $Y$ be a multiway cut for $T$ in $G_B\oplus H_B$ without terminal deletion. Thus, no component in $(G_B\oplus H_B)-Y$ contains more than one terminal and, obviously, every terminal $t\in T_G$ is in the same component as $N_G(t)\setminus Y$. Furthermore, any vertex in $B\setminus Y$ shares its component with at most one terminal. Based on this we partition the set $X$ into $(X_0,X_X,X_1,\mathrm{\dots },X_s)$ as follows: $X_X$ contains those $B\setminus T$-vertices that are contained in $Y$ and $X_0$ those that are not connected with any terminal in $(G_B\oplus H_B)-Y$; for each $t_i\in T$ put into $X_i$ every $B\setminus Y$-vertex that is connected with $t_i$ in $(G_B\oplus H_B)-Y$, and if further $t_i$ is contained in $T_G$ then also put all vertices from $N_G(t_i)\setminus Y$ into $X_i$.

Let $F=V(G)\setminus B$. Clearly, $Y\cap F$ is a multiway cut for $(X_1,\mathrm{\dots },X_s)$ in $G-X_X$. By choice of $Z$, construction of $G^{\prime }$ and Lemma 8, there is also a multiway cut $Y^{\ast }\subseteq Z$ of size at most $|Y\cap F|$ for $(X_1,\mathrm{\dots },X_s)$ in $G^{\prime }-X_X$. We will now verify that $Y^{\prime }:=(Y\setminus F)\cup Y^{\ast }$ is a multiway cut for $T$ in $G_B^{\prime }\oplus H_B$ (without terminal deletion). For that, assume for contradiction that there is a path $P$ between distinct terminals $t_{i_1},t_{i_2}\in T$ in $(G_B^{\prime }\oplus H_B)-Y^{\prime }$. Note that no two terminals from $T$ are connected in either $H-Y^{\prime }=H-Y$ or $G^{\prime }-Y^{\prime }$. Thus, the path cannot go only through $H-B$ or $G^{\prime }-B$ and contains vertices from $B\setminus (T\cup Y^{\prime })$. Give these vertices an order along the path in the direction from $t_{i_1}$ to $t_{i_2}$, i.e., $P=(t_{i_1},\mathrm{\dots },x_1,\mathrm{\dots },x_2,\mathrm{\dots },x_p,\mathrm{\dots },t_{i_2})$, where $x_1,\mathrm{\dots },x_p$ are the $B\setminus (T\cup Y^{\prime })$-vertices contained in $P$ and the vertices between $x_i,x_j$ with distinct $i,j\in [p]$ are contained in $(V(G)\cup V(H))\setminus (B\cup T\cup Y^{\prime })$. If the path between $x_i$ and $x_j$ goes through $H-(B\cup Y^{\prime })$, then they need to be in the same part of the earlier partition $(X_0,X_X,X_1,\mathrm{\dots },X_s)$: Since it holds that $H-(B\cup Y^{\prime })=H-(B\cup Y)$, the vertex $x_i$ is connected to $t\in T$ in $(G_B\oplus H_B)-Y$ if and only if $x_j$ is connected to $t$. However, if the path goes through $G^{\prime }-(B\cup Y^{\prime })$ and if, say, $x_i$ is in the part $X_h$ with $t_h\in T_H$, then it might also be the case that $x_j$ is in the part $X_0$, since $Y^{\ast }$ does not have to separate $X_h$-vertices from $X_0$-vertices. Furthermore, if terminal $t_h\in T$ is connected with $x_i$ (either through $H-(B\cup Y^{\prime })$ or $G^{\prime }-(B\cup Y^{\prime })$), then $x_i$ needs to be contained in the part $X_h$. Combining these points we come to the fact that $x_1\in X_{i_1}$ and $x_p\in X_{i_2}$, while at the same time it holds that $x_p\in X_{i_1}\cup X_0$ by the transversal from $x_1$ to $x_p$ through $H-(B\cup Y^{\prime })$ and $G^{\prime }-(B\cup Y^{\prime })$ between consecutive $B$-vertices $x_i,x_{i+1}$ for every $i\in [p-1]$. A contradiction. $◀$

As Reduction Rules 1 and 2 are clearly applicable (the former exhaustively) in polynomial time, it remains to find the cut cover $Z$ for $B\cup {\bigcup }_{t\in T_G}{N}_G(t)$, for which we use Lemma 7. Altogether, this proves Theorem 10, with small failure chance due to the computation of $Z$.

Let $G^{\prime }$ be the resulting graph. Fix $H_B,T_H$. Let $T:=T_G\cup T_H$.

Let $X^{\prime }$ be a solution for $(G_B^{\prime }\oplus H_B,T)$. Obviously, $X^{\prime }$ does not contain any bypassed vertices and thus by Lemma 8 it is also a solution for $(G_B\oplus H_B,T)$.

Let $X$ be a solution for $Q:=G_B\oplus H_B$ with terminal set $T$, such that $|X|$ is minimized but among such $|X\cap T|$ is maximized. Let $X_F:=X\cap F$, $X_0:=X\setminus T$, and $T_0:=T\setminus X$. Further, define the mixed graph $Q^{\ast }$ on the base of $Q$, but with two additional sink-only copies $v^{\prime },v^{\prime \prime }$ for every vertex $v\in V(Q)$. Kratsch [11] has shown that in $Q^{\ast }-(T\cap X)$ there exists a path packing with $|X_0|+2$ paths from $T_0$ to $X_0\cup \{x^{\prime },x^{\prime \prime }\}$ for each $x\in X_0$. Note that this implies existence of a path packing in $G^{\ast }-(T\cap X)$ with $|X_0\cap F|+2$ paths from $(B\cup T_G)\setminus X$ to $(X_0\cap F)\cup \{x^{\prime },x^{\prime \prime }\}$ for each $x\in X_0\cap F$: Take the path packing from $T_0$ to $X_0\cup \{x^{\prime },x^{\prime \prime }\}$ in $Q^{\ast }-(T\cap X)$, throw away any path going to $X_0\setminus F$, and note that the remaining paths are either totally contained in $G^{\ast }[F\cup \{x^{\prime },x^{\prime \prime }\}]$ or must intersect $B\setminus X$. For each path of the latter case we fix its last vertex $u$ contained in $B\setminus X$ and use the subpath from $u$ to $(X_0\cap F)\cup \{x^{\prime },x^{\prime \prime }\}$ for the path packing.

Now we show for any fixed $x\in X_0\cap F$ that $\{x,x^{\prime },x^{\prime \prime }\}$ is contained in ${𝒵}^{\prime }$. Fix the path packing of size $|X_0\cap F|+2$ from $(B\cup T_G)\setminus X$ to $(X_0\cap F)\cup \{x^{\prime },x^{\prime \prime }\}$ in $G^{\ast }-(T\cap X)$ and let $U$ be the set of $B\setminus X$-vertices from which the paths go to $(X_0\cap F)\cup \{x^{\prime },x^{\prime \prime }\}$ without touching $B$ any further. Set $Y:=B\setminus U$ and observe that there exists a path packing of $|X_0\cap F|+|Y|+2$ paths from $B\cup T_G$ to $(X_0\cap F)\cup Y\cup \{x^{\prime },x^{\prime \prime }\}$ (including the length-$0$ path $(y)$ for each $y\in Y$) in $G^{\ast }$, i.e., $\{x,x^{\prime },x^{\prime \prime }\}$ extends $X_x:=((X_0\cap F)-\{x\})\cup Y$ in $ℳ$. Let us make sure that $|X_x|$ is upper bounded by $2|B|+|T_G|-1$, thus leading to the fact that $\{x,x^{\prime },x^{\prime \prime }\}$ is a correct candidate for ${𝒵}^{\prime }$: If it were true that $|X_x|>2|B|+|T_G|-1$, it would follow thereof that $|X_F|>|B|+|T_G|$ and thus that $\tilde{X}:=(X\setminus V(G))\cup B\cup T_G$ is a multiway cut for $Q$ of smaller size, contradicting minimality of $|X|$. For this last point we remark that a potential path between terminals in $Q-\tilde{X}$ would need to be a path between terminals from $T_H\setminus B$ and contained entirely inside of $H-X$, contradicting the fact that $X$ is a multiway cut for $(Q,T)$.

Having seen that $\{x,x^{\prime },x^{\prime \prime }\}$ is a candidate for ${𝒵}^{\prime }$ as an extension of $X_x$, we show that there is no other vertex $v\in F$ which extends $X_x$. Assume for contradiction that such a vertex $v$ exists. First for any $v\in X_0\setminus \{x\}$ it holds that $\{v,v^{\prime },v^{\prime \prime }\}\cap X_x=\{v\}\ne \mathrm{\varnothing }$ and thus that $\{v,v^{\prime },v^{\prime \prime }\}$ does not extend $X_x$. Hence we consider the case that $v\in F\setminus X$. We remark that by choice of $U$ we have that $U\cap X=\mathrm{\varnothing }$, and that each of its vertices $u\in U$ is reachable from some terminal $t\in T$ in $Q-X$, with no two $U$-vertices sharing the terminal. Since by assumption there exist three paths from $B\cup T_G$ to $\{v,v^{\prime },v^{\prime \prime }\}$ and at most one of them goes through $x$, two of these paths go directly through $G-X_x$. In particular this means that these two paths go from $U\cup T_G$ to $\{v,v^{\prime },v^{\prime \prime }\}$, implying that $v$ is connected with two different terminals in $Q-X$, a contradiction to $X$ being a multiway cut for $(Q,T)$.

As a result, for any fixed $x\in X_0\cap F$ it must hold that $\{x,x^{\prime },x^{\prime \prime }\}$ is contained in ${𝒵}^{\prime }$ and thus no $X$-vertices were bypassed while constructing $G^{\prime }$. By Lemma 8 this means that $X$ is also a multiway cut for $(G_B^{\prime }\oplus H_B,T)$. $◀$

Now, Theorem 13 is proven by first exhaustively applying the reduction rules behind Lemma 14 in order to bound $|T_G|$ by $𝒪({(|B|+\mathrm{\ell })}^2)$; and afterwards applying Lemma 5 and Reduction Rule 3 in order to compute the representative set ${𝒵}^{\prime }\subseteq 𝒵$ of size $𝒪({(|B|+|T_G|)}^3)$ and bypass all vertices $v\in F\setminus T_G$ for which $\{v,v^{\prime },v^{\prime \prime }\}$ is not contained in ${𝒵}^{\prime }$. Together this yields our wanted vertex size of $𝒪({(|B|+\mathrm{\ell })}^6)$.

Let $G^{\prime }$ be the resulting graph. Observe that $G^{\prime }-B$ is bipartite as we only added independent edges for the triangles, substituted odd-length paths by edges, and even-length paths by length-2 paths. Construct the graph $\tilde{G}$ from $G^{\prime }$ in the same way as $G^{\ast }$ was constructed from $G$. The following claim is analogous to Lemma 8 and used for our proof.

We only show one direction of the proof here, as the other direction (to be found in the full version) works very similarly.

Let $S^{\prime }$ be an odd cycle transversal for $G_B^{\prime }\oplus H_B$. By Lemma 17 we can divide this solution into an odd cycle transversal $X^{\prime }$ for $H$ and a minimum size cut $C^{\prime }$ between $B_{\sim }$ and $B_{\mathrm{\Delta }}$ in $\tilde{G}-\{x_L,x_R\mid x\in B\cap X^{\prime }\}$. We can assume without loss of generality that none of the vertices created for the substituting paths and cycles are contained in $C^{\prime }$. Hence $C^{\prime }$ only contains vertices from $B_L\cup B_R\cup (F\cap Z)$ and it follows from Claim 19 that $C^{\prime }$ is also a cut between $B_{\sim }$ and $B_{\mathrm{\Delta }}$ in $G^{\ast }-\{x_L,x_R\mid x\in B\cap X^{\prime }\}$. Hence by Lemma 17 there exists an odd cycle transversal of size at most $|S^{\prime }|$ for $G_B\oplus H_B$. $◀$

Hence, we get our randomized polynomial boundaried kernelization for Theorem 16 in the following way. Using Lemma 7, compute a cutset $Z\subseteq V(G^{\ast })$ of size $𝒪({(|B|+\mathrm{\ell })}^3)$ for $B_L\cup B_R$. Afterwards apply Reduction Rule 4 in order to get a gluing equivalent graph $G^{\prime }$ with $𝒪({(|B|+\mathrm{\ell })}^3)$ vertices from $B\cup (F\cap Z)$ and at most $𝒪({(|B|+\mathrm{\ell })}^6)$ vertices for substituting odd cycles at vertices $x\in B$, and even-length paths between vertices from $B\cup (F\cap Z)$.