# Dynamic programming on bipartite tree decompositions

Lars Jaffke, Laure Morelle, Ignasi Sau, Dimitrios Thilikos

► To cite this version:

Lars Jaffke, Laure Morelle, Ignasi Sau, Dimitrios Thilikos. Dynamic programming on bipartite tree decompositions. Journal of Computer and System Sciences, 2026, 156, pp.103722. 10.1016/j.jcss.2025.103722. lirmm-05386282

HAL Id: lirmm-05386282

https://hal-lirmm.ccsd.cnrs.fr/lirmm-05386282v1

Submitted on 27 Nov 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Highlights

## Dynamic programming on bipartite tree decompositions*

Lars Jaffke, Laure Morelle, Ignasi Sau, Dimitrios M. Thilikos

* Bipartite treewidth generalizes both treewidth and the odd cycle transversal number

* Bipartite treewidth is closely related to odd-minors

* An algorithmic framework using bipartite tree decompositions

* Algorithms and lower bounds for a number of problems parameterized by bipartite treewidth
Dynamic programming on bipartite tree decompositions

Lars Jaffke$^{a,1}$, Laure Morelle$^{b,2,3,*}$, Ignasi Sau$^{b,2,3}$, Dimitrios M. Thilikos$^{b,3}$

$^a$Department of Informatics, University of Bergen, Postboks 7803, 5020, Bergen, Norway

$^b$LIRMM, University of Montpellier, CNRS, 161 rue Ada, 34095, Montpellier, France

**Abstract**

We revisit a graph width parameter that we dub *bipartite treewidth* (btw). Bipartite treewidth can be seen as a common generalization of treewidth and the odd cycle transversal number, and is closely related to odd-minors. Intuitively, a *bipartite tree decomposition* is a tree decomposition whose bags induce almost bipartite graphs and whose adhesions contain at most one “bipartite” vertex, while the width of such decomposition measures the number of “non-bipartite” vertices in a bag. We provide **para-NP-completeness** results and develop dynamic programming techniques to solve problems on graphs of small btw. In particular, we show that $K_t$-SUBGRAPH-COVER, WEIGHTED INDEPENDENT SET, ODD CYCLE TRANSVERSAL, and MAXIMUM WEIGHTED CUT are FPT parameterized by btw. We also provide the following dichotomy when $H$ is a 2-connected graph: if $H$ is bipartite, then $H$-{$SUBGRAPH$/$INDUCED-SUBGRAPH$/$ODD-MINOR/$SCATTERED$}-PACKING is **para-NP-complete** parameterized by btw while, if $H$ is non-bipartite, then the problem is solvable in XP-time.

**Keywords:** tree decomposition, bipartite graphs, dynamic programming, odd-minors, packing, maximum cut, vertex cover, independent set, odd cycle transversal

# 1. Introduction

A graph $H$ is said to be an *odd-minor* of a graph $G$ if it can be obtained from $G$ by iteratively removing vertices, edges, and contracting edge cuts. Hadwiger's conjecture [1], which is open since 1943, states that if a graph excludes $K_t$ as a minor, then its chromatic number is at most $t-1$. In 1993, Gerards and Seymour [2] generalized this conjecture to odd-minors, hence drawing attention to odd-minors: the Odd Hadwiger's conjecture states that if a graph excludes $K_t$ as an odd-minor, then its chromatic number is at most $t-1$. Since then, a number of papers regarding odd-minors appeared. Most of them focused to the resolution of the Odd Hadwiger's conjecture (see for instance [3], and [4] for a nice overview of the results), while some others aimed at extending the results of graph minor theory to odd-minors (see for instance [5-7]). In particular, Demaine, Hajiaghayi, and Kawarabayashi [5] provided a structure theorem which essentially states that graphs excluding an odd-minor can be obtained by clique-sums of almost-embeddable graphs and almost bipartite graphs. To prove this, they implicitly proved the following, which is described more explicitly by Tazari [8] (see Subsection 3.3 for the corresponding definitions).

**Proposition 1.1** ([8], adapted from [5]). Let $H$ be a fixed graph and let $G$ be a given $H$-odd-minor-free graph. There exists a fixed graph $H'$, $\kappa, \mu \in \mathbb{N}$ depending only on $H$, and an explicit uniform algorithm that computes a rooted tree decomposition of $G$ such that:

<footnote>*A conference version of this work will appear in the *Proceedings of the 18th International Symposium on Parameterized and Exact Computation (IPEC)*, Amsterdam, the Netherlands, September 2023, volume 285 of LIPIcs, pages 16:1–16:22.</footnote>

<footnote>*Corresponding author</footnote>

<footnote n="1">¹Supported by the Research Council of Norway (No 274526).</footnote>

<footnote n="2">²Supported by the ANR project ELIT (ANR-20-CE48-0008-01).</footnote>

<footnote n="3">³Supported by the French-German Collaboration ANR/DFG Project UTMA (ANR-20-CE92-0027), the ANR project GO-DASse ANR-24-CE48-4377, and by the Franco-Norwegian project PHC AURORA 2024-2025 (Projet n° 51260WL).</footnote>
• the adhesion<fnref n="4" /> of two nodes has size at most $κ$, and

• the torso<fnref n="5" /> of each bag $B$ either consists of a bipartite graph $W_B$ together with $\mu$ additional vertices (bags of Type 1) or is $H'$-minor-free (bags of Type 2).

Furthermore, the following properties hold:

1. Bags of Type 2 appear only in the leaves of the tree decomposition,

2. if $B_2$ is a bag that is a child of a bag $B_1$ in the tree decomposition, then $|B_2 \cap V(W_{B_1})| \le 1$; and if $B_2$ is of Type 1, then $|B_1 \cap V(W_{B_2})| \le 1$ as well,

3. the algorithm runs in time $O_H(|V(G)|^4)$, and

4. the $\mu$ additional vertices of the bags of Type 1, called apex vertices, can be computed within the same running time.

It is worth mentioning that Condition 2 of Proposition 1.1 is slightly stronger than what is stated in [8], but it follows from the proof of [5, Theorem 4.1].

<figure><img src="image_2.png" /><figcaption>Figure 1: Illustration of a bipartite tree decomposition. The blue part induces a bipartite graph, while the additional vertices are depicted in red. This bipartite tree decomposition has width at most $k$ if there are at most $k$ additional vertices in each bag.</figcaption></figure>

If we can solve a problem on graphs admitting a tree decomposition as the one described in Proposition 1.1, we should thus be able to solve this problem on odd-minor-closed graph classes. Minor-closed graph classes are already quite well-understood. Therefore, as a first step toward building a theory for solving problems on odd-minor-closed graph classes, we study in this paper a new type of tree decomposition, which we call *bipartite tree decomposition*, corresponding to the tree decompositions of Proposition 1.1, but where all bags are only of Type 1 (see Figure 1). We also stress that this decomposition has also been implicitly used in [9] and is also introduced, under the same name, in [10]. The width of such tree decompositions is defined as the maximum number of apex vertices in a bag of the decomposition. Naturally, the *bipartite treewidth* of a graph $G$, denoted by $\text{btw}(G)$, is the minimum width over all bipartite tree decompositions of $G$; a formal definition is given in Subsection 3.3. It follows easily from the definition that $\text{btw}(G) = 0$ if and only if $G$ is bipartite (indeed, to prove the sufficiency, just take a single bag containing the whole bipartite graph, with no apex vertices). More generally, for every graph $G$ it holds that $\text{btw}(G) \le \text{oct}(G)$, where $\text{oct}$ denotes the size of a minimum *odd cycle transversal*, that is, a vertex set intersecting every odd cycle. On the other hand, since a bipartite tree decomposition is a tree decomposition whose width is not larger than the maximum size

<footnote n="4">⁴The adhesion of two nodes of a tree decomposition $\mathcal{T}$ is the intersection of the corresponding bags of $\mathcal{T}$.</footnote>

<footnote n="5">⁵The *torso* of a bag *B* in a tree decomposition of a graph *G* is the graph obtained from *G*[*B*] by making a clique out of $B \cap B'$ for each other bag $B'$.</footnote>
of a bag (in each bag, just declare all vertices as apices), for every graph $G$ it holds that $\text{btw}(G) \le \text{tw}(G)+1$, where $\text{tw}$ denotes treewidth. Thus, bipartite treewidth can be seen as a common generalization of treewidth and the odd cycle transversal number. Hence, an FPT-algorithm parameterized by $\text{btw}$ should generalize both FPT-algorithms parameterized by $\text{tw}$ and by $\text{oct}$. Since our goal is to develop a theory for solving problems related to odd-minors, the first prerequisite is that bipartite treewidth is closed under odd-minors. Fortunately, this is indeed the case (cf. Lemma 3.2). Interestingly, this would not be true anymore if, in Condition 2 of Proposition 1.1, the considered intersections were required to be upper-bounded by some integer larger than one (cf. Lemma 3.3).

This type of tree decomposition has already been used implicitly in order to solve ODD CYCLE TRANSVERSAL parameterized by the solution size by Kawarabayashi and Reed [9]. Independently of our work, Campbell, Gollin, Hendrey, and Wiederrecht [10] are also currently studying bipartite tree decompositions. In particular, they provide universal obstructions characterizing bounded $\text{btw}$ in the form of a “grid theorem” (actually the result of [10] apply in the much more general setting of undirected group labeled graphs). They also designed an FPT-approximation algorithm that can construct a bipartite tree decomposition in time $g(k) \cdot n^4 \log n$ (cf. Proposition 3.1). This FPT-approximation is an important prerequisite for our algorithmic results as it permits us to assume that, for the implementation of our algorithms, some (approximate) bipartite tree decomposition is provided in advance.

Our aim is to provide a general framework for the design of dynamic programming algorithms on bipartite tree decompositions and, more generally, on a broader type of decompositions that we call *1-$\mathcal{H}$-tree decompositions*. These decompositions generalize bipartite tree decompositions, in the sense that the role of bipartite graphs is replaced by a general graph class $\mathcal{H}$.

**Our results.** In this article we formally introduce bipartite treewidth and bipartite tree decompositions (noticing that they were implicitly already used before, as discussed above). We then focus on the complexity of various problems when the bipartite treewidth of the input graph is taken as a parameter. In particular, we show the following (cf. Table 1):

* While a graph with $\text{btw}$ at most $k$ is $(k+2)$-colorable (Lemma 6.1), 3-COLORING is NP-complete even on graphs of $\text{oct}$ of size three (Lemma 6.2), and thus $\text{btw}$ at most three.

* $K_t$-SUBGRAPH-COVER, WEIGHTED VERTEX COVER/INDEPENDENT SET, ODD CYCLE TRANSVERSAL, and MAXIMUM WEIGHTED CUT are FPT parameterized by $\text{btw}$ (cf. Subsection 4.4). In particular, our FPT-algorithms extend the domain where these well-studied problems can be solved in polynomial time to graphs that are “locally close to being bipartite”. Furthermore, as $\text{btw}(G) \le \text{oct}(G)$ for any graph $G$, we think that the fact that ODD CYCLE TRANSVERSAL is FPT parameterized by $\text{btw}$ is relevant by itself, as it generalizes the well-known FPT-algorithms parameterized by the solution size [11, 12].

* Let $H$ be a 2-connected graph. For each of the $H$-(INDUCED-)SUBGRAPH-PACKING, $H$-SCATTERED-PACKING, and $H$-ODD-MINOR-PACKING problems (cf. Section 5 for the definitions), we obtain the following complexity dichotomy: if $H$ is bipartite, then the problem is para-NP-complete parameterized by $\text{btw}$ (in fact, even for $\text{btw} = 0$), and if $H$ is non-bipartite, then the problem is solvable in XP-time. The hardness results are presented in Subsection 6.3 and the XP-algorithms in Section 5.

* In view of the definition of bipartite tree decompositions, it seems natural to consider any graph class $\mathcal{H}$, instead of bipartite graphs, as the “free part” of the bags. This leads to the more general definition of *1-$\mathcal{H}$-tree decomposition* and *1-$\mathcal{H}$-treewidth* (cf. Subsection 3.3), with $1-\{\emptyset\}$-treewidth being equivalent to the usual treewidth and $1-$*B*-treewidth being the bipartite treewidth if $\mathcal{B}$ is the class of bipartite graphs. We introduce these more general definitions because our dynamic programming technologies easily extend to $1-$*H*-treewidth. It also seems natural to generalize by allowing any number $q$ of “bipartite vertices” in the adhesion, instead of just one. It corresponds, in Figure 1, to replacing the “$\le 1$” with “$\le q$”. For $q = 0$, this corresponds to the *H*-treewidth defined in [13] (see also [14, 15] on
the study of $\mathcal{H}$-treewidth for several instantiations of $\mathcal{H}$). However, as mentioned above, while 1-$\mathcal{B}$-treewidth is closed under odd-minors (Lemma 3.2), this is not the case anymore for $q \ge 2$ (Lemma 3.3). For $q \ge 2$, some problems remain intractable even when $H$ is not bipartite. As an illustration of this phenomenon, we prove that $H$-SCATTERED-PACKING (where there cannot be an edge in $G$ among the copies of $H$ to be packed) is para-NP-complete parameterized by $q$-$\mathcal{B}$-treewidth for $q \ge 2$ even if $H$ is not bipartite (Lemma 6.7).

In the statements of the running time of our algorithms, we always let $n$ (resp. $m$) be the number of vertices (resp. edges) of the input graph of the considered problem.

<table><caption>Table 1: Summary of the results obtained in this article, where $k$ is the bipartite treewidth of the input graph.</caption><thead><tr><th>Problem</th><th>Complexity</th><th>Constraints on H/Running time</th></tr></thead><tbody><tr><td>H-MINOR-COVER [16]<br>H(-INDUCED)-SUBGRAPH/<br>ODD-MINOR-COVER [16] and<br>H(-INDUCED)-SUBGRAPH/<br>H(-ODD)-MINOR-PACKING<br>H-SCATTERED-PACKING</td><td>para-NP-complete,<br>k = 0</td><td>H containing P<sub>3</sub> as a subgraph<br>H bipartite containing P<sub>3</sub> as a subgraph<br>H 2-connected bipartite with |V(H)| &ge; 2</td></tr><tr><td>3-COLORING</td><td>para-NP-complete,<br>k = 3</td><td></td></tr><tr><td>K<sub>t</sub>-SUBGRAPH-COVER<br>WEIGHTED INDEPENDENT SET<br>ODD CYCLE TRANSVERSAL<br>MAXIMUM WEIGHTED CUT</td><td>FPT</td><td>O(2<sup>k</sup> &middot; (k<sup>t</sup> &middot; (n + m) + m<sup>1+o(1)</sup>))<br>O(2<sup>k</sup> &middot; (k &middot; (k + n) + m<sup>1+o(1)</sup>))<br>O(3<sup>k</sup> &middot; (m + k<sup>2</sup> &middot; n)<sup>1+o(1)</sup>)<br>O(2<sup>k</sup> &middot; (k &middot; (k + n) + n<sup>O(1)</sup>))</td></tr><tr><td>H-SUBGRAPH-PACKING<br>H-INDUCED-SUBGRAPH-PACKING<br>H-SCATTERED-PACKING<br>H-ODD-MINOR-PACKING</td><td>XP</td><td>H non-bipartite 2-connected<br>n<sup>O(k)</sup></td></tr></tbody></table>

**Related results.** Other types of tree decompositions integrating some “free bipartite parts” have been defined recently. As we already mentioned, Eiben, Ganian, Hamm, and Kwon [13] defined $\mathcal{H}$-treewidth for a fixed graph class $\mathcal{H}$. The $\mathcal{H}$-treewidth of a graph $G$ is essentially the minimum treewidth of the graph induced by some set $X \subseteq V(G)$ such that the connected components of $G \setminus X$ belong to $\mathcal{H}$, and is equal to 0-$\mathcal{H}$-treewidth minus one (cf. Subsection 3.3). In particular, when $\mathcal{H}$ is the class of bipartite graphs $\mathcal{B}$, Jansen and de Kroon [14] provided an FPT-algorithm to test whether the $\mathcal{B}$-treewidth of a graph is at most $k$.

Recently, as a first step to provide a systematic theory for odd-minors, Gollin and Wiederrecht [17] defined the $\mathcal{H}$-blind-treewidth of a graph $G$, where $\mathcal{H}$ is a property of annotated graphs$^6$. Then the $\mathcal{H}$-blind-treewidth is the smallest $k$ such that $G$ has a tree decomposition where every bag $B$ such that $(G, B) \notin \mathcal{H}$ has size at most $k$. For the case where $C$ consists of every $(G, X)$ where every odd cycle in $H$ has at most one vertex in $X$, we obtain the $C$-blind-treewidth, for which [17] gives an analogue of the Grid Exclusion Theorem [18, 19] under the odd-minor relation. Moreover, [17] provides an FPT-algorithm for INDEPENDENT SET parameterized by $C$-blind-treewidth. The authors of [17] prove that the bipartite-blind treewidth of a graph $G$ is lower-bounded by a function of the maximum treewidth over all non-bipartite blocks of $G$. This immediately implies that bipartite-blind treewidth is lower-bounded by bipartite treewidth. Hence, our FPT-algorithm for INDEPENDENT SET is more general than the one in [17]. Independently of our work, [10] presents an FPT-algorithm to solve ODD CYCLE TRANSVERSAL parameterized by btw in time $f(btw) \cdot n^4 \log n$

<footnote>$^6$An annotated graph is a pair $(G, X)$ where $G$ is a graph and $X \subseteq V(G)$.</footnote>
(in fact, they solve a more general group labeled problem). Our algorithm for ODD CYCLE TRANSVERSAL (cf. Corollary 4.4), which runs in time $O(3^{btw} \cdot btw^3 \cdot n \cdot m)$, is considerably faster.

**Organization of the paper.** In Section 2 we provide an overview of our techniques. In Section 3 we give basic definitions on graphs and we define $q$-H-treewidth. In Section 4 we define a *nice reduction*, give a general dynamic programming algorithm to obtain FPT-algorithms, and apply it to $K_t$-SUBGRAPH-COVER, WEIGHTED INDEPENDENT SET/ VERTEX COVER, ODD CYCLE TRANSVERSAL, and MAXIMUM WEIGHTED CUT. In Section 5 we provide another dynamic programming scheme to solve H-SUBGRAPH-PACKING and H-ODD-MINOR-PACKING in XP-time. In Section 6 we provide our hardness results. Finally, we present several questions for further research in Section 7.

## 2. Overview of our techniques

In this section we present an overview of the techniques that we use to obtain our results.

### 2.1. *Dynamic programming algorithms*

Compared to dynamic programming on classical tree decompositions, there are two main difficulties for doing dynamic programming on (rooted) bipartite tree decompositions. The first one is that the bags in a bipartite tree decomposition may be arbitrarily large, which prevents us from applying typical brute-force approaches to define table entries. The second one, and apparently more important, is the lack of an upper bound on the number of children of each node of the decomposition. Indeed, unfortunately, a notion of “nice bipartite tree decomposition” preserving the width (even approximately) does not exist (cf. Lemma 3.4). We discuss separately the main challenges involved in our FPT-algorithms and in our XP-algorithms.

#### 2.1.1. FPT-algorithms

In fact, in order to obtain FPT-algorithms parameterized by btw, for most of the considered problems, it would be enough to bound the number of children as a function of btw, but we were not able to come up with a general technique that achieves this property (cf. Lemma 3.4). For particular problems, however, we can devise ad-hoc solutions. Namely, for $K_t$-SUBGRAPH-COVER, WEIGHTED VERTEX COVER/INDEPENDENT SET, ODD CYCLE TRANSVERSAL, and MAXIMUM WEIGHTED CUT parameterized by btw, we overcome the above issue by managing to replace the children with constant-sized bipartite gadgets. More specifically, we guess an annotation of the “apex” vertices of each bag $t$, whose number is bounded by btw, that essentially tells which of these vertices go to the solution or not (with some extra information depending on each particular problem; for instance, for ODD CYCLE TRANSVERSAL, we also guess the side of the bipartition of the non-solution vertices). Having this annotation, each adhesion of the considered node $t$ with a child contains, by the definition of bipartite tree decompositions, at most one vertex $v$ that is not annotated. At this point, we crucially observe that, for the considered problems, we can make a local computation for each child, independent from the computations at other children, depending only on the values of the optimum solutions at that child that are required to *contain* or to *exclude* $v$ (note that we need to be able to keep this extra information at the tables of the children). Using the information given by these local computations, we can replace the children of $t$ by constant-sized bipartite gadgets (sometimes empty) so that the newly built graph, which we call a *nice reduction*, is an equivalent instance modulo some constant. If a nice reduction can be efficiently computed for a problem $\Pi$, then we say that $\Pi$ is a *nice problem* (cf. Subsection 4.1). The newly modified bag has bounded oct, so we can then use an FPT-algorithm parameterized by oct to find the optimal solution with respect to the guessed annotation.

**An illustrative example.** Before entering into some more technical details and general definitions, let us illustrate this idea with the WEIGHTED VERTEX COVER problem. The formal definition of bipartite tree decomposition can be found in Subsection 3.3 (in fact, for the more general setting of 1-H-treewidth). For this informal explanation, it is enough to suppose that we want to compute the dynamic programming tables at a bag associated with a node $t$ of the rooted tree decomposition, and that the vertices of the bag at $t$ are
partitioned into two sets: $\beta(t)$ induces a bipartite graph and its complement, denoted by $\alpha(t)$, corresponds to the apex vertices, whose size is bounded by the parameter btw. The first step is to guess, in time at most $2^{\text{btw}}$, which vertices in $\alpha(t)$ belong to the desired minimum vertex cover. After such a guess, all the vertices in $\alpha(t)$ can be removed from the graph, by also removing the neighborhood of those that were not taken into the solution. The definition of bipartite tree decomposition implies that, in each adhesion with a child of the current bag, there is at most one "surviving" vertex. Let $v$ be such a vertex belonging to the adhesion with a child $t'$ of $t$. Suppose that, inductively, we have computed in the tables for $t'$ the following two values, subject to the choice that we made for $\alpha(t)$: the minimum weight $w_v$ of a vertex cover in the graph below $t'$ that contains $v$, and the minimum weight $w_{\bar{v}}$ of a vertex cover in the graph below $t'$ that does not contain $v$. Then, the trick is to observe that, having these two values at hand, we can totally forget the graph below $t'$: it is enough to delete this whole graph, except for $v$, and attach a new pendant edge $vu$, where $u$ is a new vertex, such that $v$ is given weight $w_v$ and $u$ is given weight $w_{\bar{v}}$. It is easy to verify that this gadget mimics, with respect to the current bag, the behavior of including vertex $v$ or not in the solution for the child $t'$. Adding this gadget for every child results in a bipartite graph, for which we can just solve WEIGHTED VERTEX COVER in polynomial time using a classical algorithm [27], and add the returned weight to our tables. The running time of this whole procedure, from the leaves to the root of the decomposition, is clearly FPT parameterized by the bipartite treewidth of the input graph.

**Extensions and limitations.** The algorithm sketched above is problem-dependent, in particular the choice of the gadgets for the children, and the deletion of the neighborhood of the vertices chosen in the solution. Which type of replacements and reductions can be afforded in order to obtain an FPT-algorithm for bipartite treewidth? For instance, concerning the gadgets for the children, as far as the considered problem can be solved in polynomial time on bipartite graphs, we could attach to the “surviving” vertices an arbitrary bipartite graph instead of just an edge. If we assume that the considered problem is FPT parameterized by oct (which is a reasonable assumption, as btw generalizes oct), then one could think that it may be sufficient to devise gadgets with bounded oct. Unfortunately, this will not work in general. Indeed, even if each of the gadgets has bounded oct (take, for instance, a triangle), since we do not have any upper bound, in terms of btw, on the number of children (hence, the number of different adhesions), the resulting graph after the gadget replacement may have unbounded oct. In order to formalize the type of replacements and reductions that can be allowed, we introduce in Section 4 the notions of *nice reduction* and *nice problem*. Additional insights into these definitions, which are quite lengthy, are provided in Subsection 4.1.

Another sensitive issue is that of “guessing the vertices into the solution”. While this is quite simple for WEIGHTED VERTEX COVER (either a vertex is in the solution, or it is not), for some other problems we may have to guess a richer structure in order to have enough information to combine the tables of the children into the tables of the current bag. This is the reason why, in the general dynamic programming scheme that we present in Section 4, we deal with *annotated problems*, i.e., problems that receive as input, apart from a graph, a collection of annotated sets in the form of a partition $\mathcal{X}$ of some $X \subseteq V(G)$. For instance, for WEIGHTED VERTEX COVER, we define its *annotated extension*, which we call ANNOTATED WEIGHTED VERTEX COVER, that takes as input a graph $G$ and two disjoint sets $R$ and $S$ of vertices of $G$, and asks for a minimum vertex cover $S^*$ such that $S \subseteq S^*$ and $S^* \cap R = \emptyset$.

**General dynamic programming scheme.** Our general scheme essentially says that if a problem $\Pi$ has an annotated extension $\Pi'$ that is

* a nice problem and

* solvable in FPT-time parameterized by oct,

then $\Pi$ is solvable in FPT-time parameterized by btw. More specifically, it is enough to prove that $\Pi'$ is solvable in time $f(|X|) \cdot n^{O(1)}$ on an instance $(G, \mathcal{X})$ such that $G \setminus X$ is bipartite, where $\mathcal{X}$ is a partition of $X$ corresponding to the annotation. This general dynamic programming algorithm works in a wider setting, namely for a general graph class $\mathcal{H}$ that plays the role of bipartite graphs, with the additional condition that the annotated extension $\Pi'$ is “$\mathcal{H}$-nice”; cf. Lemma 4.1 for the details.
**Applications.** We then apply this general framework to obtain parameterized algorithms for several problems parameterized by bipartite treewidth. For each of $K_t$-SUBGRAPH-COVER (Subsection 4.4.1), WEIGHTED VERTEX COVER / INDEPENDENT SET (Subsection 4.4.2), ODD CYCLE TRANSVERSAL (Subsection 4.4.3), and MAXIMUM WEIGHTED CUT (Subsection 4.4.4), we prove that the problem has an annotated extension that is 1) nice and 2) solvable in FPT-time parameterized by oct, as discussed above.

To prove that an annotated problem has a nice reduction, we essentially use two ingredients. Given two compatible bounded graphs $\mathbf{F}$ and $\mathbf{G}$ with boundary $X$ (a bounded graph is essentially a graph along with some labeled vertices that form a boundary, see the formal definition in Subsection 3.4), an annotated problem is usually nice if the following hold:

* (Gluing property) Given that we have guessed the annotation $\mathcal{X}$ in the boundary $X$, a solution compatible with the annotation is optimal in the graph $\mathbf{F} \oplus \mathbf{G}$ obtained by gluing $\mathbf{F}$ and $\mathbf{G}$ if and only if it is optimal in each of the two glued graphs. In this case, it means that the optimum on $(\mathbf{F} \oplus \mathbf{G}, \mathcal{X})$ is equal to the optimum on $(F, \mathcal{X})$ modulo some constant depending only on $G$ and $\mathcal{X}$.

* (Gadgetization) Given that we have guessed the annotation in the boundary $X \setminus \{v\}$ for some vertex $v$ in $X$, there is a small bounded graph $G'$, that is bipartite (maybe empty), such that the optimum on $(\mathbf{F} \oplus \mathbf{G}, \mathcal{X})$ is equal to the optimum on $(\mathbf{F} \oplus \mathbf{G}', \mathcal{X})$ modulo some constant depending only on $G$ and $\mathcal{X}$.

The gluing property seems critical to show that a problem is nice. This explains why we solve $\mathbf{H}$-SUBGRAPH-COVER only when $H$ is a clique. For any graph $H$, ANNOTATED $\mathbf{H}$-SUBGRAPH-COVER is defined similarly to ANNOTATED WEIGHTED VERTEX COVER by specifying vertices that must or must not be taken in the solution. If $H$ is a clique, then we crucially use the fact that $H$ is a subgraph of $\mathbf{F} \oplus \mathbf{G}$ if and only if it is a subgraph of either $F$ or $G$ to prove that ANNOTATED $\mathbf{H}$-SUBGRAPH-COVER has the gluing property. However, we observe that if $H$ is not a clique, then ANNOTATED $\mathbf{H}$-SUBGRAPH-COVER does not have the gluing property (see Lemma 4.3). This is the main difficulty that we face to solve $\mathbf{H}$-SUBGRAPH-COVER in the general case.

Note also that if we define in a similar fashion the annotated extension of ODD CYCLE TRANSVERSAL (that is, a set $S$ of vertices contained in the solution and a set $R$ of vertices that do not belong to the solution), then we can prove that this annotated extension does not have the gluing property. However, if we define ANNOTATED ODD CYCLE TRANSVERSAL as the problem that takes as input a graph $G$ and three disjoint sets $S, X_1, X_2$ of vertices of $G$ and aims at finding an odd cycle transversal $S^*$ of minimum size such that $S \subseteq S^*$ and $X_1$ and $X_2$ are on different sides of the bipartition obtained after removing $S^*$, then ANNOTATED ODD CYCLE TRANSVERSAL does have the gluing property (see Lemma 4.9).

For MAXIMUM WEIGHTED CUT, the annotation is pretty straightforward: we use two annotation sets $X_1$ and $X_2$, corresponding to the vertices that will be on each side of the cut. It is easy to see that this annotated extension has the gluing property.

Finding the right gadgets is the main difficulty to prove that a problem is nice. As explained above, for ANNOTATED WEIGHTED VERTEX COVER, we replace the bounded graph $\mathbf{G}$ by an edge that simulates the behavior of $G$ with respect to $v$, which is the only vertex that interest us (see Lemma 4.7). For ANNOTATED MAXIMUM WEIGHTED CUT, if $\mathcal{X} = (X_1, X_2)$, the behavior of $G$ can be simulated by an edge between $v$ and a vertex in $X_1$ of weight equal to the optimum on $(G, (X_1, X_2 \cup \{v\}))$ and an edge between $v$ and a vertex in $X_2$ of weight equal to the optimum on $(G, (X_1 \cup \{v\}, X_2))$ (see Lemma 4.14). For ANNOTATED $K_t$-SUBGRAPH-COVER, if $\mathcal{X} = (R, S)$, depending on the optimum on $(G, (R \cup \{v\}, S))$ and the one on $(G, (R, S \cup \{v\}))$, we can show that the optimum on $(\mathbf{F} \oplus \mathbf{G}, \mathcal{X})$ is equal to the optimum on $(F, \mathcal{X})$ or $(F \setminus \{v\}, \mathcal{X})$ modulo some constant (see Lemma 4.4). For ANNOTATED ODD CYCLE TRANSVERSAL, if $\mathcal{X} = (S, X_1, X_2)$, we can show that the optimum on $(\mathbf{F} \oplus \mathbf{G}, \mathcal{X})$ is equal modulo some constant to the optimum on either $(F, \mathcal{X})$, or $(F \setminus \{v\}, \mathcal{X})$, or $(F', \mathcal{X})$, where $F'$ is obtained from $F$ by adding an edge between $v$ and either a vertex of $X_1$ or a vertex of $X_2$ (see Lemma 4.10).

Finally, let us now mention some particular ingredients used to prove that the considered annotated problems are solvable in time $f(|X|) \cdot n^{O(1)}$ on an instance $(G, \mathcal{X})$ such that $G \setminus X$ is bipartite, where
X is a partition of a vertex set X corresponding to the annotation. For ANNOTATED $K_t$-SUBGRAPH-COVER and ANNOTATED WEIGHTED VERTEX COVER, this is simply a reduction to (WEIGHTED) VERTEX COVER on bipartite graphs. For ODD CYCLE TRANSVERSAL, we adapt the algorithm of Reed, Smith, and Vetta [11] that uses iterative compression to solve ANNOTATED ODD CYCLE TRANSVERSAL in FPT-time parameterized by oct, so that it takes annotations into account (Lemma 4.12). As for MAXIMUM WEIGHTED CUT parameterized by oct, the most important trick is to reduce to a $K_5$-odd-minor-free graph, and then use known results of Grötschel and Pulleyblank [22] and Guenin [23] to solve the problem in polynomial time (Proposition 4.1).

### 2.1.2. XP-algorithms

We now sketch some of the basic ingredients of the XP-algorithms that we present in Section 5 for $H$-(INDUCED-)SUBGRAPH/ODD-MINOR/SCATTERED-PACKING. The main observation is that, if $H$ is 2-connected and non-bipartite, since the “non-apex” part of each bag is bipartite and $H$ is non-bipartite, in any $H$-subgraph/induced/scattered/odd-minor-packing and every bag of the decomposition, there are at most btw occurrences of $H$ that intersect that bag. We thus guess these occurrences, and how they intersect the children, which allows us to reduce the number of children by just deleting those not involved in the packing. The guess of these occurrences is the dominant term in the running time of the resulting XP-algorithm using this method. Note that for $H$-(INDUCED)-SUBGRAPH/SCATTERED-PACKING, we can indeed easily guess those occurrences in XP-time parameterized by btw, as the total size of the elements of the packing intersecting a given bag is bounded by a function of btw and $H$. However, for $H$-ODD-MINOR-PACKING this is not the case anymore, as an element of the packing may contain an arbitrary number of vertices in the bipartite part of a bag. We overcome this issue as follows. The existence of an $H$-odd-minor is equivalent to the existence of a so-called *odd $H$-expansion*, which is essentially a collection of trees connected by edges preserving the appropriate parities of the resulting cycles (cf. Lemma 3.1). In an odd $H$-expansion, the *branch vertices* are those that have degree at least three, or that are incident to edges among different trees (cf. Subsection 5.2). Note that, in an odd $H$-expansion, the number of branch vertices depends only on $H$. Equipped with this property, we first guess, at a given bag, the branch vertices of the packing that intersect that bag. Note that this indeed yields an XP number of choices, as required. Finally, for each such choice, we use an FPT-algorithm of Kawarabayashi, Reed, and Wollan [7] solving the PARITY $k$-DISJOINT PATHS to check whether the guessed packing exists or not. This approach is formalized in Lemma 5.3.

It is worth mentioning that, as will be discussed in Section 7, we leave as an open problem the existence of FPT-algorithms for the above packing problems parameterized by btw.

### 2.2. Hardness results

Finally, we discuss some of the tools that we use to obtain the para-NP-completeness results summarized in Table 1, which can be found in Section 6. We present a number of different reductions, some of them consisting of direct simple reductions, such as the one we provide for 3-COLORING in Lemma 6.2.

Except for 3-COLORING, all the considered problems fall into two categories: covering or packing problems. For the first family (cf. Subsection 6.2), the para-NP-completeness is an immediate consequence of a result of Yannakakis [16] that characterizes hereditary graph classes $\mathcal{G}$ for which VERTEX DELETION TO $\mathcal{G}$ on bipartite graphs is polynomial-time solvable and those for which VERTEX DELETION TO $\mathcal{G}$ remains NP-complete (cf. Proposition 6.1).

For the packing problems (cf. Subsection 6.3), we do not have such a general result as for the covering problems, and we provide several reductions for different problems. For instance, we prove in Lemma 6.3 that if $H$ is a bipartite graph containing $P_3$ as a subgraph, then $H$-SUBGRAPH-PACKING and $H$-INDUCED-SUBGRAPH-PACKING are NP-complete on bipartite graphs. The proof of Lemma 6.3 consists of a careful analysis and a slight modification of a reduction of Kirkpatrick and Hell [24] for the problem of partitioning the vertex set of an input graph $G$ into subgraphs isomorphic to a fixed graph $H$. The hypothesis about containing $P_3$ is easily seen to be tight. We derive from Lemma 6.3 a similar result for $H$-MINOR-PACKING in Lemma 6.4. Given that odd-minors preserve cycle parity (Lemma 3.1), when $H$ is bipartite, $H$-ODD-MINOR-PACKING and $H$-MINOR-PACKING are the same problem on bipartite graphs (Lemma 6.5). Hence, the same hardness result holds for $H$-ODD-MINOR-PACKING when $H$ is bipartite and contains $P_3$ as a subgraph.
In Lemma 6.6 we prove that, if $H$ is a 2-connected bipartite graph with at least one edge, then $H$-SCATTERED-PACKING is NP-complete on bipartite graphs, by a simple reduction from the INDUCED MATCHING on bipartite graphs, which is known to be NP-complete [25].

Finally, in Lemma 6.7 we prove that if $H$ is a 2-connected graph containing an edge and $q \in \mathbb{N}_{\ge 2}$, then $H$-SCATTERED-PACKING is para-NP-complete parameterized by $q$-B-treewidth. In fact, this reduction is exactly the same as the one of Lemma 6.6, with the extra observation that, if $G'$ is the graph constructed in the reduction, then the “bipartite” treewidth of $G'$ is at most the one of $H$ for $q \ge 2$.

### 3. Definitions

In this section we give some definitions and preliminary results. Basic definitions are given in Subsection 3.1. Odd-minors are defined in Subsection 3.2. Treewidth, bipartite treewidth, and other treewidth-like parameters are defined in Subsection 3.3. Finally, bounded graphs are defined in Subsection 3.4.

#### 3.1. Basic definitions

**Sets and integers.** We denote by $\mathbb{N}$ the set of non-negative integers. Given two integers $p$ and $q$, the set $[p,q]$ contains every integer $r$ such that $p \le r \le q$. For an integer $p \ge 1$, we set $[p] = [1,p]$ and $\mathbb{N}_{\ge p} = \mathbb{N} \setminus [0,p-1]$. For a set $S$, we denote by $2^S$ the set of all subsets of $S$ and, given an integer $r \in [|S|]$, we denote by $\binom{S}{r}$ the set of all subsets of $S$ of size exactly $r$.

**Parameterized complexity.** A parameterized problem is a language $L \subseteq \Sigma^* \times \mathbb{N}$, where $\Sigma^*$ is a set of strings over a finite alphabet $\Sigma$. An input of a parameterized problem is a pair $(x, k)$, where $x$ is a string over $\Sigma$ and $k \in \mathbb{N}$ is a parameter. A parameterized problem is fixed-parameter tractable (or FPT) if it can be solved in time $f(k) \cdot |x|^{O(1)}$ for some computable function $f$. A parameterized problem is XP if it can be solved in time $f(k) \cdot |x|^{g(k)}$ for some computable functions $f$ and $g$. A parameterized problem is para-NP-complete if it is NP-complete for some fixed value $k$ of the parameter.

**Partitions.** Given $p \in \mathbb{N}$, a *p-partition* of a set $X$ is a tuple $(X_1, \dots, X_p)$ of pairwise disjoint subsets of $X$ such that $X = \cup_{i \in [p]} X_i$. We denote by $\mathcal{P}_p(X)$ the set of all *p-partitions* of $X$. Given a partition $\mathcal{X} \in \mathcal{P}_p(X)$, its domain $X$ is also denoted as $\cup \mathcal{X}$. A *partition* is a *p-partition* for some $p \in \mathbb{N}$. Note that here, we allow empty sets in a *p-partition* and that the order matters. Given $Y \subseteq X$, $\mathcal{X} = (X_1, \dots, X_p) \in \mathcal{P}_p(X)$, and $\mathcal{Y} = (Y_1, \dots, Y_p) \in \mathcal{P}_p(Y)$, we say that $\mathcal{Y} \subseteq \mathcal{X}$ if $Y_i \subseteq X_i$ for each $i \in [p]$. Given a set $U$, two subsets $X, A \subseteq U$, and $\mathcal{X} = (X_1, \dots, X_p) \in \mathcal{P}_p(X)$, $\mathcal{X} \cap A$ denotes the partition $(X_1 \cap A, \dots, X_p \cap A)$ of $X \cap A$.

**Functions.** Given two sets $A$ and $B$, and two functions $f, g: A \to 2^B$, we denote by $f \cup g$ the function that maps $x \in A$ to $f(x) \cup g(x) \in 2^B$. Let $f: A \to B$ be an injection. Let $K \subseteq B$ be the image of $f$. By convention, if $f$ is referred to as a bijection, it means that $f$ maps $A$ to $K$. Given a function $w: A \to \mathbb{N}$, and $A' \subseteq A$, $w(A') = \sum_{x \in A'} w(x)$.

**Basic concepts on graphs.** All graphs considered in this paper are undirected, finite, and without loops or parallel edges. We use standard graph-theoretic notation and we refer the reader to [26] for any undefined terminology. For convenience, we use $uv$ instead of $\{u, v\}$ to denote an edge of a graph. Let $G$ be a graph. In the rest of this paper we always use $n$ for the cardinality of $V(G)$, and $m$ for the cardinality of $E(G)$, where $G$ is the input graph of the problem under consideration. For $S \subseteq V(G)$, we set $G[S] = (S, E \cap \binom{S}{2})$ and use the shortcut $G \setminus S$ to denote $G[V(G) \setminus S]$. Given a vertex $v \in V(G)$, we denote by $N_G(v)$ the set of vertices of $G$ that are adjacent to $v$ in $G$. Moreover, given a set $A \subseteq V(G)$, $N_G(A) = \cup_{v \in A} N_G(v) \setminus A$. For $k \in \mathbb{N}$, we denote by $P_k$ the path with $k$ vertices, and we say that $P_k$ has length $k-1$ (i.e., the length of a path is its number of edges). We denote by $cc(G)$ the set of connected components of a graph $G$. For $A, B \subseteq V(G)$, $E(A, B)$ denotes the set of edges of $G$ with one endpoint in $A$ and the other in $B$. We say that $E' \subseteq E(G)$ is an *edge cut* of $G$ if there is a partition $(A, B)$ of $V(G)$ such that $E' = E(A, B)$. We say
that a pair $(L, R) \in 2^{V(G)} \times 2^{V(G)}$ is a *separation* of $G$ if $L \cup R = V(G)$ and $E(L \setminus R, R \setminus L) = \emptyset$. The *order* of $(L, R)$ is $|L \cap R|$. $L \cap R$ is called a $|L \cap R|$-separator of $G$. A graph $G$ is $k$-connected if, for any separation $(L, R)$ of $G$ of order at most $k-1$, either $L \subseteq R$ or $R \subseteq L$. A *cut vertex* in a connected graph $G$ is a vertex whose removal disconnects $G$. A *block* of $G$ is a maximal connected subgraph of $G$ without a cut vertex. A graph class $\mathcal{H}$ is *monotone* if the subgraphs of graphs in $\mathcal{H}$ are also in $\mathcal{H}$. A graph class $\mathcal{H}$ is *hereditary* if the induced subgraphs of graphs in $\mathcal{H}$ are also in $\mathcal{H}$. The *torso* of a set $X \subseteq V(G)$, denoted by $\text{torso}_G(X)$, is the graph obtained from $G[X]$ by making $N_G(C)$ a clique for each $C \in \text{cc}(G \setminus X)$. Given two graphs $G_1$ and $G_2$, and $q \in \mathbb{N}$, a $q$-clique-sum of $G_1$ and $G_2$ is obtained from their disjoint union by identifying a $q$-clique of $G_1$ with a $q$-clique of $G_2$, and then possibly deleting some edges of that clique. A graph class $\mathcal{G}$ is *closed under $q$-clique-sums* if for each $G_1, G_2 \in \mathcal{G}$, any $q$-clique-sum of $G_1$ and $G_2$ also belongs to $\mathcal{G}$.

## 3.2. Odd-minors

**Colorings.** A *coloring* of a graph $G$ is a function $c: V(G) \to \mathbb{N}$. Given $v \in V(G)$, $c(v)$ is called the *color* of $v$ by $c$. Given $k \in \mathbb{N}$, a $k$-coloring is a coloring $c: V(G) \to [k]$. Given a coloring $c$ of a graph $G$ and an edge $uv \in E(G)$, we say that $uv$ is *monochromatic* if $c(u) = c(v)$. Otherwise, we say the $uv$ is *bichromatic*. A coloring $c$ of a graph $G$ is said to be *proper* if every edge of $G$ is bichromatic. We say that a graph $G$ is $k$-colorable if there exists a proper $k$-coloring of $G$.

**Minors and odd-minors.** Let $G$ and $H$ be two graphs. An $H$-expansion in $G$ is a function $\eta$ with domain $V(H) \cup E(H)$ such that:

* for every $v \in V(H)$, $\eta(v)$ is a subgraph of $G$ that is a tree $T_v$, called *node of $\eta$*, such that each leaf of $T_v$ is adjacent to a vertex of another node of $\eta$, and $\eta(v)$ is disjoint from $\eta(w)$ for distinct $v, w \in V(H)$, and

* for every $uv \in E(H)$, $\eta(uv)$ is an edge $u'v'$ in $G$, called *edge of $\eta$*, such that $u' \in V(\eta(u))$ and $v' \in V(\eta(v))$.

We denote by $\bigcup \eta$ the subgraph $\bigcup_{x \in V(H) \cup E(H)} \eta(x)$ of $G$. Given a cycle $C$ in $H$, we set $\eta(C)$ to be the unique cycle in $G$ intersecting exactly the edges $\eta(uv)$ of $\eta$ such that $uv \in E(C)$.

If there is an $H$-expansion in $G$, then we say that $H$ is a *minor* of $G$. The *contraction* of an edge $uv$ in a simple graph $G$ results in a simple graph $G'$ obtained from $G \setminus \{u, v\}$ by adding a new vertex $w$ adjacent to all the vertices in the set $N_G(\{u, v\})$. Equivalently, a graph $H$ is a *minor* of a graph $G$ if $H$ can be obtained from a subgraph of $G$ by contracting edges. We call such a subgraph *model* of $H$ in $G$. Note that the image of $\eta$ is a model of $H$ in $G$. We say that a graph $G$ is $H$-minor-free if $G$ excludes the graph $H$ as a minor.

**Lemma 3.1.** Let $G$ and $H$ be two graphs. The following statements are equivalent.

1. There is an $H$-expansion $\eta$ in $G$ and a 2-coloring of $\bigcup \eta$ that is proper in each node of $\eta$ and such that each edge of $\eta$ is monochromatic.

2. There is an $H$-expansion $\eta$ in $G$ such that every cycle in $\bigcup \eta$ has an even number of edges in $\bigcup_{v \in V(H)} \eta(v)$.

3. There is an $H$-expansion $\eta$ in $G$ such that the length of every cycle $C$ in $H$ has the same parity as the length of the cycle $\eta(C)$ in $\bigcup \eta$.

4. $H$ can be obtained from a subgraph of $G$ by contracting each edge of an edge cut.

*Proof.* See Figure 2 to get some intuition.

1 ⇒ 2: Let $\eta$ be an $H$-expansion in $G$ with a 2-coloring $c$ of $\bigcup \eta$ that is proper in each node of $\eta$ and such that each edge of $\bigcup \eta$ is monochromatic. $\bigcup \eta$ is a subgraph of $G$. The edges of $\bigcup_{v \in V(H)} \eta(v)$ are exactly the bichromatic edges of $\eta$. Let $C$ be a cycle in $\bigcup \eta$. We transform $C$ into a directed cyclic graph $C'$. The bichromatic edges in $C'$ have alternatively color 1-2 and color 2-1. Thus, since $C'$ is a cycle, the number of edges 1-2 and 2-1 is equal. Hence, the number of bichromatic edges in $C$ is even.

2 ⇒ 1: Let $\eta$ be an $H$-expansion in $G$ such that every cycle in $\bigcup \eta$ has an even number of edges in $\bigcup_{v \in V(H)} \eta(v)$. Let $v$ be an arbitrary vertex of $H$. We color $\eta(v)$ greedily to obtain a proper 2-coloring
of the node. Since $\eta(v)$ is a tree, there is only one proper 2-coloring up to isomorphism. We extend this isomorphism greedily to the entire $\bigcup \eta$ so that each edge of $\eta$ is monochromatic and each node of $\eta$ is properly 2-colored. Assume that there is a vertex $v$ of $\bigcup \eta$ that is not colorable by this greedy approach. Then $v$ is part of a cycle $C$ in $\eta$ such that each other vertex of $C$ is colored, but the neighbors $u$ and $w$ of $v$ in $C$ give contradictory instructions for the coloring of $v$. If $u$ has color $c_u$ and $w$ has color $c_w$ with $c_u \neq c_w$ (resp. $c_u = c_w$), then, given that $C$ has an even number of bichromatic edges, this implies that exactly one of $uv$ and $vw$ is bichromatic (resp. $uv$ and $vw$ are either both monochromatic or both bichromatic). Thus, $v$ can be colored greedily. Therefore, $\eta$ is an $H$-expansion in $G$ with a 2-coloring $c$ of $\bigcup \eta$ that is proper in each node of $\eta$ and such that each edge of $\eta$ is monochromatic.

**2** $\Leftrightarrow$ **3**: Let $\eta$ be an $H$-expansion in $G$. By definition, there is a one-to-one correspondence between the edges of $\eta$ and the edges of $H$. Therefore, $C$ is a cycle of $H$ if and only if $\eta(C)$ is a cycle of $\bigcup \eta$, and there are as many edges of $\eta$ in $\eta(C)$ as the number of edges in $C$. The other edges of $\eta(C)$ are in the nodes of $\eta$, i.e., in $\bigcup_{v \in V(H)} \eta(v)$. Thus, every cycle in $\bigcup \eta$ has an even number of edges in $\bigcup_{v \in V(H)} \eta(v)$ if and only if the length of every cycle $C$ in $H$ has the same parity as the length of the cycle $\eta(C)$ in $\bigcup \eta$.

**1** $\Rightarrow$ **4**: Let $\eta$ be an $H$-expansion in $G$ with a 2-coloring $c$ of $\bigcup \eta$ that is proper in each node of $\eta$ and such that each edge of $\eta$ is monochromatic. $\bigcup \eta$ is a subgraph of $G$. Let $X_1$ and $X_2$ be the sets of vertices of $\eta$ with color 1 and 2 respectively. By the definition of $c$, the set $E' = E(X_1, X_2)$ contains exactly the edges that are inside the nodes of $\eta$, and none of the edges joining two nodes of $\eta$. Then $E'$ is an edge cut (between $X_1$ and $X_2$) of $\bigcup \eta$ and, by contracting $E'$ in $\bigcup \eta$, we obtain $H$.

**4** $\Rightarrow$ **1**: Let $G'$ be a subgraph of $G$ and $E'$ be an edge cut of $G'$ such that $H$ can be obtained by contracting $E'$ in $G'$. Let $E'' = E(G') \setminus E'$. Let $G''$ be a graph obtained from $G'$ by removing edges in $E'$ such that every connected component of $G'' \setminus E''$ is a spanning tree. Then there is an $H$-expansion $\eta$ in $G$ such that $\bigcup \eta = G''$ and the edges of $\eta$ are exactly the edges in $E''$. Let $(X_1, X_2)$ be the partition of $V(G')$ witnessing the edge cut $E'$. Then, if we give color 1 to the vertices of $X_1$ and color 2 to the vertices of $X_2$, there is a proper 2-coloring of every node of $\eta$ and each edge of $\eta$ is monochromatic. $\square$

<figure><img src="image_3.png" /><figcaption>Figure 2: An odd $H$-expansion $\eta$ in a graph $G$. The nodes of $\eta$ are the subgraphs in the blue disks, and the edges of $\eta$ are the blue edges in $G$.</figcaption></figure>

An $H$-expansion for which one of the statements of Lemma 3.1 is true is called an *odd $H$-expansion* (see Figure 2 for an illustration). Using Statement 3, we say that such an $H$-expansion in $G$ preserves cycle parity. If there is an $H$-expansion in $G$, then we say that $H$ is an *odd-minor* of $G$. Note that if $H$ is an odd-minor of $G$, then $H$ is a minor of $G$. However, the opposite does not always hold. For instance, $K_3$ is a minor of $C_4$, but is not an odd-minor of $C_4$. We say that a graph $G$ is *$H$-odd-minor-free* if $G$ excludes the graph $H$ as an odd-minor. In particular, observe that bipartite graphs are exactly the $K_3$-odd-minor-free graphs and that the forests are exactly the $\{K_3, C_4\}$-odd-minor-free graphs.
### 3.3. Treewidth-like parameters and preliminary results

**Treewidth.** A tree decomposition of a graph $G$ is a pair $(T, \chi)$ where $T$ is a tree and $\chi: V(T) \to 2^{V(G)}$ such that

* $\bigcup_{t \in V(T)} \chi(t) = V(G),$

* for every $e \in E(G)$, there is a $t \in V(T)$ such that $\chi(t)$ contains both endpoints of $e$, and

* for every $v \in V(G)$, the subgraph of $T$ induced by $\{t \in V(T) \mid v \in \chi(t)\}$ is connected.

The width of $(T, \chi)$ is equal to $\max \{|\chi(t)| - 1 \mid t \in V(T)\}$ and the treewidth of $G$, denoted by $\mathrm{tw}(G)$, is the minimum width over all tree decompositions of $G$.

For every node $t \in V(T)$, $\chi(t)$ is called bag of $t$. Given $tt' \in E(T)$, the adhesion of $t$ and $t'$, denoted by $\mathrm{adh}(t, t')$, is the set $\chi(t) \cap \chi(t')$.

A rooted tree decomposition is a triple $(T, \chi, r)$ where $(T, \chi)$ is a tree decomposition and $(T, r)$ is a rooted tree (i.e., $T$ is a tree and $r \in V(T)$). Given $t \in V(T)$, we denote by $\mathrm{ch}_r(t)$ the set of children of $t$ and by $\mathrm{par}_r(t)$ the parent of $t$ (if $t \neq r$). We set $\delta_t^r = \mathrm{adh}(t, \mathrm{par}_r(t))$, with the convention that $\delta_r^r = \emptyset$. Moreover, we denote by $G_t^r$ the graph induced by $\bigcup_{t' \in V(T_t)} \chi(t')$ where $(T_t, t)$ is the rooted subtree of $(T, r)$ containing all descendants of $t$. We may use $\delta_t$ and $G_t$ instead of $\delta_t^r$ and $G_t^r$ when there is no risk of confusion.

While our goal in this article is to study bipartite treewidth, defined below, we provide the following definition in a more general way, namely of a parameter that we call 1-$\mathcal{H}$-treewidth, with the hope of it finding some application in future work. We use the term 1-$\mathcal{H}$-treewidth to signify that the $\mathcal{H}$-part of each bag intersects each neighboring bag in at most one vertex. This also has the benefit of avoiding confusion with $\mathcal{H}$-treewidth defined in [13], which would be another natural name for this class of parameters.

**1-$\mathcal{H}$-treewidth.** Let $\mathcal{H}$ be a graph class. A 1-$\mathcal{H}$-tree decomposition of a graph $G$ is a triple $(T, \alpha, \beta)$, where $T$ is a tree and $\alpha, \beta: V(T) \to 2^{V(G)}$, such that

* $(T, \alpha \cup \beta)$ is a tree decomposition of $G$, where $\alpha \cup \beta$ maps each $t \in V(T)$ to $\alpha(t) \cup \beta(t)$,

* for every $t \in V(T)$, $\alpha(t) \cap \beta(t) = \emptyset$,

* for every $t \in V(T)$, $G[\beta(t)] \in \mathcal{H}$, and

* for every $tt' \in E(T)$, $| (\alpha \cup \beta)(t') \cap \beta(t) | \leq 1$.

The vertices in $\alpha(t)$ are called apex vertices of the node $t \in V(T)$.

The width of $(T, \alpha, \beta)$ is equal to $\max \{|\alpha(t)| \mid t \in V(T)\}$. The 1-$\mathcal{H}$-treewidth of $G$, denoted by $(1, \mathcal{H})$-tw$(G)$, is the minimum width over all 1-$\mathcal{H}$-tree decompositions of $G$.

A rooted 1-$\mathcal{H}$-tree decomposition is a tuple $(T, \alpha, \beta, r)$ where $(T, \alpha, \beta)$ is a 1-$\mathcal{H}$-tree decomposition and $(T, r)$ is a rooted tree.

Given that $(T, \alpha \cup \beta)$ is a tree decomposition, we naturally extend all definitions and notations concerning treewidth to 1-$\mathcal{H}$-treewidth.

Observe also that a tree decomposition $(T, \chi)$ is also a 1-$\mathcal{H}$-tree decomposition for every graph class $\mathcal{H}$, in the sense that $(T, \chi, o)$ is a 1-$\mathcal{H}$-tree decomposition, where $o: V(T) \to \emptyset$. Therefore, for every graph class $\mathcal{H}$ and every graph $G$, $(1, \mathcal{H})$-tw$(G) \leq \mathrm{tw}(G) + 1$.

If $\mathcal{H}$ is the graph class containing only the empty graph, then a 1-$\mathcal{H}$-tree decomposition is exactly a tree decomposition.
<figure><img src="image_4.png" /><figcaption>Figure 3: A graph of bipartite treewidth one. A corresponding bipartite tree decomposition of width one is depicted, with two bags (one blue and one pink). The apex vertex of each bag is the squared vertex of the same color.</figcaption></figure>

**Remark.** In [13], a parameter with a similar name is defined, namely $\mathcal{H}$-treewidth. The $\mathcal{H}$-treewidth of a graph $G$ is essentially the minimum treewidth of the graph induced by some set $X \subseteq V(G)$ such that the connected components of $G \setminus X$ belong to $\mathcal{H}$. This actually corresponds to the 0-$\mathcal{H}$-treewidth (minus one), which is defined by replacing the “1” by a “0” in the last item of the definition of a 1-$\mathcal{H}$-tree decomposition above. Indeed, let $(T, \alpha, \beta)$ be a 0-$\mathcal{H}$-tree decomposition of a graph $G$ of width $k$. Note that, for each distinct $t, t' \in V(T)$, $\beta(t) \cap \beta(t') = \emptyset$. Let $X = \bigcup_{t \in V(T)} \alpha(t)$. Then $(T, \alpha)$ is a tree decomposition of $X$ of width $k-1$. Moreover, for each $t \in V(T)$, $G[\beta(t)] \in \mathcal{H}$, and therefore the connected components of $G \setminus X$ belong to $\mathcal{H}$.

**Bipartite treewidth [adapted from [5, 8]].** A graph $G$ is bipartite if there is a partition $(A, B)$ of $V(G)$ such that $E(G) = E(A, B)$. We denote the class of bipartite graphs by $\mathcal{B}$. We focus here on the case where $\mathcal{H} = \mathcal{B}$. Then, we use the term *bipartite treewidth* instead of 1-$\mathcal{H}$-treewidth, and denote it by *btw*. As mentioned in the introduction, this definition had already been used (more or less implicitly) in [5, 8].

Given that the bipartite graphs are closed under 1-clique-sums, we have the following.

**Observation 3.1.** A graph has bipartite treewidth zero if and only if it is bipartite.

Moreover, Campbell, Gollin, Hendrey, and Wiederrecht [10] recently announced an FPT-approximation algorithm to construct a bipartite tree decomposition.

**Proposition 3.1 ([10]).** There exist computable functions $f_1, f_2, g: \mathbb{N} \to \mathbb{N}$ and an algorithm that, given a graph $G$ and $k \in \mathbb{N}$, outputs, in time $g(k) \cdot n^4 \log n$, either a report that $\text{btw}(G) \ge f_1(k)$, or a bipartite tree decomposition of $G$ of width at most $f_2(k)$.

Bipartite treewidth is not closed under minors, given that contracting an edge in a bipartite graph (which has bipartite treewidth zero) may create a non-bipartite graph (which has positive bipartite treewidth). However, bipartite treewidth is closed under odd-minors, which is a desirable property to deal with odd-minor related problems.

**Lemma 3.2.** *Bipartite treewidth is closed under odd-minor containment.*

*Proof.* Let $G$ be a graph and $H$ be an odd-minor of $G$. We want to prove that $\text{btw}(H) \le \text{btw}(G)$. By Lemma 3.1, there is a subgraph $G'$ of $G$ and an edge cut $E'$ such that $H$ is obtained from $G'$ by contracting every edge in $E'$.

Since we only removed vertices and edges to obtain $G'$ from $G$, $\text{btw}(G') \le \text{btw}(G)$. It remains to show that $\text{btw}(H) \le \text{btw}(G')$. Let $(T, \alpha', \beta')$ be a bipartite tree decomposition of $G'$. We transform $(T, \alpha', \beta')$ to a bipartite tree decomposition $(T, \alpha, \beta)$ of $H$ as follows. For each $e = uv \in E'$ and for each $t \in V(T)$ such that $\{u, v\} \cap (\alpha' \cup \beta')(t) \ne \emptyset$,

* if $\{u, v\} \cap \alpha'(t) \ne \emptyset$, then the vertex $v_e$ resulting from contracting $e$ is placed in $\alpha(t)$,

* otherwise, $v_e$ is placed in $\beta(t)$.
For each $v \in V(G')$ that is not involved in any contraction and for each $t \in V(T)$, if $v \in \alpha'(t)$ (resp. $v \in \beta'(t)$), then $v \in \alpha(t)$ (resp. $v \in \beta(t)$).

Let us show that $(T, \alpha, \beta)$ is indeed a bipartite tree decomposition of $H$. For simplicity, we identify the vertices in the bags with the vertices of $H$. It is easy to see that $(T, \alpha \cup \beta)$ is a tree decomposition of $H$, since it is obtained from $(T, \alpha' \cup \beta')$ by contracting the edge set $E'$. The only difficult point is to check that, for each $v \in V(H)$ the subgraph of $T$ induced by the bags containing $v$ is connected. This trivially true if $v \in V(G)$. Otherwise, $v = v_{uw}$ for some $u, w \in V(G)$. In this case, given that the subgraph of $T$ induced by the bags of $(T, \alpha' \cup \beta')$ containing $u$ (resp. $w$) is connected and that there is a bag of $(T, \alpha' \cup \beta')$ containing both $u$ and $w$, we also conclude that the subgraph of $T$ induced by the bags of $(T, \alpha \cup \beta)$ containing $v_{uw}$ is indeed connected.

Moreover, given that an edge with at least one endpoint in $\alpha'(t)$ contracts to a vertex in $\alpha(t)$, no new vertex is added to $\beta(t)$, and therefore, for any $t' \in V(T) \setminus \{t\}$, $|\alpha \cup \beta(t') \cap \beta(t)| \le 1$.

It remains to prove that, for each $t \in V(T)$, $H[\beta(t)]$ is bipartite. Let $t \in V(T)$. Let $E_t$ be the set of edges of $E'$ with both endpoints in $\beta'(t)$. We have to prove that the bipartite graph induced by $\beta'(t)$ in $G'$ remains bipartite after contracting $E_t$. $E_t$ is an edge cut of $G'[\beta'(t)]$, witnessed by some vertex partition $(A_1, A_2)$. Given a proper 2-coloring $(B_1, B_2)$ of $G'[\beta'(t)]$, which is bipartite, keep the same color for the vertices in $A_1$, and change the color of the vertices in $A_2$, i.e., define the coloring $(C_1, C_2) = ((B_1 \cap A_1) \cup (B_2 \cap A_2), (B_2 \cap A_1) \cup (B_1 \cap A_2))$. Thus, the monochromatic edges are exactly the edges of $E_t$. Therefore, contracting $E_t$ gives a proper 2-coloring of $H[\beta(t)]$, so $H[\beta(t)]$ is bipartite. Thus, $(T, \alpha, \beta)$ is a bipartite tree decomposition of $H$.

Moreover, since the contraction of an edge with both endpoints in $\beta'(t)$ is a vertex in $\beta(t)$, it follows that $|\alpha(t)| \le |\alpha'(t)|$ for every $t \in V(T)$. Therefore, $\text{btw}(H) \le \text{btw}(G')$. $\square$

A natural generalization of bipartite treewidth can be made by replacing the “1” in the last item of the definition of 1-$\mathcal{H}$-tree decomposition by any $q \in \mathbb{N}$, hence defining $q$-$\mathcal{H}$-tree decompositions and $q$-$\mathcal{H}$-treewidth, denoted by $(q, \mathcal{H})$-tw$(G)$. For $q \ge 2$, however, $q$-$\mathcal{B}$-treewidth is not closed under odd-minor containment, as we prove in Lemma 3.3 below. Additionally, given that for $q \in \{0, 1\}$, $\text{torso}_{G\setminus\alpha(t)}(\beta(t)) = G[\beta(t)]$, we could replace the third item by the property “for every $t \in V(T)$, $\text{torso}_{G\setminus\alpha(t)}(\beta(t)) \in \mathcal{H}'$, hence defining what we call $q$-$\text{torso-}\mathcal{H}$-tree decompositions and $q$-$\text{torso-}\mathcal{H}$-treewidth, denoted by $(q, \mathcal{H})$*-tw$(G)$. However, we prove in Lemma 3.3 that, for $q \ge 2$, $(q, \mathcal{B})$*-tw is also not closed under odd-minors. These facts, in our opinion, provide an additional justification for the choice of $q \le 1$ in the definition of bipartite treewidth.

**Lemma 3.3.** For $q \ge 2$, $q$-$\text{(-torso-}\mathcal{B}$-treewidth is not closed under odd-minor containment. In particular, for any $t \ge 3$, there exist a graph $G$ and an odd-minor $H$ of $G$, such that $(q, \mathcal{B})$-btw$(G) = 0$ and $(q, \mathcal{B})$-btw$(H) = t-2$, and $(q, \mathcal{B})$*-btw$(G) \le 1$ and $(q, \mathcal{B})$*-btw$(H) = t-2$.

*Proof.* Let $t \in \mathbb{N}_{\ge 3}$ and let $K_t''$ (resp. $K_t''$) be the graph obtained from $K_t$ by subdividing every edge once (resp. twice). Let $V' = \{v_1, \dots, v_t\}$ be the set of vertices of $K_t''$ that are the original vertices of $K_t$. $K_t$ is an odd-minor of $K_t''$ since $K_t$ can be obtained from $K_t''$ by contracting the edge cut $E(V', V(K_t'') \setminus V')$. Note also that $K_t'$ is bipartite. We show that taking $G = K_t''$ and $H = K_t$ satisfies the statement of the lemma.

Given that $K_t$ is a complete graph, it has to be fully contained in one bag of any tree decomposition, so in particular of any $q$-(-torso-)$\mathcal{B}$-tree decomposition. Since the smallest odd cycle transversal of $K_t$ has size $t-2$, we have that $(q, \mathcal{B})$*-tw$(K_t) = (q, \mathcal{B})$-tw$(K_t) = t-2$.

Let us first prove that $(q, \mathcal{B})$-tw$(K_t'') = 0$. For $i, j \in [t]$ with $i < j$, let $e_{i,j}$ be the path of length three between $v_i$ and $v_j$. Let $T$ be a tree with one central vertex $x_0$ and, for each $i, j \in [t]$ with $i < j$, a vertex $x_{i,j}$ only adjacent to $x_0$ (thus, $T$ is a star). Let $\beta(x_0) = V'$ and $\beta(x_{i,j}) = V(e_{i,j})$ for each $i, j \in [t]$ with $i < j$. Let $\alpha(x) = \emptyset$ for each $x \in V(T)$. $V'$ is an independent set, so $G[V']$ is bipartite. Note that paths are bipartite. Moreover, each adhesion contains at most two vertices of $\beta(x_0)$ and two vertices of $\beta(x_{i,j})$. Hence, $(T, \alpha, \beta)$ is a $q$-$\mathcal{B}$-tree decomposition of $K_t''$, for $q \ge 2$, and has width zero.

Let us now prove that $(q, \mathcal{B})$*-btw$(K_t'') \le 1$. Let $u_{i,j}$ and $w_{i,j}$ be the internal vertices of $e_{i,j}$, such that $u_{i,j}$ is adjacent to $v_i$. Let $V_1$ (resp. $V_2$) be the set of vertices $u_{i,j}$ (resp. $w_{i,j}$). We construct a $q$-$\text{torso-}\mathcal{B}$-tree decomposition $(T, \alpha', \beta')$ of $K_t''$ as follows. We set $\alpha'(x_0) = \emptyset$ and $\beta'(x_0) = V' \cup V_2$. For each $i, j \in [t]$ with $i < j$, we set $\alpha'(x_{i,j}) = \{v_i\}$ and $\beta'(x_{i,j}) = \{u_{i,j}, w_{i,j}\}$. Observe that $\text{torso}_{K_t''\setminus\alpha'(x_0)}(\beta'(x_0)) = K_t'$, since
each path $v_i-u_{i,j}-w_{i,j}$ is replaced by an edge $v_i w_{i,j}$. Thus, it is bipartite. Similarly, the torso at each other node of $T$ is an edge, and hence is bipartite as well. Moreover, each adhesion contains at most two vertices of $\beta'(x_0)$ and one vertex of $\beta'(x_{i,j})$. Hence, $(T, \alpha', \beta')$ is indeed a $q$-torso-$\mathcal{B}$-tree decomposition of $K_t''$, for $q \ge 2$, and has width one. Therefore, $(q, \mathcal{B})^*\text{-btw}(K_t'') \le 1$.

Hence, $q$-torso-$\mathcal{B}$-treewidth is not closed under odd-minor containment and the gap between a graph and an odd-minor of this graph can be arbitrarily large. $\square$

As mentioned in Subsection 2.1, one of the main difficulties for doing dynamic programming on (rooted) bipartite tree decompositions is the lack of a way to upper-bound the number of children of each node of the decomposition. As shown in the next lemma, the notion of “nice tree decomposition” is not generalizable to bipartite tree decompositions.

**Lemma 3.4.** For any $t \in \mathbb{N}$, there exists a graph $G$ such that $\text{btw}(G) = 1$ and any bipartite tree decomposition of $G$ whose nodes all have at most $t$ neighbors has width at least $t-1$.

*Proof.* Let $G$ be the graph obtained from $K_{t,t}$ by gluing a new pendant triangle $H_v$ to each vertex $v$ of $K_{t,t}$ (that is, $v$ is identified with one vertex of its pendant triangle). Let $T$ be the star $K_{1,2t}$, with vertex set $\{t_0\} \cup \{t_v \mid v \in V(K_{t,t})\}$. Let $\alpha(t_0) = \emptyset$, $\beta(t_0) = V(K_{t,t})$, and for every $v \in V(K_{t,t})$, $\alpha(t_v) = \{v\}$ and $\beta(t_v) = V(H_v) \setminus \{v\}$. It can be easily verified that $\mathcal{T} = (T, \alpha, \beta)$ is a bipartite tree decomposition of $G$ of width one. Given that $G$ is not bipartite, Observation 3.1 implies that $\text{btw}(G) = 1$. Note that node $t_0$ has $2t$ neighbors. For any bipartition $(A, B)$ of $V(K_{t,t})$ such that $A, B \ne \emptyset$, we have $|E(A, B)| \ge t$. Indeed, if $a_1$ and $a_2$ are the vertices of $A$ on each side of $K_{t,t}$, where we can assume without loss of generality $a_1 \ge 1$ and $a_2 \le k-1$ (since $A, B \ne \emptyset$), then $E(A, B)$ has size $a_1(k-a_2)+a_2(k-a_1) = (k-a_1)a_1+(k-a_2)a_2+(a_1-a_2)^2 \ge k-a_1+a_2+(a_1-a_2)^2 \ge k$. Hence, for any bipartite tree decomposition $\mathcal{T}'$ of $G$ such that $V(K_{t,t})$ is not totally contained in one bag, there is an adhesion of two bags of size at least $t$, so the width of $\mathcal{T}'$ is at least $t-1$. If $V(K_{t,t})$ is fully contained in one bag, however, the only way to reduce the number of children to $k$, for some integer $k$, is to add $2t-k$ of the pendant triangles inside the same bag. But then this bag has odd cycle transversal number at least $2t-k$, so the obtained bipartite tree decomposition has width at least $2t-k$. Hence, if we want that $k \le t$, then the corresponding width is at least $2t-k \ge t$. $\square$

### 3.4. *Boundaried graphs*

To design dynamic programming algorithms, we need to first define bounded graphs.

Let $t \in \mathbb{N}$. A $t$-bounded *graph* is a triple $\mathbf{G} = (G, B, \rho)$ where $G$ is a graph, $B \subseteq V(G)$, $|B| = t$, and $\rho: B \to \mathbb{N}$ is an injective function. We say that $B$ is the *boundary* of $\mathbf{G}$ and we write $B = \text{bd}(G)$. We call $\mathbf{G}$ *trivial* if all its vertices belong to the boundary. We say that two $t$-bounded graphs $\mathbf{G}_1 = (G_1, B_1, \rho_1)$ and $\mathbf{G}_2 = (G_2, B_2, \rho_2)$ are *isomorphic* if $\rho_1(B_1) = \rho_2(B_2)$ and there is an isomorphism from $G_1$ to $G_2$ that extends the bijection $\rho_2^{-1} \circ \rho_1$. A triple $(G, B, \rho)$ is a *bounded graph* if it is a $t$-bounded graph for some $t \in \mathbb{N}$. A bounded graph $\mathbf{F}$ is a *bounded induced subgraph* (resp. *bounded subgraph*) of $\mathbf{G}$ if $\mathbf{F}$ can be obtained from $\mathbf{G}$ by removing vertices (resp. and edges). A bounded graph $\mathbf{F}$ is a *bounded odd-minor* of $\mathbf{G}$ if $\mathbf{F}$ can be obtained from a bounded subgraph $\mathbf{G}'$ of $\mathbf{G}$ by contracting an edge cut such that every vertex in $\text{bd}(\mathbf{G}')$ is on the same side of the cut. We say that two bounded graphs $\mathbf{G}_1 = (G_1, B_1, \rho_1)$ and $\mathbf{G}_2 = (G_2, B_2, \rho_2)$ are *compatible* if $\rho_1(B_1) = \rho_2(B_2)$ and $\rho_2^{-1} \circ \rho_1$ is an isomorphism from $G_1[B_1]$ to $G_2[B_2]$.

Given two bounded graphs $\mathbf{G}_1 = (G_1, B_1, \rho_1)$ and $\mathbf{G}_2 = (G_2, B_2, \rho_2)$, we define $\mathbf{G}_1 \oplus \mathbf{G}_2$ as the unbounded graph obtained if we take the disjoint union of $G_1$ and $G_2$ and, for every $i \in \rho_1(B_1) \cap \rho_2(B_2)$, we identify vertices $\rho_1^{-1}(i)$ and $\rho_2^{-1}(i)$. Note that we do not ask $\mathbf{G}_1$ and $\mathbf{G}_2$ to be compatible. If two vertices are adjacent in at least one boundary, then there are adjacent in $\mathbf{G}_1 \oplus \mathbf{G}_2$. If $v$ is the result of the identification of $v_1 := \rho_1^{-1}(i)$ and $v_2 := \rho_2^{-1}(i)$ then we say that $v$ is the *heir* of $v_i$ from $\mathbf{G}_i$, $i \in [2]$. If $v$ is either a vertex in $B_1$ where $\rho_1(v) \notin \rho_1(B_1) \cap \rho_2(B_2)$ or a vertex in $B_2$ where $\rho_2(v) \notin \rho_1(B_1) \cap \rho_2(B_2)$, then $v$ is also a (non-identified) vertex of $\mathbf{G}_1 \oplus \mathbf{G}_2$ and is an *heir* of itself (from $\mathbf{G}_1$ or $\mathbf{G}_2$ respectively). For $i \in [2]$, and given an edge $vu$ in $\mathbf{G}_1 \oplus \mathbf{G}_2$, we say that $vu$ is the *heir* of an edge $v'u'$ from $\mathbf{G}_i$ if $v'$ is the heir of $v$ from $\mathbf{G}_i$, $u'$ is the heir of $u$ from $\mathbf{G}_i$, and $v'u'$ is an edge of $G_i$. If $x'$ is an heir of $x$ from $\mathbf{G} = (G, B, \rho)$ in $\mathbf{G}'$, then we write $x = \text{heir}_{\mathbf{G}, \mathbf{G}'}(x')$. Given $B' \subseteq B$, we write $\text{heir}_{\mathbf{G}, \mathbf{G}'}(B') = \bigcup_{v \in B'} \text{heir}_{\mathbf{G}, \mathbf{G}'}(x')$. We
<figure><img src="image_5.png" /><figcaption>Figure 4: Examples of use of the operations $\oplus$, $\boxplus$, and $\triangleright$.</figcaption></figure>

also define $G_1 \boxplus G_2$ as the *bounded* graph $(G_1 \oplus G_2, B, \rho)$, where $B$ is the set of all heirs from $G_1$ and $G_2$ and $\rho: B \to \mathbb{N}$ is the union of $\rho_1$ and $\rho_2$ after identification. Note that in circumstances where $\boxplus$ is repetitively applied, the heir relation is maintained due to its transitivity. Moreover, we define $G_1 \triangleright G_2$ as the unbounded graph $G$ obtained from $G_1 \oplus G_2$ by removing all heirs from $G_2$ that are not heirs from $G_1$ and all heirs of edges from $G_2$ that are not heirs of edges from $G_1$. Informally, $G_1 \triangleright G_2$ is obtained from $G_1 \oplus G_2$ by removing vertices and edges of $G[B_2]$ that are not in $G[B_1]$. Note that $\triangleright$ is not commutative. See Figure 4 for an illustration of the operations $\oplus$, $\boxplus$, and $\triangleright$.

# 4. General dynamic programming to obtain FPT-algorithms

In this section, we introduce a framework for obtaining FPT-algorithms for problems parameterized by the width of a given bipartite tree decomposition of the input graph. In Subsection 4.1 we introduce the main technical notion of a *nice problem* and the necessary background, and in Subsection 4.2 we provide dynamic programming algorithms for nice problems. In Subsection 4.4, we give applications to concrete problems.

## 4.1. Nice problems

All algorithms we give for problems on graphs of bounded *btw* follow the same strategy. To avoid unnecessary repetition, we introduce a framework that captures the features that the problems have in common with respect to their algorithms using bipartite tree decompositions. Naturally, the algorithms use dynamic programming along a rooted bipartite tree decomposition. However, as the bags in the decomposition can now be large, we cannot apply brute-force approaches to define table entries as we can, for instance, on standard tree decompositions when dealing with treewidth.

Suppose we are at a node $t$ with children $t_1, \dots, t_d$. Since the size of $\alpha(t)$ is bounded by the width, we can store all possible ways in which solutions interact with $\alpha(t)$. Moreover, since each adhesion has at most one vertex from $\beta(t)$, the size of each adhesion is still bounded in terms of the bipartite treewidth. Therefore, we can store one table entry for each way in which a solution can interact with the adhesion $\delta_t$ of $t$ and its parent. However, since the size of $\beta(t)$ is unbounded, there can now be an exponential (in $n$) number of choices of table entries that are “compatible” with the choice $\mathcal{X}$ made for $\delta_t$, so we cannot simply brute-force them to determine the optimum value corresponding to $\mathcal{X}$. To overcome this, we apply the following strategy: First, since the size of $\alpha(t)$ is bounded in terms of the bipartite treewidth, we guess which choice $\mathcal{A}$ of the interaction of the solution with $\alpha(t) \cup \delta_t$ that extends $\mathcal{X}$ leads to the optimum partial solution. For each $i \in [d]$, there may be a vertex $v_{t_i} \in \delta_{t_i} \cap \beta(t)$ whose interaction with the partial solution remained undecided. We replace, for each $i \in [d]$, the subgraph $G_{t_i} \setminus \delta_{t_i}$ with a simply structured subgraph that simulates the
behaviour of the table at $t_i$ when it comes to the decision of how $v_{t_i}$ interacts with the solution, under the choice of $\mathcal{A}$ for $\alpha(t) \cup \delta_t$. The crux is that the resulting graph will have an odd cycle transversal that is bounded in terms of the size of $\alpha(t)$, so we can apply known FPT-algorithms parameterized by odd cycle transversal to determine the value of the table entry. These notions can be formalized not only for bipartite treewidth, but for any $1-\mathcal{H}$-treewidth, so we present them in full generality here. We also depart from using tree decompositions explicitly, and state them in an equivalent manner in the language of bounded graphs.

First, let us formalize the family of problems we consider which we refer to as *optimization problems*. Here, solutions correspond in some sense to partitions of the vertex set, and we want to optimize some property of such a partition. For instance, if we consider ODD CYCLE TRANSVERSAL, then this partition has three parts, one for the vertices in the solution, and one part for each part of the bipartition of the vertex set of the graph obtained by removing the solution vertices, and we want to minimize the size of the first part of the partition. (It will become clear later why we keep one separate part for each part of the bipartition.) In MAXIMUM CUT, the partition simply points to which side of the cut each vertex is on, and we want to maximize the number of edges going across.

A *p-partition-evaluation function on graphs* is a function $f$ that receives as input a graph $G$ along with a *p-partition* $\mathcal{P}$ of its vertices and outputs a non-negative integer. Given such a function $f$ and some choice $\text{opt} \in \{\max, \min\}$ we define the associated graph parameter $\mathbf{p}_{\text{opt}}$ where, for every graph $G$,

$$ \mathbf{p}_{\text{opt}}(G) = \text{opt}\{f(G, \mathcal{P}) \mid \mathcal{P} \text{ is a } p\text{-partition of } V(G)\}. $$

An *optimization graph partition problem* (optimization problem for short) is a problem that can be expressed as follows.

**Input:** A graph $G$.

**Objective:** Compute $\mathbf{p}_{\text{opt}}(G)$.

To represent the case when we made some choices for the (partial) solution to an optimization problem, such as $\mathcal{A}$ above, we consider *annotated* versions of such problems. They extend the function $\mathbf{p}_{\text{opt}}$ so to receive as input, apart from a graph, a set of annotated sets in the form of a partition $\mathcal{X} \in \mathcal{P}_p(X)$ of some $X \subseteq V(G)$. More formally, the *annotated extension* of $\mathbf{p}_{\text{opt}}$ is the parameter $\hat{\mathbf{p}}_{\text{opt}}$ such that

$$ \hat{\mathbf{p}}_{\text{opt}}(G, \mathcal{X}) = \text{opt}\{f(G, \mathcal{P}) \mid \mathcal{P} \text{ is a } p\text{-partition of } V(G) \text{ with } \mathcal{X} \subseteq \mathcal{P}\}. $$

Observe that $\mathbf{p}_{\text{opt}}(G) = \hat{\mathbf{p}}_{\text{opt}}(G, \emptyset^p)$, for every graph $G$. The problem $\Pi'$ is a *p-annotated extension* of the optimization problem $\Pi$ if $\Pi$ can be expressed by some *p-partition-evaluation function* $f$ and some choice $\text{opt} \in \{\max, \min\}$, and if $\Pi'$ can be expressed as follows.

**Input:** A graph $G$ and $\mathcal{X} \in \mathcal{P}_p(X)$ for some $X \subseteq V(G)$.

**Objective:** Compute $\hat{\mathbf{p}}_{\text{opt}}(G, \mathcal{X})$.

We also say that $\Pi'$ is a *p-annotated problem*.

Let us turn to the main technical tool introduced in this section that formalizes the above idea, namely *nice problems*. First, we may assume that the vertices of $G$ are labeled injectively via $\sigma$. Then, each graph $G_{t_i}$, for $i \in [d]$, naturally corresponds to a bounded graph $\mathbf{G}_i = (G_{t_i}, \delta_{t_i}, \sigma|_{\delta_{t_i}})$; from now on let $X_i = \delta_{t_i}$. The part of $G_t$ that will be modified can be viewed as a bounded graph $\mathbf{G}$ which is essentially obtained as $\bigoplus_{i \in [d]} \mathbf{G}_i$. However, as we want to fix a choice of how the partial solution interacts with $\delta_t$, we include these corresponding vertices in $\mathbf{G}$ as well, modeled as a trivial bounded graph $\mathbf{X}$, making $\mathbf{G} = \mathbf{X} \oplus (\bigoplus_{i \in [d]} \mathbf{G}_i)$ (see Figure 5 for an illustration).

Denote the boundary of $\mathbf{G}$ by $X$. The set $X$ is partitioned into $(A, B)$, corresponding to $(X \cap (\alpha(t) \cup \delta(t))) \cup X \cap (\beta(t) \setminus \delta(t)))$, and the fact that the adhesion between $t_i$ and $t$ had at most one vertex in common with $\beta(t)$ now materializes as the fact that for each $i \in [d]$, $\mathbf{G}$ has at most one vertex outside of $A$ that is an heir of a vertex in $\mathbf{G}_i$. Fixing a choice for $\alpha(t) \cup \delta_t$ now corresponds to choosing a partition $\mathcal{A}$ of the set $A$. As we assume that all table entries at the children have been computed, we assume knowledge of all values $\hat{\mathbf{p}}_{\text{opt}}(G_{t_i}, \mathcal{X}_i)$, for all $i \in [d]$ and $\mathcal{X}_i \in \mathcal{P}_p(X_i)$. This finishes the motivation of the input of a nice problem.
<figure><img src="image_6.png" /><figcaption>Figure 5: Illustration of $G = X \boxplus (\coprod_{i \in [d]} G_i)$.</figcaption></figure>

Given the pair $(G, A)$, a nice problem outputs a tuple $(G' = (G', X', \rho'), A', s')$, called *nice reduction*, with the following desired properties. $G'$ can be constructed by gluing $d'$ bounded graphs plus one trivial one (for some $d' \in \mathbb{N}$), similarly to $G$. $A'$ is a $p$-partition of a set $A' \subseteq V(G')$ whose size is at most the size of $A$ plus a constant. No matter what the structure of the graph of the vertices in $(\alpha \cup \beta)(t)$ looked like (remember, so far we carved out only the adhesions), the solutions are preserved, up to an offset of $s'$. This is modeled by saying that for each bounded graph $F$ (which corresponds to the remainder of the bag at $t$) compatible with $G$, $\hat{p}_{f,\text{opt}}(G \oplus F, A) = \hat{p}_{f,\text{opt}}(G' \triangleright F, A') + s'$. The reason why we use the $\triangleright$-operator in the right-hand side of the equation is the gadgeteering happening in the later sections. To achieve the “solution-preservation”, we might have to add or remove vertices, or change adjacencies between vertices in $X_i$ (for ODD CYCLE TRANSVERSAL and MAXIMUM CUT for instance).

The last condition corresponds to our aim that if the bag at $t$ induces a graph of small *oct* (now, a small modulator to a graph class $\mathcal{H}$), then the entire graph resulting from the operation $(G' \triangleright F)$ should have a small modulator to $\mathcal{H}$ (namely $A'$). All remaining conditions are related to the efficiency of the nice reduction.

**Nice problem and nice reduction.** Let $p \in \mathbb{N}$, let $\mathcal{H}$ be a graph class, and let $\Pi$ be a $p$-annotated problem corresponding to some choice of a $p$-partition-evaluation function $f$ and some $\text{opt} \in \{\max, \min\}$. We say that $\Pi$ is a $\mathcal{H}$-nice problem if there exists an algorithm that receives as input

* a bounded graph $G = (G, X, \rho)$,

* a trivial bounded graph $X = (G[X], X, \rho_X)$ and a collection $\{G_i \mid i \in [d]\}$ of bounded graphs with $G_i = (G_i, X_i, \rho_i)$ for $i \in [d]$, such that $d \in \mathbb{N}$ and $G = X \boxplus (\coprod_{i \in [d]} G_i)$ (see Figure 5),

* a partition $(A, B)$ of $X$ such that for all $i \in [d]$, $|\text{heir}_{G_i, G}(X_i) \setminus A| \le 1$,

* some $A \in \mathcal{P}_p(A)$, and

* for every $i \in [d]$ and each $X_i \in \mathcal{P}_p(X_i)$, the value $\hat{p}_{f,\text{opt}}(G_i, X_i)$,

and outputs, in time $O(|A| \cdot d)$, a tuple $(G' = (G', X', \rho'), A', s')$, called $\mathcal{H}$-nice reduction of the pair $(G, A)$ with respect to $\Pi$, such that the following hold (see Figure 6 for an illustration).

(i) There are sets $A' \subseteq V(G')$ and $A' \in \mathcal{P}_p(A')$ with $|A'| = |A| + O(1)$.

(ii) There is a trivial bounded graph $X' = (G[X'], X', \rho_{X'})$ and a collection $\{G'_i = (G'_i, X'_i, \rho'_i) \mid i \in [d']\}$, where $d' \in \mathbb{N}$, of bounded graphs such that $G' = X' \boxplus (\coprod_{i \in [d']} G'_i)$ and $|V(G')| \le |X| + O(|B|)$, $|E(G')| \le |E(G[X'])| + O(|B|)$.

(iii) For any bounded graph $F$ compatible with $G$, it holds that

$$ \hat{p}_{f,\text{opt}}(G \oplus F, A) = \hat{p}_{f,\text{opt}}(G' \triangleright F, A') + s'. $$
<figure><img src="image_7.png" /><figcaption>Figure 6: Illustration of the setting of the nice problem and reduction. The shaded area on the left is $\mathbf{G}$ where $X = X_1 \cup X_2 \cup X^*$, and the shaded area on the right is $\mathbf{G}'$ where $X' = X'_1 \cup X'_2 \cup X'^*$.</figcaption></figure>

(iv) For any bounded graph $\mathbf{F} = (F, X_F, \rho_F)$ compatible with $\mathbf{G}$, if $\bar{F} \setminus A_F \in \mathcal{H}$, where $\bar{F} = (\mathbf{F} \oplus \mathbf{G})[\text{heir}_{\mathbf{F}, \mathbf{G} \oplus \mathbf{F}}(V(F))]$ and $A_F = \text{heir}_{\mathbf{G}, \mathbf{G} \oplus \mathbf{F}}(A)$, then $(\mathbf{G}' \triangleright \mathbf{F}) \setminus A' \in \mathcal{H}$.

All the definitions of this section are naturally generalizable to graphs with weights on the vertices and/or edges. Given such a weight function $w$, we extend $f(G, \mathcal{P})$, $\mathbf{p}_{\text{fopt}}(G)$, $\hat{\mathbf{p}}_{\text{fopt}}(G, \mathcal{X})$, $(\mathbf{G}, \mathcal{A})$, and $(\mathbf{G}', \mathcal{A}', s')$ to $f(G, \mathcal{P}, w)$, $\mathbf{p}_{\text{fopt}}(G, w)$, $\hat{\mathbf{p}}_{\text{fopt}}(G, \mathcal{X}, w)$, $(\mathbf{G}, \mathcal{A}, w)$, and $(\mathbf{G}', \mathcal{A}', s', w')$, respectively.

## 4.2. General dynamic programming scheme

We now have all the ingredients for our general dynamic programming scheme on bipartite tree decompositions. We essentially prove that if a problem $\Pi$ has an annotated extension that is $\mathcal{B}$-nice and solvable in FPT-time parameterized by $\text{oct}$, then $\Pi$ is solvable in FPT-time parameterized by $\text{btw}$. This actually holds for more general $\mathcal{H}$.

**Lemma 4.1.** Let $p \in \mathbb{N}$. Let $\mathcal{H}$ be a hereditary graph class. Let $\Pi$ be an optimization problem. Let $\Pi'$ be a problem that is:

* a p-annotated extension of $\Pi$ corresponding to some choice of p-partition-evaluation function $g$ and some $\text{opt} \in \{\max, \min\}$,

* $\mathcal{H}$-nice, and

* solvable, given instances $(G, \mathcal{X})$ such that $G \setminus \mathcal{X} \in \mathcal{H}$, in time $f(|\mathcal{X}|) \cdot n^c \cdot m^d$, for some $c, d \in \mathbb{N}$.

Then, there is an algorithm that, given a graph $G$ and a 1-$\mathcal{H}$-tree decomposition of $G$ of width $k$, computes $\mathbf{p}_{\text{fopt}}(G)$ in time $\mathcal{O}(p^k \cdot f(k + \mathcal{O}(1)) \cdot (k \cdot n)^c \cdot m^d)$ (or $\mathcal{O}(p^k \cdot f(k + \mathcal{O}(1)) \cdot (m + k^2 \cdot n)^d)$ if $c = 0$).

*Proof.* Let Alg be the algorithm that solves instances $(G, \mathcal{X})$ such that $G \setminus \mathcal{X} \in \mathcal{H}$ in time $f(|\mathcal{X}|) \cdot n^c \cdot m^d$.

Let $(T, \alpha, \beta, r)$ be a rooted 1-$\mathcal{H}$-tree decomposition of $G$ of width at most $k$. Let $\sigma: V(G) \to \mathbb{N}$ be an injection. For $t \in V(T)$, we set the following. Let $\mathbf{G}_t = (G_t, \delta_t, \sigma|_{\delta_t})$ be a bounded graph whose underlying graph $G_t$ contains the vertices of $G$ appearing below $t$ in the tree decomposition and whose boundary is the adhesion $\delta_t$ of $t$ with its parent. Let $A_t = \alpha(t) \cup \delta_t$ be the vertices of $\alpha(t)$ plus the vertex in $\delta_t \setminus \alpha(t)$, if it exists. Let $X_t$ be the union of $A_t$ and the adhesions $\delta_{t'}$ for $t' \in \text{chr}_r(t)$ and let $B_t = X_t \setminus A_t$, that is, containing the vertex in $\delta_{t'} \setminus \alpha(t)$ for each $t' \in \text{chr}_r(t)$, if it exists. Let also $\mathbf{X}_t = (G[X_t], X_t, \sigma|_{X_t})$ be a trivial bounded graph with underlying graph $X_t$ and $\mathbf{H}_t = \mathbf{X}_t \boxplus (\boxtimes_{t' \in \text{chr}_r(t)} \mathbf{G}_{t'})$ (as in Figure 5). Let also $\mathbf{F}_t$ be such that $G_t = \mathbf{F}_t \oplus \mathbf{H}_t$, that is, essentially, the graph induced by the bag at node $t$ with boundary $X_t$. Recall that $|\text{bd}(\mathbf{G}_{t'}) \setminus A_t| \le 1$ for $t' \in \text{chr}_r(t)$.

We proceed in a bottom-up manner to compute $\hat{p}_{g,\text{opt}}(G_t, \mathcal{X})$, for each $t \in V(T)$, for each $\mathcal{X} \in \mathcal{P}_p(\delta_t)$. Hence, given that $\delta_r = \emptyset$, it implies that $\hat{p}_{g,\text{opt}}(G_r, \emptyset) = \mathbf{p}_{g,\text{opt}}(G)$.

We fix $t \in V(T)$. By induction, for each $t' \in \text{chr}_r(t)$ and for each $\mathcal{X}_{t'} \in \mathcal{P}_p(\delta_{t'})$, we compute the value $\hat{p}_{g,\text{opt}}(G_{t'}, \mathcal{X}_{t'})$. Let $\mathcal{X} \in \mathcal{P}_p(\delta_t)$, let $\mathcal{Q}$ be the set of all $\mathcal{A} \in \mathcal{P}_p(A_t)$ such that $\mathcal{A} \cap \delta_t = \mathcal{X}$, and let
$\mathcal{A} \in \mathcal{Q}$. Since $\Pi'$ is $\mathcal{H}$-nice, there is an $\mathcal{H}$-nice reduction $(\mathbf{H}_{\mathcal{A}}, \mathcal{A}', s_{\mathcal{A}})$ of $(\mathbf{H}_t, \mathcal{A})$ with respect to $\Pi'$. Hence, $\hat{\mathbf{p}}_{g,\text{opt}}(G_t, \mathcal{A}) = \hat{\mathbf{p}}_{g,\text{opt}}(\mathbf{H}_{\mathcal{A}} \triangleright \mathbf{F}_t, \mathcal{A}') + s_{\mathcal{A}}$ by item (iii). Let us compute $\hat{\mathbf{p}}_{g,\text{opt}}(\mathbf{H}_{\mathcal{A}} \triangleright \mathbf{F}_t, \mathcal{A}')$.

Given that $(T, \alpha, \beta)$ is a 1-$\mathcal{H}$-tree decomposition, we have $F_t \setminus \alpha(t) = G[\beta(t)] \in \mathcal{H}$, where $F_t$ is the underlying graph of $\mathbf{F}_t$. Thus, given that $\mathcal{H}$ is hereditary, we have $F_t \setminus A_t \in \mathcal{H}$. Therefore, by item (iv) of the definition of an $\mathcal{H}$-reduction, $(\mathbf{H}_{\mathcal{A}} \triangleright \mathbf{F}_t) \setminus (\cup \mathcal{A}') \in \mathcal{H}$. Hence, we can compute $\hat{\mathbf{p}}_{g,\text{opt}}(\mathbf{H}_{\mathcal{A}} \triangleright \mathbf{F}_t, \mathcal{A}')$, and thus $\hat{\mathbf{p}}_{g,\text{opt}}(G_t, \mathcal{A})$, using Alg on the instance $(\mathbf{H}_{\mathcal{A}} \triangleright \mathbf{F}_t, \mathcal{A}')$. Finally, $\hat{\mathbf{p}}_{g,\text{opt}}(G_t, \mathcal{X}) = \text{opt}_{\mathcal{A} \in \mathcal{Q}} \hat{\mathbf{p}}_{g,\text{opt}}(G_t, \mathcal{A})$.

It remains to calculate the complexity. Throughout, we make use of the fact that $p$ is a fixed constant. We can assume that $T$ has at most $n$ nodes: for any pair of nodes $t$ and $t'$ with $(\alpha \cup \beta)(t) \subseteq (\alpha \cup \beta)(t')$, we can contract the edge $tt'$ of $T$ to a new vertex $t''$ with $\alpha(t'') = \alpha(t')$ and $\beta(t'') = \beta(t')$. This defines a valid 1-$\mathcal{H}$-tree decomposition of the same width. For any leaf $t$ of $T$, there is a vertex $u \in V(G)$ that only belongs to the bag of $t$. From this observation, we can inductively associate each node of $T$ to a distinct vertex of $G$. Hence, if $c_t = |\text{ch}_r(t)|$, then we have $\sum_{t \in V(T)} c_t \le n$. Let also $n_t = |(\alpha \cup \beta)(t)|$ and $m_t = |E(G[(\alpha \cup \beta)(t)])|$. Note that $|A_t| = |\alpha(t)| + |\delta_t \cap \beta(t)| \le k+1$ and that $|B_t| = |\bigcup_{t' \in V(T)} \delta_{t'} \cap \beta(t)| \le c_t$, so $|X_t| \le k+1+c_t$. Moreover, the properties of the tree decompositions imply that the vertices in $\beta(t) \setminus X_t$ are only present in node $t$. Then, $\sum_{t \in V(T)} n_t = \sum_{t \in V(T)} (|X_t| + |\beta(t) \setminus X_t|) = \mathcal{O}(k \cdot n)$. Also, let $\bar{m}_t$ be the number of edges only present in the bag of node $t$. The edges that are present in several bags are those in the adhesion of $t$ and its neighbors. $t$ is adjacent to its $|c_t|$ children and its parent, and an adhesion has size at most $k+1$. Thus, $\sum_{t \in V(T)} m_t \le \sum_{t \in V(T)} (\bar{m}_t + k^2(1+c_t)) = \mathcal{O}(m + k^2 \cdot n)$.

There are $p^{|A_t|} \le p^{k+1} = \mathcal{O}(p^k)$ partitions of $\mathcal{P}_p(A_t)$. For each of them, we compute in time $\mathcal{O}(k \cdot c_t)$ an $\mathcal{H}$-nice reduction $(\mathbf{H}_{\mathcal{A}}, \mathcal{A}', s_{\mathcal{A}})$ with $|\cup \mathcal{A}'| = |A_t| + \mathcal{O}(1) = k + \mathcal{O}(1)$ (by item (i)) and with $\mathcal{O}(|B_t|) = \mathcal{O}(c_t)$ additional vertices and edges (by item (ii)). We thus solve $\Pi'$ on $(\mathbf{H}_{\mathcal{A}} \triangleright \mathbf{F}_t, \mathcal{A}')$ in time $f(k + \mathcal{O}(1)) \cdot \mathcal{O}((n_t + c_t)^c \cdot (m_t + c_t)^d)$. Hence, the running time is $\mathcal{O}(p^k \cdot f(k + \mathcal{O}(1)) \cdot (k \cdot n)^c \cdot m^d)$ (or $\mathcal{O}(p^k \cdot f(k + \mathcal{O}(1)) \cdot (m + k^2 \cdot n)^d)$ if $c=0$). $\square$

### 4.3. Generalizations

For the sake of simplicity, we assumed in Lemma 4.1 that the problem $\Pi$ under consideration takes as input just a graph. However, a similar statement still holds if we add labels/weights on the vertices/edges of the input graph. This is in particular the case for WEIGHTED INDEPENDENT SET (Subsection 4.4.2) and MAXIMUM WEIGHTED CUT (Subsection 4.4.4) where the vertices or edges are weighted. Furthermore, while we omit the proof here, with some minor changes to the definition of a nice problem, a similar statement would also hold for $q$(-torso)-$\mathcal{H}$-treewidth.

Moreover, again for the sake of simplicity, we assumed that $\Pi'$ is solvable in FPT-time, while other complexities such as XP-time could be considered. Similarly, in the definition of the nice reduction, the constraints $|A'| = |A| + \mathcal{O}(1)$, $|V(G')| \le |X| + \mathcal{O}(|B|)$, $|E(G')| \le |E(G[X])| + \mathcal{O}(|B|)$ can be modified. For instance, we could change the first constraint to $|A'| = \mathcal{O}(1)$. In those cases, the dynamic programming algorithm still applies, but the running time of Lemma 4.1 is different.

To give a precise running time for $K_t$-SUBGRAPH-COVER (Subsection 4.4.1), WEIGHTED INDEPENDENT SET (Subsection 4.4.2), and MAXIMUM WEIGHTED CUT (Subsection 4.4.4) below, let us observe that, if $\Pi'$ is solvable in time $f(|\cup X|) \cdot (n')^c \cdot (m')^d$, where $G' = G \setminus X$, $n' = |V(G')|$, and $m' = |E(G')|$, then the running time of Lemma 4.1 is better. Indeed, in the proof of the complexity of Lemma 4.1, we now solve $\Pi'$ on $(\mathbf{H}_{\mathcal{A}} \triangleright \mathbf{F}_t, \mathcal{A}')$ in time $f(k + \mathcal{O}(1)) \cdot \mathcal{O}((n'_t + c_t)^c \cdot (m'_t + c_t)^d)$, where $n'_t = |\beta(t)|$ and $m'_t = |E(G[\beta(t)])|$. We have $\sum_{t \in V(T)} n'_t = \sum_{t \in V(T)} (|B| + |\beta(t) \cap \delta_t| + |\beta(t) \setminus X|) = \mathcal{O}(n)$ and $\sum_{t \in V(T)} m'_t \le m$. Hence, the total running time is $\mathcal{O}(p^k \cdot (k \cdot n + f(k + \mathcal{O}(1)) \cdot n^c \cdot m^d))$.

### 4.4. Applications

We now apply the above framework to give FPT-algorithms for several problems parameterized by bipartite treewidth, that is, 1-$\mathcal{B}$-treewidth where $\mathcal{B}$ is the class of bipartite graphs. Thanks to Lemma 4.1, this now reverts to showing that the problem under consideration has a $\mathcal{B}$-nice annotated extension that is solvable in FPT time when parameterized by oct. Several of the presented results actually hold for other graph classes $\mathcal{H}$, not necessarily only bipartite graphs.
All of the problems of this section have the following property, that seems critical to show that a problem is H -nice.

**Gluing property.** Let $\Pi$ be a $p$-annotated problem corresponding to some choice of $p$-partition-evaluation function $f$ and some $\text{opt} \in \{\text{max, min}\}$. We say that $\Pi$ has the *gluing property* if, given two compatible bounded graphs $\mathbf{F} = (F, X, \rho)$ and $\mathbf{G} = (G, X, \rho)$, $\mathcal{X} \in \mathcal{P}_p(X)$, and $\mathcal{P} \in \mathcal{P}_p(V(\mathbf{F} \oplus \mathbf{G}))$ such that $\mathcal{X} \subseteq \mathcal{P}$, then $\hat{\mathbf{p}}_{f,\text{opt}}(\mathbf{F} \oplus \mathbf{G}, \mathcal{X}) = f(\mathbf{F} \oplus \mathbf{G}, \mathcal{P})$ if and only if $\hat{\mathbf{p}}_{f,\text{opt}}(F, \mathcal{X}) = f(F, \mathcal{P} \cap V(F))$ and $\hat{\mathbf{p}}_{f,\text{opt}}(G, \mathcal{X}) = f(G, \mathcal{P} \cap V(G))$, where $F$ and $G$ are the underlying graphs of $\mathbf{F}$ and $\mathbf{G}$ (see Figure 7).

<figure><img src="image_8.png" /><figcaption>Figure 7: If a problem $\Pi$ has the gluing property, then a solution is optimal on $\mathbf{F} \oplus \mathbf{G}$ if and only if its restriction to $F$ and its restriction to $G$ are both optimal.</figcaption></figure>

For the sake of simplicity, with a slight abuse of notation, we identify in this section a vertex with its
heir.

Let $\Pi'$ be an annotated extension of some problem $\Pi$. Given an instance $(\mathbf{G} = \mathbf{X} \boxplus (\boxplus_{i \in [d]} \mathbf{G}_i), (A, B), \mathcal{A})$ for a $\mathcal{B}$-nice reduction with respect to $\Pi'$, we know that the boundary of each $G_i$ contains at most one vertex of $B$, and hence which is not annotated (the annotated vertices are those in $A = \cup \mathcal{A}$). To show that $\Pi'$ is $\mathcal{B}$-nice, we thus essentially need to show how to reduce a graph $\mathbf{F} \oplus \mathbf{G}$ to a graph $F'$ when the boundary of $\mathbf{F}$ and $\mathbf{G}$ is totally annotated (and that $\Pi'$ has the gluing property), and when the boundary of $\mathbf{F}$ and $\mathbf{G}$ has a single vertex $v$ that is not annotated. To show that $\Pi$ is FPT parameterized by $\mathbf{btw}$, it then suffices to prove that $\Pi'$ is FPT parameterized by $\mathbf{oct}$ on instances where a minimal odd cycle transversal is annotated.

4.4.1. $K_t$-Subgraph-Cover

Let $\mathcal{G}$ be a graph class. The problem VERTEX DELETION TO $\mathcal{G}$ is defined as follows.

(WEIGHTED) VERTEX DELETION TO G

Input: A graph $G$ (and a weight function $w : V(G) \to \mathbb{N}$).

**Objective:** Find the set $S \subseteq V(G)$ of minimum size (resp. weight) such that $G \setminus S \in \mathcal{G}$.

If $\mathcal{G}$ is the class of edgeless (resp. acyclic, planar, bipartite, (proper) interval, chordal) graphs, then we obtain the VERTEX COVER (resp. FEEDBACK VERTEX SET, VERTEX PLANARIZATION, ODD CYCLE TRANSVERSAL, (PROPER) INTERVAL VERTEX DELETION, CHORDAL VERTEX DELETION) problem. Also, given a graph $H$, if $\mathcal{G}$ is the class of graphs that do not contain $H$ as a subgraph (resp. a minor/odd-minor/induced subgraph), then the corresponding problem is called $H$-SUBGRAPH-COVER (resp. $H$-MINOR-COVER/$H$-ODD-MINOR-COVER/$H$-INDUCED-SUBGRAPH-COVER).

Let $H$ be a graph and $w: V(G) \to \mathbb{N}$ be a weight function (assigning one to every vertex in the unweighted case). We define $f_H$ as the 2-partition-evaluation function where, for every graph $G$, for every $(R, S) \in \mathcal{P}_2(V(G))$,

$$
f_H(G, (R, S)) = \begin{cases} +\infty & \text{if } H \text{ is a subgraph of } G \setminus S, \\ w(S) & \text{otherwise.} \end{cases}
$$

Seen as an optimization problem, (WEIGHTED) *H*-SUBGRAPH-COVER is the problem of computing $\mathbf{p}_{f_H, \min}(G)$. We call its annotated extension (WEIGHTED) ANNOTATED *H*-SUBGRAPH-COVER. In other words, (WEIGHTED) ANNOTATED *H*-SUBGRAPH-COVER is defined as follows.
(WEIGHTED) ANNOTATED H-SUBGRAPH-COVER

**Input:** A graph $G$, two disjoint sets $R, S \subseteq V(G)$ (and a weight function $w: V(G) \to \mathbb{N}$).

**Objective:** Find, if it exists, the minimum size (resp. weight) of a set $S^* \subseteq V(G)$ such that $R \cap S^* = \emptyset$, $S \subseteq S^*$, and $G \setminus S^*$ does not contain $H$ as a subgraph.

Given a graph $G$ and a set $X \subseteq V(G)$, note that $X$ is a vertex cover if and only if $V(G) \setminus X$ is an independent set. Hence, the size/weight of a minimum vertex cover is equal to the size/weight of a maximum independent set. Thus, seen as optimization problems, (WEIGHTED) VERTEX COVER and (WEIGHTED) INDEPENDENT SET are equivalent problems.

In order to prove that (WEIGHTED) ANNOTATED $K_t$-SUBGRAPH-COVER is a nice problem, we first prove that (WEIGHTED) ANNOTATED $K_t$-SUBGRAPH-COVER has the gluing property.

**Lemma 4.2 (Gluing property).** (WEIGHTED) ANNOTATED $K_t$-SUBGRAPH-COVER has the gluing property. More precisely, given two bounded graphs $\mathbf{F} = (F, B_F, \rho_F)$ and $\mathbf{G} = (G, B_G, \rho_G)$, a weight function $w: V(\mathbf{F} \oplus \mathbf{G}) \to \mathbb{N}$, a set $X \subseteq V(\mathbf{F} \oplus \mathbf{G})$ such that $B_F \cap B_G \subseteq X$, and $\mathcal{X} = (R, S) \in \mathcal{P}_2(X)$, we have

$$ \hat{\mathbf{p}}_{f_{K_t}, \min}(\mathbf{F} \oplus \mathbf{G}, \mathcal{X}, w) = \hat{\mathbf{p}}_{f_{K_t}, \min}(F, \mathcal{X} \cap V(F), w) + \hat{\mathbf{p}}_{f_{K_t}, \min}(G, \mathcal{X} \cap V(G), w) - \bar{w}, $$

where $\bar{w} = w(S \cap B_F \cap B_G)$.

*Proof.* Observe that $K_t$ is a subgraph of $\mathbf{F} \oplus \mathbf{G}$ if and only if $K_t$ is a subgraph of $F$ or of $G$.

Let $\mathcal{P} = (R^*, S^*) \in \mathcal{P}_2(V(\mathbf{F} \oplus \mathbf{G}))$ be such that $\mathcal{X} \subseteq \mathcal{P}$ and $\hat{\mathbf{p}}_{f_{K_t}, \min}(\mathbf{F} \oplus \mathbf{G}, \mathcal{X}, w) = f_{K_t}(\mathbf{F} \oplus \mathbf{G}, \mathcal{P}, w)$. Then $K_t$ is neither a subgraph of $F \setminus (S^* \cap V(F))$ nor of $G \setminus (S^* \cap V(G))$. Therefore,

$$ \begin{aligned} \hat{\mathbf{p}}_{f_{K_t}, \min}(\mathbf{F} \oplus \mathbf{G}, \mathcal{X}, w) &= w(S^*) \\ &= w(S^* \cap V(F)) + w(S^* \cap V(G)) - w(S^* \cap B_F \cap B_G) \\ &\geq \hat{\mathbf{p}}_{f_{K_t}, \min}(F, \mathcal{X} \cap V(F), w) + \hat{\mathbf{p}}_{f_{K_t}, \min}(G, \mathcal{X} \cap V(G), w) - \bar{w}. \end{aligned} $$

Reciprocally, let $\mathcal{P}_H = (R_H, S_H) \in \mathcal{P}_2(V(H))$ be such that $\mathcal{X} \cap V(H) \subseteq \mathcal{P}_H$ and $\hat{\mathbf{p}}_{f_{K_t}, \min}(H, \mathcal{X} \cap V(H)) = f_{K_t}(H, \mathcal{P}_H)$ for $H \in \{F, G\}$. Then $K_t$ is not a subgraph of $(\mathbf{F} \oplus \mathbf{G}) \setminus (S_F \cup S_G)$, so

$$ \begin{aligned} \hat{\mathbf{p}}_{f_{K_t}, \min}(\mathbf{F} \oplus \mathbf{G}, \mathcal{X}, w) &\leq w(S_F \cup S_G) \\ &= w(S_F) + w(S_G) - \bar{w} \\ &= \hat{\mathbf{p}}_{f_{K_t}, \min}(F, \mathcal{X} \cap V(F), w) + \hat{\mathbf{p}}_{f_{K_t}, \min}(G, \mathcal{X} \cap V(G), w) - \bar{w}. \end{aligned} $$

□

The main obstacle to find an FPT-algorithm parameterized by $(1, \mathcal{H})$-tw for (WEIGHTED) ANNOTATED H-SUBGRAPH-COVER, for $H$ that is not a clique, is the fact that the problem does not have the gluing property.

**Lemma 4.3.** If $H$ is not a complete graph, then (WEIGHTED) ANNOTATED H-SUBGRAPH-COVER does not have the gluing property.

*Proof.* Since $H$ is not a clique, there are two vertices $u, v \in V(H)$ that are not adjacent. Let $V' = V(H) \setminus \{u, v\}$ and let $\sigma: V' \to \mathbb{N}$ be an injection. Let $\mathbf{F} = (H \setminus \{u\}, V', \sigma)$ and $\mathbf{G} = (H \setminus \{v\}, V', \sigma)$. Then $\mathbf{F} \oplus \mathbf{G}$ is isomorphic to $H$. Let $\mathcal{X} = (V', \emptyset)$ and $\mathcal{P} = (H \setminus \{u\}, \{u\}) \supseteq \mathcal{X}$. Then we have $\hat{\mathbf{p}}_{f_H, \min}(\mathbf{F} \oplus \mathbf{G}, \mathcal{X}) = f_H(\mathbf{F} \oplus \mathbf{G}, \mathcal{P}) = 1$. However, $\hat{\mathbf{p}}_{f_H, \min}(G, \mathcal{X} \cap V(G)) = 0 < f_H(G, \mathcal{P} \cap V(G)) = 1$. □

We now show how to reduce a graph $\mathbf{F} \oplus \mathbf{G}$ when the boundary of $\mathbf{F}$ and $\mathbf{G}$ has a single vertex $v$ that is not annotated. Essentially, given an annotation $(R, S)$, we compare the size $s^+$ of an optimal solution
<figure><img src="image_9.png" /><figcaption>Figure 8: Illustration of the gadgetization for $K_t$-SUBGRAPH-COVER.</figcaption></figure>

when $v$ is added to $S$ and the size $s^-$ of an optimal solution when $v$ is added to $R$. If $s^+ \le s^-$, then it is always better too add $v$ to $S$, so we do so and delete $V(G) \setminus V(F)$ from $\mathbf{F} \oplus \mathbf{G}$. Otherwise, we still delete $V(G) \setminus V(F)$ from $\mathbf{F} \oplus \mathbf{G}$, but there is no need to annotate $v$, whose addition to $S$ or not will be determined by its behaviour in $F$. See Figure 8 for an illustration.

**Lemma 4.4 (Gadgetization).** Let $\mathbf{F} = (F, B_F, \rho_F)$ and $\mathbf{G} = (G, B_G, \rho_G)$ be two bounded graphs. Let $X \subseteq V(\mathbf{F} \oplus \mathbf{G})$ be such that $B_F \cap B_G \subseteq X$. Let also $v \in B_F \cap B_G$ and let $\mathcal{X} = (R, S) \in \mathcal{P}_2(X \setminus \{v\})$. We define $\mathcal{X}^+ = (R, S \cup \{v\})$ and $\mathcal{X}^- = (R \cup \{v\}, S)$. Furthermore, for $a \in \{+, -\}$, we set $s^a = \hat{p}_{f_{K_t}, \min}(G, \mathcal{X}^a \cap V(G))$, and we set $\bar{s} = |S \cap B_F \cap B_G|$. Then, for any $t \in \mathbb{N}$,

$$ \hat{p}_{f_{K_t}, \min}(\mathbf{F} \oplus \mathbf{G}, \mathcal{X}) = \begin{cases} s^+ + \hat{p}_{f_{K_t}, \min}(F, \mathcal{X}^+ \cap V(F)) - \bar{s} - 1 & \text{if } s^+ \le s^-, \\ s^- + \hat{p}_{f_{K_t}, \min}(F, \mathcal{X} \cap V(F)) - \bar{s} & \text{otherwise.} \end{cases} $$

*Proof.* For $H \in \{F, G\}$ and for $a \in \{+, -\}$, let $S_H^a \subseteq V(H)$ be such that $\mathcal{X}^a \cap V(H) \subseteq (V(H) \setminus S_H^a, S_H^a)$ and $\hat{p}_{f_{K_t}, \min}(H, \mathcal{X}^a \cap V(H)) = f_{K_t}(H, (V(H) \setminus S_H^a, S_H^a)) = |S_H^a|$. We deduce that $s^+ = |S_G^+|$ and $s^- = |S_G^-|$. Let us note similarly $t^+ = |S_F^+|$ and $t^- = |S_F^-|$.

Note that $S_F^+ \cap S_G^+ = (S \cap B_F \cap B_G) \cup \{v\}$ and $S_F^- \cap S_G^- = S \cap B_F \cap B_G$. Hence, using Lemma 4.2, we have that

$$ \begin{aligned} \hat{p}_{f_{K_t}, \min}(\mathbf{F} \oplus \mathbf{G}, \mathcal{X}) &= \min\{\hat{p}_{f_{K_t}, \min}(\mathbf{F} \oplus \mathbf{G}, \mathcal{X}^+), \hat{p}_{f_{K_t}, \min}(\mathbf{F} \oplus \mathbf{G}, \mathcal{X}^-)\} \\ &= \min\{t^+ + s^+ - 1, t^- + s^-\} - \bar{s}. \end{aligned} $$

Note that we always have $s^+ \le s^- + 1$ since $G \setminus (S_G^- \cup \{v\})$ does not contain $K_t$ as a subgraph, and thus $|S_G^- \cup \{v\}| \ge \hat{p}_{f_{K_t}, \min}(G, \mathcal{X}^+ \cap V(G))$. Similarly, $t^+ \le t^- + 1$.

Thus, if $s^+ \le s^-$, then $t^+ + s^+ - 1 \le t^- + s^+ \le t^- + s^-$. Given that $t^+ = \hat{p}_{f_{K_t}, \min}(F, \mathcal{X}^+ \cap V(F))$, it follows that

$$ \hat{p}_{f_{K_t}, \min}(\mathbf{F} \oplus \mathbf{G}, \mathcal{X}) = \hat{p}_{f_{K_t}, \min}(F, \mathcal{X}^+ \cap V(F)) + s^+ - \bar{s} - 1. $$

And if $s^- < s^+$, then $s^+ = s^- + 1$, so $\min\{t^+ + s^+ - 1, t^- + s^-\} = \min\{t^+, t^-\} + s^- = \hat{p}_{f_{K_t}, \min}(F, \mathcal{X} \cap V(F)) + s^-$. It follows that

$$ \hat{p}_{f_{K_t}, \min}(\mathbf{F} \oplus \mathbf{G}, \mathcal{X}) = \hat{p}_{f_{K_t}, \min}(F, \mathcal{X} \cap V(F)) + s^- - \bar{s}. $$

□

Contrary to Lemma 4.2, observe that Lemma 4.4 only holds in the unweighted case. Indeed, in the weighted case, we now have $s^+ \le s^- + w(v)$, and thus, when $s^+ \in [s^- + 1, s^- + w(v) - 1]$, we do not know what happens.
Using Lemma 4.2 and Lemma 4.4, we can now prove that ANNOTATED K_t-SUBGRAPH-COVER is H-nice. Essentially, given an instance (G = X ⊕ (⊕_{i∈[d]} G_i), (A, B), (R, S)), we reduce G to X and further remove some vertices of B that can be optimally added to S, and show that the resulting bounded graph is equivalent to G modulo some constant s.

**Lemma 4.5 (Nice problem).** Let $\mathcal{H}$ be a hereditary graph class. Let $t \in \mathbb{N}$. ANNOTATED K_t-SUBGRAPH-COVER is $\mathcal{H}$-nice.

*Proof.* Let $G = (G, X, \rho)$ be a bounded graph, let $X = (G[X], X, \rho_X)$ be a trivial bounded graph and let $\{G_i = (G_i, X_i, \rho_i) | i \in [d]\}$ be a collection of bounded graphs, such that $G = X \oplus (\oplus_{i \in [d]} G_i)$, let $(A, B)$ be a partition of $X$ such that for all $i \in [d]$, $|X_i \setminus A| \le 1$, and let $\mathcal{A} = (R, S) \in \mathcal{P}_2(A)$. Suppose that we know, for every $i \in [d]$ and each $\mathcal{X}_i \in \mathcal{P}_2(X_i)$, the value $\hat{\rho}_{f_{K_t}, \min}(G_i, \mathcal{X}_i)$.

Let us show that item (iii) holds (recall that $\mathcal{H}$-niceness is defined in Subsection 4.1). Let $(\mathbf{H}_0, S_0, s_0) = (\mathbf{G}, S, 0)$. For $i$ going from 1 up to $d$, we construct $(\mathbf{H}_i, S_i, s_i)$ from $(\mathbf{H}_{i-1}, S_{i-1}, s_{i-1})$ such that for any bounded graph $\mathbf{F}$ compatible with $\mathbf{G}$,

$$ \hat{\rho}_{f_{K_t}, \min}(\mathbf{G} \oplus \mathbf{F}, \mathcal{A}) = \hat{\rho}_{f_{K_t}, \min}(\mathbf{H}_i \oplus \mathbf{F}, \mathcal{A}_i) + s_i, $$

where $\mathcal{A}_i = (R, S_i)$. This is obviously true for $i = 0$.

Let $i \in [d]$. Let $\mathbf{H}_i$ be the bounded graph such that $\mathbf{H}_{i-1} = \mathbf{H}_i \oplus \mathbf{G}_i$. See Figure 9 for an illustration. By induction, $\hat{\rho}_{f_{K_t}, \min}(\mathbf{G} \oplus \mathbf{F}, \mathcal{A}) = \hat{\rho}_{f_{K_t}, \min}(\mathbf{H}_{i-1} \oplus \mathbf{F}, \mathcal{A}_{i-1}) + s_{i-1}$.

<figure><img src="image_10.png" /><figcaption>Figure 9: Illustration of $\mathbf{G}$ and $\mathbf{H}_{i-1}$ in the proof of Lemma 4.5.</figcaption></figure>

Suppose first that $X_i \subseteq R \cup S_{i-1}$. Let $\mathcal{P}_i = (R^i, S^i) \in \mathcal{P}_2(X)$ be such that $\mathcal{A}_{i-1} \subseteq \mathcal{P}_i$ and $\hat{\rho}_{f_{K_t}, \min}(\mathbf{H}_{i-1} \oplus \mathbf{F}, \mathcal{A}_{i-1}) = \hat{\rho}_{f_{K_t}, \min}(\mathbf{H}_{i-1} \oplus \mathbf{F}, \mathcal{P}_i)$. Let $F$ be the underlying graph of $\mathbf{F}$. According to Lemma 4.2,

$$ \begin{aligned} \hat{\rho}_{f_{K_t}, \min}(\mathbf{H}_{i-1} \oplus \mathbf{F}, \mathcal{P}_i) &= \hat{\rho}_{f_{K_t}, \min}(F, \mathcal{P}_i) + \hat{\rho}_{f_{K_t}, \min}(H_{i-1}, \mathcal{P}_i) - |X_i \cap S^i| \\ &= \hat{\rho}_{f_{K_t}, \min}(F, \mathcal{P}_i) + \hat{\rho}_{f_{K_t}, \min}(H_i, \mathcal{P}_i) \\ &\quad + \hat{\rho}_{f_{K_t}, \min}(G_i, \mathcal{P}_i \cap X_i) - |X_i \cap S^i| - |X_i \cap S^i| \\ &= \hat{\rho}_{f_{K_t}, \min}(\mathbf{H}_i \oplus \mathbf{F}, \mathcal{P}_i) + \hat{\rho}_{f_{K_t}, \min}(G_i, \mathcal{A}_{i-1} \cap X_i) - |S_{i-1} \cap X_i|. \end{aligned} $$

Since this is the case for all such $\mathcal{P}_i$, it implies that

$$ \hat{\rho}_{f_{K_t}, \min}(\mathbf{H}_{i-1} \oplus \mathbf{F}, \mathcal{A}_{i-1}) = \hat{\rho}_{f_{K_t}, \min}(\mathbf{H}_i \oplus \mathbf{F}, \mathcal{A}_{i-1}) + \hat{\rho}_{f_{K_t}, \min}(G_i, \mathcal{A}_{i-1} \cap X_i) - |S_{i-1} \cap X_i|. $$

Therefore,

$$ \hat{\rho}_{f_{K_t}, \min}(\mathbf{G} \oplus \mathbf{F}, \mathcal{A}) = \hat{\rho}_{f_{K_t}, \min}(\mathbf{H}_i \oplus \mathbf{F}, \mathcal{A}_i) + s_i, $$

where $\mathcal{A}_i = \mathcal{A}_{i-1}$ and $s_i = s_{i-1} + \hat{\rho}_{f_{K_t}, \min}(G_i, \mathcal{A}_{i-1} \cap X_i) - |S_{i-1} \cap X_i|$.

Otherwise, there is $v_i \in V(G_{i-1})$ such that $X_i \setminus (R \cup S_{i-1}) = \{v_i\}$. Let $\mathcal{X}_i^+ = (R, S_{i-1} \cup \{v_i\}) \cap X_i$ and $\mathcal{X}_i^- = (R \cup \{v_i\}, S_{i-1}) \cap X_i$. Let $\mathcal{P}_i = (R^i, S^i) \in \mathcal{P}_2(X \setminus \{v_i\})$ be such that $\mathcal{A}_{i-1} \subseteq \mathcal{P}_i$ and $\hat{\rho}_{f_{K_t}, \min}(\mathbf{H}_{i-1} \oplus \mathbf{F}, \mathcal{A}_{i-1}) = \hat{\rho}_{f_{K_t}, \min}(\mathbf{H}_{i-1} \oplus \mathbf{F}, \mathcal{P}_i)$. Note that

$$ \mathbf{H}_{i-1} \oplus \mathbf{F} = (\mathbf{H}_i \oplus \mathbf{G}_i) \oplus \mathbf{F} = (\mathbf{H}_i \oplus \mathbf{F}) \oplus \mathbf{G}_i. $$
For $a \in \{+, -\}$, let $s_i^a = \mathbf{p}_{f_{K_t}, \min}(G, \mathcal{X}_i^a)$. Then, using Lemma 4.4, we have the following case distinction.

$$ \begin{aligned} \hat{\mathbf{p}}_{f_{K_t}, \min}(\mathbf{H}_{i-1} \oplus \mathbf{F}, \mathcal{P}_i) &= \hat{\mathbf{p}}_{f_{K_t}, \min}((\mathbf{H}_i \boxplus \mathbf{F}) \oplus \mathbf{G}_i \oplus \mathbf{F}, \mathcal{P}_i) \\ &= \begin{cases} s_i^+ + \hat{\mathbf{p}}_{f_{K_t}, \min}(\mathbf{H}_i \oplus \mathbf{F}, (R^i, S^i \cup \{v_i\})) - |S_{i-1} \cap X_i| - 1 & \text{if } s_i^+ \le s_i^- \\ s_i^- + \hat{\mathbf{p}}_{f_{K_t}, \min}(\mathbf{H}_i \oplus \mathbf{F}, \mathcal{P}_i) - |S_{i-1} \cap X_i| & \text{otherwise.} \end{cases} \end{aligned} $$

Since this is the case for every such $\mathcal{P}_i$, by setting $(\mathbf{H}_i, S_i, s_i) = (\mathbf{H}_i, S_{i-1} \cup \{v_i\}, s_{i-1} + s^+ - |S_{i-1} \cap X_i| - 1)$ if $s^+ \le s^-$ and $(\mathbf{H}_i, S_i, s_i) = (\mathbf{H}_i, S_{i-1}, s_{i-1} + s^- - |S_{i-1} \cap X_i|)$ otherwise, we have that

$$ \hat{\mathbf{p}}_{f_{K_t}, \min}(\mathbf{G} \oplus \mathbf{F}, \mathcal{A}) = \hat{\mathbf{p}}_{f_{K_t}, \min}(\mathbf{H}_i \oplus \mathbf{F}, \mathcal{A}_i) + s_i. $$

The bounded graph $\mathbf{H}_d$ obtained at the end is isomorphic to $\mathbf{X}$. Let $S_B = S_d \setminus S \subseteq B$. Observe that

$$ \begin{aligned} \hat{\mathbf{p}}_{f_{K_t}, \min}(\mathbf{H}_d \oplus \mathbf{F}, \mathcal{A}_d) &= \hat{\mathbf{p}}_{f_{K_t}, \min}((\mathbf{H}_d \oplus \mathbf{F}) \setminus S_B, \mathcal{A}_d \setminus S_B) + |S_B| \\ &= \hat{\mathbf{p}}_{f_{K_t}, \min}((\mathbf{H}_d \setminus S_B) \triangleright \mathbf{F}, \mathcal{A}) + |S_B| \end{aligned} $$

Hence,

$$ \hat{\mathbf{p}}_{f_{K_t}, \min}(\mathbf{G} \oplus \mathbf{F}, \mathcal{A}) = \hat{\mathbf{p}}_{f_{K_t}, \min}((\mathbf{X} \setminus S_B) \triangleright \mathbf{F}, \mathcal{A}) + |S_B| + s_d. $$

Let $\mathbf{H} = \mathbf{X} \setminus S_B$. Item (i) holds trivially. Item (ii) also holds, given that $|V(H)| \le |X|$ and $|E(H)| \le E(G[X])$, where $H$ is the underlying graph of $\mathbf{H}$. Given that $S_B \subseteq B \subseteq X$, it implies that $\mathbf{H} \triangleright \mathbf{F}$ is isomorphic to $F \setminus S_B$. Thus, since $\mathcal{H}$ is hereditary, if $F \setminus A$ belongs to $\mathcal{H}$, then so does $(\mathbf{H} \triangleright \mathbf{F}) \setminus A$. So item (iv) holds. Hence, $(\mathbf{X} \setminus S_B, \mathcal{A}, |S_B| + s_d)$ follows every conditions so that it is an $\mathcal{H}$-nice reduction of $(G, \mathcal{A})$ with respect to ANNOTATED $K_t$-SUBGRAPH-COVER.

At each step $i$, we compute $|S_{i-1} \cap X_i|$, and thus $s_i$, in time $\mathcal{O}(|A|)$ (since $\hat{\mathbf{p}}_{f_{K_t}, \min}(G_i, \mathcal{X}_i)$ is supposed to be known). $\mathbf{H}_i$ and $S_i$ are then constructed in time $\mathcal{O}(1)$. Hence, the computation takes time $\mathcal{O}(|A| \cdot d)$, and thus, ANNOTATED $K_t$-SUBGRAPH-COVER is $\mathcal{H}$-nice. $\square$

We now solve WEIGHTED ANNOTATED $K_t$-SUBGRAPH-COVER for $t \ge 3$ parameterized by oct. Note that WEIGHTED VERTEX COVER can be solved on bipartite graphs in time $\mathcal{O}(m^{1+o(1)})$ using a flow algorithm [27]. Indeed, let $G = (A, B)$ be a bipartite graph and $w: V(G) \to \mathbb{N}$ be a weight function. We construct a flow network $N$ by connecting a source $s$ to each vertex in $A$ and a sink $t$ to each vertex in $B$. We give infinite capacity to the original edges of $G$, and capacity $w(v)$ to each edge connecting a vertex $v$ and a terminal vertex. Every $s-t$ cut in $N$ corresponds to exactly one vertex cover and every vertex cover corresponds to an $s-t$ cut. Thus a minimum cut of $N$ gives a minimum weight vertex cover of $G$.

**Lemma 4.6.** Let $t \in \mathbb{N}_{\ge 2}$. There is an algorithm that, given a graph $G$ and two disjoint sets $R, S \subseteq V(G)$ such that $G' = G \setminus (R \cup S)$ is bipartite, solves WEIGHTED ANNOTATED $K_t$-SUBGRAPH-COVER on $(G, R, S)$ in time $\mathcal{O}(k^t \cdot (n' + m') + (m')^{1+o(1)})$, where $k = |R|$, $n' = |V(G')|$, and $m' = |E(G')|$.

*Proof.* Observe that we can assume that $S = \emptyset$, since $S^*$ is an optimal solution for $(G, R, S)$ if and only if $S^* \setminus S$ is an optimal solution for $(G \setminus S, R, \emptyset)$. Thus, $G \setminus R$ is bipartite, so for any occurrence of $K_t$ contained in $G$ (as a subgraph), at most two of its vertices belong to $G \setminus R$. Hence, enumerating the occurrences of $K_t$ takes time $\mathcal{O}(k^t + k^{t-1} \cdot n' + k^{t-2} \cdot m')$. If $G[R]$ contains an occurrence of $K_t$, then WEIGHTED ANNOTATED $K_t$-SUBGRAPH-COVER has no solution. Let us thus assume that $G[R]$ contains no $K_t$. For each occurrences of $K_t$ in $G$ that contains $t-1$ vertices of $R$ and one vertex $v \in V(G) \setminus R$, we add $v$ to $S^*$ and remove $v$ from $G$, since $v$ has to be taken in the solution. Hence, all that remains are occurrences of $K_t$ with $t-2$ vertices in $R$ and the two others in $G \setminus R$. Let $H$ be the graph induced by the edges of the occurrences of $K_t$ in $G$ with both endpoints in $G \setminus R$. Each edge of $H$ intersects any solution $\bar{S}$ on $G$ for WEIGHTED ANNOTATED $K_t$-SUBGRAPH-COVER. Hence, $\bar{S}$ is the union of $S^*$ and a minimum weighted vertex cover $C$ of $H$. Thus, $C$ can be computed in time $\mathcal{O}((m')^{1+o(1)})$. The running time of the algorithm is hence $\mathcal{O}(k^t + k^{t-1} \cdot n' + k^{t-2} \cdot m' + (m')^{1+o(1)})$. $\square$
We apply Lemma 4.5 and Lemma 4.6 to the dynamic programming algorithm of Lemma 4.1 to obtain the following result.

**Corollary 4.1.** Let $t \in \mathbb{N}_{\ge 2}$. Given a graph $G$ and a bipartite tree decomposition of $G$ of width $k$, there is an algorithm that solves $K_t$-SUBGRAPH-COVER on $G$ in time $O(2^k \cdot (k^t \cdot (n+m) + m^{1+o(1)}))$.

### 4.4.2. Weighted Vertex Cover/Weighted Independent Set

Given that Lemma 4.4 only holds for $K_t$-SUBGRAPH-COVER in the unweighted case, we propose here an analogous result that holds in the weighted case, when we restrict ourselves to $t = 2$, i.e., WEIGHTED VERTEX COVER. We already know that WEIGHTED VERTEX COVER has the gluing property (Lemma 4.2). We now show how to reduce a graph $\mathbf{F} \oplus \mathbf{G}$ to a graph $F'$ when the boundary of $\mathbf{F}$ and $\mathbf{G}$ has a single vertex $v$ that is not annotated. Recall that this reduction was sketched in Section 2, and see Figure 10 for an illustration.

<figure><img src="image_11.png" /><figcaption>Figure 10: Illustration of the gadgetization for WEIGHTED VERTEX COVER.</figcaption></figure>

**Lemma 4.7 (Gadgetization).** Let $\mathbf{F} = (F, B_F, \rho_F)$ and $\mathbf{G} = (G, B_G, \rho_G)$ be two bounded graphs. Let $w: V(\mathbf{F} \oplus \mathbf{G}) \to \mathbb{N}$ be a weight function, let $X \subseteq V(\mathbf{F} \oplus \mathbf{G})$ be such that $B_F \cap B_G \subseteq X$, let $v \in B_F \cap B_G$, and let $\mathcal{X} = (R, S) \in \mathcal{P}_2(X \setminus \{v\})$. We define $\mathcal{X}^+ = (R, S \cup \{v\})$ and $\mathcal{X}^- = (R \cup \{v\}, S)$. Furthermore, for $a \in \{+, -\}$, we set $s^a = \hat{p}_{f_{K_t}, \min}(G, \mathcal{X}^a \cap V(G), w)$. We also set $\bar{w} = w(S \cap B_F \cap B_G)$, $\mathbf{G}' = (G', \{v\}, \rho_{|\{v\}})$, where $G'$ is an edge $vv^-$ for some new vertex $v^-$, and $w' : V(\mathbf{F} \oplus \mathbf{G}') \to \mathbb{N}$ such that $w'(v) = s^+ - \bar{w}$, $w'(v^-) = s^- - \bar{w}$, and $w'(x) = w(x)$ otherwise. Then

$$ \hat{p}_{f_{K_2}, \min}(\mathbf{F} \oplus \mathbf{G}, \mathcal{X}, w) = \hat{p}_{f_{K_2}, \min}(\mathbf{F} \oplus \mathbf{G}', \mathcal{X}, w'). $$

*Proof.* For $a \in \{+, -\}$, let $t^a = \hat{p}_{f_{K_t}, \min}(F, \mathcal{X}^a \cap V(F), w)$.

Note that

$$ \begin{aligned} s'^- &:= \hat{p}_{f_{K_2}, \min}(G', \mathcal{X}^- \cap V(G'), w') = \hat{p}_{f_{K_2}, \min}(G', (\{v\}, \emptyset), w') \\ &= w'(v^-) \\ &= s^- - \bar{w}, \end{aligned} $$

$$ \begin{aligned} s'^+ &:= \hat{p}_{f_{K_2}, \min}(G', \mathcal{X}^+ \cap V(G'), w') = \hat{p}_{f_{K_2}, \min}(G', (\emptyset, \{v\}), w') \\ &= w'(v) \\ &= s^+ - \bar{w}, \end{aligned} $$

$$ t'^- := \hat{p}_{f_{K_2}, \min}(F, \mathcal{X}^- \cap V(F), w') = t^-, \text{ and} $$

$$ t'^+ := \hat{p}_{f_{K_2}, \min}(F, \mathcal{X}^+ \cap V(F), w') = t^+ + w'(v) - w(v). $$
Hence, using Lemma 4.2, we have that

$$
\begin{align*}
\hat{\mathbf{p}}_{f_{K_2}, \min}(\mathbf{F} \oplus \mathbf{G}, \mathcal{X}, w) & \\
&= \min\{\hat{\mathbf{p}}_{f_{K_2}, \min}(\mathbf{F} \oplus \mathbf{G}, \mathcal{X}^+, w), \hat{\mathbf{p}}_{f_{K_2}, \min}(\mathbf{F} \oplus \mathbf{G}, \mathcal{X}^-, w)\} \\
&= \min\{t^+ + s^+ - w(v), t^- + s^-\} - \bar{w} \\
&= \min\{t^+ + s'^+ - w(v), t^- + s'^-\} \\
&= \min\{t'^+ + s'^+ - w'(v), t'^- + s'^-\} \\
&= \min\{\hat{\mathbf{p}}_{f_{K_2}, \min}(\mathbf{F} \oplus \mathbf{G}', \mathcal{X}^+, w'), \hat{\mathbf{p}}_{f_{K_2}, \min}(\mathbf{F} \oplus \mathbf{G}', \mathcal{X}^-, w')\} \\
&= \hat{\mathbf{p}}_{f_{K_2}, \min}(\mathbf{F} \oplus \mathbf{G}', \mathcal{X}, w').
\end{align*}
$$

□

Using Lemma 4.2 and Lemma 4.7, we can now prove that WEIGHTED ANNOTATED VERTEX COVER is $\mathcal{H}$-nice. Essentially, given an instance $(\mathbf{G} = \mathbf{X} \boxplus (\boxplus_{i \in [d]} \mathbf{G}_i), (A, B), (R, S), w)$, we reduce $\mathbf{G}$ to $\mathbf{X}$ where we glue an edge to some vertices in $B$. We then show that if the appropriate weight is given to each new vertex, then the resulting bounded graph is equivalent to $\mathbf{G}$ modulo some constant $s$.

**Lemma 4.8 (Nice problem).** Let $\mathcal{H}$ be a graph class that is closed under 1-clique-sums and contains $K_2$. Then WEIGHTED ANNOTATED VERTEX COVER is $\mathcal{H}$-nice.

*Proof.* Let $\mathbf{G} = (G, X, \rho)$ be a bounded graph, let $w: V(G) \to \mathbb{N}$ be a weight function, let $\mathbf{X} = (G[X], X, \rho_X)$ be a trivial bounded graph and let $\{\mathbf{G}_i = (G_i, X_i, \rho_i) \mid i \in [d]\}$ be a collection of bounded graphs, such that $\mathbf{G} = \mathbf{X} \boxplus (\boxplus_{i \in [d]} \mathbf{G}_i)$, let $(A, B)$ be a partition of $X$ such that for all $i \in [d]$, $|X_i \setminus A| \le 1$, and let $\mathcal{A} = (R, S) \in \mathcal{P}_2(A)$. Suppose that we know, for every $i \in [d]$ and each $\mathcal{X}_i \in \mathcal{P}_2(X_i)$, the value $\hat{\mathbf{p}}_{f_{K_i}, \min}(G_i, \mathcal{X}_i, w)$. Recall the $\mathcal{H}$-niceness was defined in Subsection 4.1.

Let $v_1, \dots, v_{|B|}$ be the vertices of $B$. For $i \in [|B|]$, let $I_i = \{j \in [d] \mid X_j \setminus A = \{v_i\}\}$. Let $I_0 = \{j \in [d] \mid X_j \subseteq A\}$. Obviously, $(I_i)_{i \in [0, |B|]}$ is a partition of $[d]$. Let $\mathbf{G}'_i = \boxplus_{j \in I_i} \mathbf{G}_j$. See Figure 11 for an illustration.

<figure><img src="image_12.png" /><figcaption>Figure 11: Illustration of $\mathbf{G}'_i$ in the proof of Lemma 4.8.</figcaption></figure>

Let us show that item (iii) holds. Let $(\mathbf{H}_{-1}, w_{-1}, s_{-1}) = (\mathbf{G}, w, 0)$. For $i$ going from 0 up to $|B|$, we will construct $(\mathbf{H}_i, w_i, s_i)$ from $(\mathbf{H}_{i-1}, w_{i-1}, s_{i-1})$ such that $(w_i)_{|V(F) \setminus \{v_j | j \le i\}} = w_{|V(F) \setminus \{v_j | j \le i\}}$ and $(w_i)_{|V(G'_j)} = w_{|V(G'_j)}$, for $j > i$, and for any bounded graph $\mathbf{F}$ with underlying graph $F$ and compatible with $\mathbf{G}$,

$$ \hat{\mathbf{p}}_{f_{K_2}, \min}(\mathbf{G} \oplus \mathbf{F}, \mathcal{A}, w) = \hat{\mathbf{p}}_{f_{K_2}, \min}(\mathbf{H}_i \oplus \mathbf{F}, \mathcal{A}, w_i) + s_i. $$

This is obviously true for $i = -1$.

Let $i \in [0, |B|]$. Let $\mathbf{H}'_i$ be the bounded graph with underlying graph $\mathbf{H}'_i$ such that $\mathbf{H}_{i-1} = \mathbf{H}'_i \boxplus \mathbf{G}'_i$. By induction, we have

$$ \hat{\mathbf{p}}_{f_{K_2}, \min}(\mathbf{G} \oplus \mathbf{F}, \mathcal{A}, w) = \hat{\mathbf{p}}_{f_{K_2}, \min}(\mathbf{H}_{i-1} \oplus \mathbf{F}, \mathcal{A}, w_{i-1}) + s_{i-1}. $$
Suppose first that $i=0$. Let $\mathcal{P}_0 = (\mathbb{R}^0, \mathbb{S}^0) \in \mathcal{P}_2(X)$ be such that $\mathcal{A} \subseteq \mathcal{P}_0$ and $\hat{\mathbf{p}}_{f_{\mathcal{K}_2}, \min}(\mathbf{G} \oplus \mathbf{F}, \mathcal{A}, w) = \hat{\mathbf{p}}_{f_{\mathcal{K}_2}, \min}(\mathbf{G} \oplus \mathbf{F}, \mathcal{P}_0, w)$. According to Lemma 4.2,

$$
\begin{align*}
\hat{\mathbf{p}}_{f_{\mathcal{K}_2}, \min}(\mathbf{G} \oplus \mathbf{F}, \mathcal{P}_0, w) &= \hat{\mathbf{p}}_{f_{\mathcal{K}_2}, \min}(F, \mathcal{P}_0, w) + \hat{\mathbf{p}}_{f_{\mathcal{K}_2}, \min}(G, \mathcal{P}_0, w) - w(X \cap \mathbb{S}^0) \\
&= \hat{\mathbf{p}}_{f_{\mathcal{K}_2}, \min}(F, \mathcal{P}_0, w) - w(X \cap \mathbb{S}^0) + \hat{\mathbf{p}}_{f_{\mathcal{K}_2}, \min}(H'_0, \mathcal{P}_0, w) \\
&\quad + \sum_{j \in I_0} (\hat{\mathbf{p}}_{f_{\mathcal{K}_2}, \min}(G_j, \mathcal{P}_0 \cap X_j, w) - w(\mathbb{S}^0 \cap X_j)) \\
&= \hat{\mathbf{p}}_{f_{\mathcal{K}_2}, \min}(H'_0 \oplus \mathbf{F}, \mathcal{P}_0, w) + \sum_{j \in I_0} (\hat{\mathbf{p}}_{f_{\mathcal{K}_2}, \min}(G_j, \mathcal{A} \cap X_j, w) - w(S \cap X_j)).
\end{align*}
$$

Since this is the case for all such $\mathcal{P}_0$, it implies that

$$
\hat{\mathbf{p}}_{f_{\mathcal{K}_2}, \min}(\mathbf{G} \oplus \mathbf{F}, \mathcal{A}, w) = \hat{\mathbf{p}}_{f_{\mathcal{K}_2}, \min}(\mathbf{H}'_0 \oplus \mathbf{F}, \mathcal{A}, w) + \sum_{j \in I_0} (\hat{\mathbf{p}}_{f_{\mathcal{K}_2}, \min}(G_j, \mathcal{A} \cap X_j, w) - w(S \cap X_j)).
$$

Therefore, if $\mathbf{H}_0 = \mathbf{H}'_0$, $w_0 = w$ and

$$
s_0 = \sum_{j \in I_0} (\hat{\mathbf{p}}_{f_{\mathcal{K}_2}, \min}(G_j, \mathcal{A} \cap X_j, w) - w(S \cap X_j)),
$$

then

$$
\hat{\mathbf{p}}_{f_{\mathcal{K}_2}, \min}(\mathbf{G} \oplus \mathbf{F}, \mathcal{A}, w) = \hat{\mathbf{p}}_{f_{\mathcal{K}_2}, \min}(\mathbf{H}_0 \oplus \mathbf{F}, \mathcal{A}, w_0) + s_0.
$$

Otherwise, $i \in [|B|]$ and $X_j \setminus A = \{v_i\}$ for each $j \in I_i$. Let $X_i' = \bigcup_{j \in I_i} X_j$. Let $\mathcal{X}_i^+ = (R, S \cup \{v_i\}) \cap X_i'$ and $\mathcal{X}_i^- = (R \cup \{v_i\}, S) \cap X_i'$. Let $\mathbf{H}_i'' = (\mathbf{H}_i'', \{v_i\}, \rho_{|\{v_i\}})$ be the bounded graph where $\mathbf{H}_i''$ is an edge $v_i v_i^-$ for some new vertex $v_i^-$. Let $\mathbf{H}_i = \mathbf{H}_i' \boxplus \mathbf{H}_i''$. Let $s_i^+ = \hat{\mathbf{p}}_{f_{\mathcal{K}_t}, \min}(G_i^+, \mathcal{X}_i^+, w)$ and $s_i^- = \hat{\mathbf{p}}_{f_{\mathcal{K}_t}, \min}(G_i^-, \mathcal{X}_i^-, w)$. By Lemma 4.2,

$$
s_i^+ = \sum_{j \in I_i} (\hat{\mathbf{p}}_{f_{\mathcal{K}_t}, \min}(G_j, \mathcal{X}_i^+ \cap X_j, w) - w(S \cap X_j) - w(v_i)) + w(S \cap X_i') + w(v_i),
$$

and

$$
s_i^- = \sum_{j \in I_i} (\hat{\mathbf{p}}_{f_{\mathcal{K}_t}, \min}(G_j, \mathcal{X}_i^- \cap X_j, w) - w(S \cap X_j)) + w(S \cap X_i').
$$

Since the $\hat{\mathbf{p}}_{f_{\mathcal{K}_t}, \min}(G_j, \mathcal{X}_i^a \cap X_j, w)$ are given, $s_i^+$ and $s_i^-$ can be computed in time $\mathcal{O}(|A| \cdot |I_i|)$. Let $w_i : V(\mathbf{F} \oplus \mathbf{H}_i'') \to \mathbb{N}$ be such that $w_i(v_i) = s_i^+ - w(S \cap B_F \cap B_G)$, $w_i(v_i^-) = s_i^- - w(S \cap B_F \cap B_G)$, and $w_i(x) = w(x)$ otherwise. Let $\mathcal{P}_i = (R^i, S^i) \subseteq \mathcal{P}_2(X \setminus \{v_i\})$ be such that $\mathcal{A} \subseteq \mathcal{P}_i$ and $\hat{\mathbf{p}}_{f_{\mathcal{K}_2}, \min}(\mathbf{H}_{i-1} \oplus \mathbf{F}, \mathcal{A}, w_{i-1}) = \hat{\mathbf{p}}_{f_{\mathcal{K}_2}, \min}(\mathbf{H}_{i-1} \oplus \mathbf{F}, \mathcal{P}_i, w_{i-1})$. Then, using Lemma 4.7,

$$
\begin{align*}
\hat{\mathbf{p}}_{f_{\mathcal{K}_2}, \min}(\mathbf{H}_{i-1} \oplus \mathbf{F}, \mathcal{P}_i, w_{i-1}) &= \hat{\mathbf{p}}_{f_{\mathcal{K}_2}, \min}((\mathbf{H}_i' \boxplus \mathbf{F}) \oplus \mathbf{G}_i', \mathcal{P}_i, w_{i-1}) \\
&= \hat{\mathbf{p}}_{f_{\mathcal{K}_2}, \min}((\mathbf{H}_i' \boxplus \mathbf{F}) \oplus \mathbf{H}_i'', \mathcal{P}_i, w_i) \\
&= \hat{\mathbf{p}}_{f_{\mathcal{K}_2}, \min}(\mathbf{H}_i \oplus \mathbf{F}, \mathcal{P}_i, w_i)
\end{align*}
$$

Since this is the case for all such $\mathcal{P}_i$, it implies that

$$
\hat{\mathbf{p}}_{f_{\mathcal{K}_2}, \min}(\mathbf{H}_{i-1} \oplus \mathbf{F}, \mathcal{A}, w_{i-1}) = \hat{\mathbf{p}}_{f_{\mathcal{K}_2}, \min}(\mathbf{H}_i \oplus \mathbf{F}, \mathcal{A}, w_i).
$$

Therefore, given $s_i = s_{i-1}$,

$$
\hat{\mathbf{p}}_{f_{\mathcal{K}_2}, \min}(\mathbf{G} \oplus \mathbf{F}, \mathcal{A}, w) = \hat{\mathbf{p}}_{f_{\mathcal{K}_2}, \min}(\mathbf{H}_i \oplus \mathbf{F}, \mathcal{A}, w_i) + s_i.
$$

Observe that $\mathbf{H}_{|B|} = \mathbf{X} \boxplus (\boxplus_{i \in [|B|]} \mathbf{H}_i'')$ and $\mathbf{H}_{|B|} \oplus \mathbf{F} = \mathbf{F} \oplus (\boxplus_{i \in [|B|]} \mathbf{H}_i'')$. Suppose that $F \setminus A \in \mathcal{H}$. Given that $\mathcal{H}$ is closed under 1-clique-sums and contains edges, that each $\mathbf{H}_i''$ is an edge, and that $|bd(\mathbf{H}_i'')| = 1$,
it follows that $(\mathbf{H}_{|B|} \oplus \mathbf{F}) \setminus A \in \mathcal{H}$. So item (iv) holds. Moreover, item (i) trivially holds and item (ii) holds given that $|V(\mathbf{H}_{|B|})| = |X| + |B|$ and $|E(\mathbf{H}_{|B|})| = |E(G[X])| + |B|$. Hence, $(\mathbf{H}_{|B|}, \mathcal{A}, s_{|B|}, w_{|B|})$ is an $\mathcal{H}$-nice reduction of $(\mathbf{G}, \mathcal{A}, w)$ with respect to WEIGHTED ANNOTATED VERTEX COVER.

At each step $i$, $s_i$ is computable in time $O(|A| \cdot |I_i|)$, and $\mathbf{H}_i$ and $w_i$ are computable in time $O(1)$. Hence, the computation takes time $O(|A| \cdot d)$. Therefore, WEIGHTED ANNOTATED VERTEX COVER is $\mathcal{H}$-nice. $\square$

We now solve WEIGHTED VERTEX COVER/INDEPENDENT SET parameterized by oct with a better running time than Lemma 4.6.

**Observation 4.1.** Let $\mathcal{H}$ be a hereditary graph class such that WEIGHTED VERTEX COVER can be solved on instances $(G, w)$ where $G \in \mathcal{H}$ in time $O(n^c \cdot m^d)$ for some $c, d \in \mathbb{N}$. Then WEIGHTED ANNOTATED VERTEX COVER is solvable on instance $(G, R, S, w)$ such that $G' = G \setminus (R \cup S) \in \mathcal{H}$ in time $O(k \cdot (k+n') + n'^c \cdot m'^d)$, where $n' = |V(G')|, m' = |E(G')|, \text{ and } k = |R|$.

*Proof.* Let $G$ be a graph, $w$ be a weight function, and $R, S \subseteq V(G)$ be two disjoint sets such that $G \setminus (R \cup S) \in \mathcal{H}$. If $R$ is not an independent set, then $(G, R, S, w)$ has no solution. Hence, we assume that $R$ is an independent set. Then $S^* \subseteq V(G)$ is a solution of WEIGHTED ANNOTATED VERTEX COVER on $(G, R, S, w)$ if and only if $S^* = S_B \cup S \cup N_G(R)$ where $S_B$ is a solution of WEIGHTED VERTEX COVER on $(G \setminus (R \cup S), w)$. Checking that $R$ is an independent set takes time $O(k^2)$ and then finding $N_G(R)$ takes time $O(k \cdot n')$, hence the result. $\square$

We apply Lemma 4.8 and Observation 4.1 to the dynamic programming algorithm of Lemma 4.1 to obtain the following result. Note that any graph class that is hereditary and does not contain $K_2$ is edgeless. Given that the problem is trivial on edgeless graphs, we can remove the condition of containing $K_2$.

**Corollary 4.2.** Let $\mathcal{H}$ be a hereditary graph class that is closed under 1-clique-sum. Suppose that WEIGHTED VERTEX COVER can be solved on instances $(G, w)$ where $G \in \mathcal{H}$ in time $O(n^c \cdot m^d)$. Then, given a graph $G$, a 1-$\mathcal{H}$-tree decomposition of $G$ of width $k$, and a weight function $w$, there is an algorithm that solves WEIGHTED VERTEX COVER/WEIGHTED INDEPENDENT SET on $(G, w)$ in time $O(2^k \cdot (k \cdot (k+n) + n^c \cdot m^d))$.

Given that the class $\mathcal{B}$ of bipartite graphs is hereditary, closed under 1-clique-sums, and that WEIGHTED VERTEX COVER can be solved on bipartite graphs in time $O(m^{1+o(1)})$ [27], we obtain the following result concerning bipartite treewidth using Corollary 4.2.

**Corollary 4.3.** Given a graph $G$, a bipartite tree decomposition of $G$ of width $k$, and a weight function $w$, there is an algorithm that solves WEIGHTED VERTEX COVER/WEIGHTED INDEPENDENT SET on $(G, w)$ in time $O(2^k \cdot (k \cdot (k+n) + m^{1+o(1)}))$.

### 4.4.3. Odd Cycle Transversal

Let $\mathcal{H}$ be a graph. We define $f_{\text{oct}}$ as the 3-partition-evaluation function where, for every graph $G$ and for every $(S, X_1, X_2) \in \mathcal{P}_3(V(G))$,

$$f_{\text{oct}}(G, (S, X_1, X_2)) = \begin{cases} |S| & \text{if } G \setminus S \in \mathcal{B}, \text{ with bipartition } (X_1, X_2), \\ +\infty & \text{otherwise.} \end{cases}$$

Hence, seen as an optimization problem, ODD CYCLE TRANSVERSAL is the problem of computing $p_{f_{\text{oct}},\min}(G)$. We call its annotated extension ANNOTATED ODD CYCLE TRANSVERSAL. In other words, ANNOTATED ODD CYCLE TRANSVERSAL is defined as follows.

(WEIGHTED) ANNOTATED ODD CYCLE TRANSVERSAL

**Input:** A graph $G$, three disjoint sets $S, X_1, X_2 \subseteq V(G)$ (and a weight function $w: V(G) \to \mathbb{N}$).

**Objective:** Find, if it exists, a set $S^*$ of minimum size (resp. weight) such that $S \subseteq S^*$, $(X_1 \cup X_2) \cap S^* = \emptyset$, and $G \setminus S^*$ is bipartite with $X_1$ and $X_2$ on different sides of the bipartition.
We first prove that (WEIGHTED) ANNOTATED ODD CYCLE TRANSVERSAL has the gluing property.

**Lemma 4.9 (Gluing property).** (WEIGHTED) ANNOTATED ODD CYCLE TRANSVERSAL has the gluing property. More precisely, given two bounded graphs **F** = (F, B<sub>F</sub>, ρ<sub>F</sub>) and **G** = (G, B<sub>G</sub>, ρ<sub>G</sub>), a function w: V(**F** ⊕ **G**) → N, a set X ⊆ V(**F** ⊕ **G**) such that B<sub>F</sub> ∩ B<sub>G</sub> ⊆ X, and X = (S, X<sub>1</sub>, X<sub>2</sub>) ∈ P<sub>3</sub>(X), we have

$$ \hat{\mathbf{p}}_{\text{foct, min}}(\mathbf{F} \oplus \mathbf{G}, \mathcal{X}, w) = \hat{\mathbf{p}}_{\text{foct, min}}(F, \mathcal{X} \cap V(F), w) + \hat{\mathbf{p}}_{\text{foct, min}}(G, \mathcal{X} \cap V(G), w) - \bar{w}, $$

where $\bar{w} = w(S \cap B_F \cap B_G)$.

*Proof.* Let P = (S<sup>*</sup>, X<sub>1</sub><sup>*</sup>, X<sub>2</sub><sup>*</sup>) ∈ P<sub>3</sub>(V(**F** ⊕ **G**)) be such that X ⊆ P and $\hat{\mathbf{p}}_{\text{foct, min}}(\mathbf{F} \oplus \mathbf{G}, \mathcal{X}, w) = f_{\text{oct}}(\mathbf{F} \oplus \mathbf{G}, P, w)$. Then, for H ∈ {F, G}, H \ (S<sup>*</sup> ∩ V(H)) is bipartite, witnessed by the 2-partition (X<sub>1</sub><sup>*</sup> ∩ V(H), X<sub>2</sub><sup>*</sup> ∩ V(H)). Therefore,

$$ \begin{aligned} \hat{\mathbf{p}}_{\text{foct, min}}(\mathbf{F} \oplus \mathbf{G}, \mathcal{X}, w) &= w(S^*) \\ &= w(S^* \cap V(F)) + w(S^* \cap V(G)) - w(S^* \cap B_F \cap B_G) \\ &\geq \hat{\mathbf{p}}_{\text{foct, min}}(F, \mathcal{X} \cap V(F), w) + \hat{\mathbf{p}}_{\text{foct, min}}(G, \mathcal{X} \cap V(G), w) - \bar{w}. \end{aligned} $$

Reciprocally, let P<sub>H</sub> = (S<sub>H</sub>, X<sub>1</sub><sup>H</sup>, X<sub>2</sub><sup>H</sup>) ∈ P<sub>3</sub>(V(H)) be such that X ∩ V(H) ⊆ P<sub>H</sub> and $\hat{\mathbf{p}}_{\text{foct, min}}(H, X \cap V(H), w) = f_{\text{oct}}(H, P_H, w)$ for H ∈ {F, G}. Since P<sub>F</sub> ∩ B<sub>F</sub> ∩ B<sub>G</sub> = P<sub>G</sub> ∩ B<sub>F</sub> ∩ B<sub>G</sub>, it follows that $X_1^F \cup X_1^G$ and $X_2^F \cup X_2^G$ are two independent sets of ($\mathbf{F} \oplus \mathbf{G}$) \ ($S_F \cup S_G$). Therefore, ($\mathbf{F} \oplus \mathbf{G}$) \ ($S_F \cup S_G$) is a bipartite graph witnessed by ($X_1^F \cup X_1^G$, $X_2^F \cup X_2^G$). Thus,

$$ \begin{aligned} \hat{\mathbf{p}}_{\text{foct, min}}(\mathbf{F} \oplus \mathbf{G}, \mathcal{X}, w) &\leq w(S_F \cup S_G) \\ &= w(S_F) + w(S_G) - \bar{w} \\ &= \hat{\mathbf{p}}_{\text{foct, min}}(F, \mathcal{X} \cap V(F), w) + \hat{\mathbf{p}}_{\text{foct, min}}(G, \mathcal{X} \cap V(G), w) - \bar{w}. \end{aligned} $$

□

We now show how to reduce a graph **F** ⊕ **G** to a graph F' when the boundary of **F** and **G** has a single vertex v that is not annotated. See Figure 12 for an illustration. Similarly to Lemma 4.4, the proof of Lemma 4.10 only holds in the unweighted case.

<figure><img src="image_13.png" /><figcaption>Figure 12: Illustration of the gadgetization for ODD CYCLE TRANSVERSAL.</figcaption></figure>

**Lemma 4.10 (Gadgetization).** Let **F** = (F, B<sub>F</sub>, ρ<sub>F</sub>) and **G** = (G, B<sub>G</sub>, ρ<sub>G</sub>) be two bounded graphs. Let X ⊆ V(**F** ⊕ **G**) be such that B<sub>F</sub> ∩ B<sub>G</sub> ⊆ X. Let also v ∈ B<sub>F</sub> ∩ B<sub>G</sub>, let X = (S, X<sub>1</sub>, X<sub>2</sub>) ∈ P<sub>3</sub>(X \ {v})
with $X_1, X_2 \neq \emptyset$, and let $v_1 \in X_1$ and $v_2 \in X_2$. We set $\mathcal{X}_S = (S \cup \{v\}, X_1, X_2)$, $\mathcal{X}_1 = (S, X_1 \cup \{v\}, X_2)$, and $\mathcal{X}_2 = (S, X_1, X_2 \cup \{v\})$. We also set, for $a \in \{S, 1, 2\}$, $s_a = \hat{p}_{\text{foct,min}}(G, \mathcal{X}_a \cap V(G))$, and we set $\bar{s} = |S \cap B_F \cap B_G|$. For $i \in [2]$, we note $F_i$ the graph obtained from $F$ by adding the edge $vv_i$. Then we have the following case distinction.

$$ \hat{p}_{\text{foct,min}}(\mathbf{F} \oplus \mathbf{G}, \mathcal{X}) = \begin{cases} s_S + \hat{p}_{\text{foct,min}}(F, \mathcal{X}_S \cap V(F)) - \bar{s} - 1 & \text{if } s_S \le s_1, s_2, \\ s_1 + \hat{p}_{\text{foct,min}}(F, \mathcal{X} \cap V(F)) - \bar{s} & \text{if } s_1 = s_2 < s_S, \\ s_1 + \hat{p}_{\text{foct,min}}(F_2, \mathcal{X} \cap V(F)) - \bar{s} & \text{if } s_1 < s_S, s_2, \\ s_2 + \hat{p}_{\text{foct,min}}(F_1, \mathcal{X} \cap V(F)) - \bar{s} & \text{otherwise.} \end{cases} $$

*Proof.* For $H \in \{F, G\}$ and $a \in \{S, 1, 2\}$, let $\mathcal{P}_H^a = (S_H^a, X_{1,H}^a, X_{2,H}^a)$ be a partition of $V(H)$ such that $\mathcal{X}_a \cap V(H) \subseteq \mathcal{P}_H^a$ and $\hat{p}_{\text{foct,min}}(H, \mathcal{X}_a \cap V(H)) = f_{\text{oct}}(H, \mathcal{P}_H^a) = |S_H^a|$. We therefore have $s_a = |S_G^a|$. Let us similarly define $t_a = |S_F^a|$ for $a \in \{S, 1, 2\}$.

Note that $S_F^S \cap S_G^S = (S \cap B_F \cap B_G) \cup \{v\}$ and for $a \in \{1, 2\}$, $S_F^a \cap S_G^a = S \cap B_F \cap B_G$. Hence, using Lemma 4.2, we have that

$$ \hat{p}_{\text{foct,min}}(\mathbf{F} \oplus \mathbf{G}, \mathcal{X}) = \min\{\hat{p}_{\text{foct,min}}(\mathbf{F} \oplus \mathbf{G}, \mathcal{X}_a) \mid a \in \{S, 1, 2\}\} \\ = \min\{t_S + s_S - 1, t_1 + s_1, t_2 + s_2\} - \bar{s}. $$

Note that $s_S \le s_1 + 1$, since $G \setminus (S_G^1 \cup \{v\})$ is bipartite, witnessed by the 2-partition $(X_1 \setminus \{v\}, X_2)$, and thus $|S_G^1 \cup \{v\}| \ge \hat{p}_{\text{foct,min}}(G, \mathcal{X}_S \cap V(G))$. Similarly, $s_S \le s_2 + 1$, $t_S \le t_1 + 1$, and $t_S \le t_2 + 1$.

Hence, if $s_S \le s_1, s_2$, then $\min\{t_S + s_S - 1, t_1 + s_1, t_2 + s_2\} = t_S + s_S - 1$, so

$$ \hat{p}_{\text{foct,min}}(\mathbf{F} \oplus \mathbf{G}, \mathcal{X}) = s_S + t_S - \bar{s} - 1. $$

If $s_1 = s_2 < s_S$, then $s_1 = s_2 = s_S - 1$. Thus, $\min\{t_S + s_S - 1, t_1 + s_1, t_2 + s_2\} = \min\{t_S, t_1, t_2\} + s_1 = \hat{p}_{\text{foct,min}}(F, \mathcal{X} \cap V(F)) + s_1$, so

$$ \hat{p}_{\text{foct,min}}(\mathbf{F} \oplus \mathbf{G}, \mathcal{X}) = s_1 + \hat{p}_{\text{foct,min}}(F, \mathcal{X} \cap V(F)) - \bar{s}. $$

If $s_1 < s_S, s_2$, then $s_1 + 1 = s_S \le s_2$. We have $t_2 + s_2 \ge t_S + s_2 \ge t_S + s_S - 1$. Thus, $\min\{t_S + s_S - 1, t_1 + s_1, t_2 + s_2\} = \min\{t_S, t_1\} + s_1 = s_1 + \min\{\hat{p}_{\text{foct,min}}(F, \mathcal{X}_S \cap V(F)), \hat{p}_{\text{foct,min}}(F, \mathcal{X}_1 \cap V(F))\}$. Hence, we just need to ensure that $v$ cannot be added to $X_2$, which is done by adding an edge between $v$ and $v_2 \in X_2$. Therefore,

$$ \hat{p}_{\text{foct,min}}(\mathbf{F} \oplus \mathbf{G}, \mathcal{X}) = s_1 + \hat{p}_{\text{foct,min}}(F_2, \mathcal{X} \cap V(F)) - \bar{s}. $$

Otherwise, $s_2 < s_S, s_1$. By symmetry, we similarly obtain

$$ \hat{p}_{\text{foct,min}}(\mathbf{F} \oplus \mathbf{G}, \mathcal{X}) = s_2 + \hat{p}_{\text{foct,min}}(F_1, \mathcal{X} \cap V(F)) - \bar{s}. $$

□

Using Lemma 4.9 and Lemma 4.10, we can now prove that ANNOTATED ODD CYCLE TRANSVERSAL is $\mathcal{H}$-nice. Essentially, given an instance $(\mathbf{G} = \mathbf{X} \oplus (\oplus_{i \in [d]} \mathbf{G}_i), (A, B), \mathcal{A})$, we reduce $\mathbf{G}$ to $\mathbf{X}$ where we add two new vertices $u_1$ and $u_2$ in $\mathcal{A}$ and add edges between $u_i$ and some vertices in $B$, for $i \in [2]$, and show that the resulting bounded cycle graph is equivalent to $\mathbf{G}$ modulo some constant $s$.

**Lemma 4.11 (Nice problem).** Let $\mathcal{H}$ be a hereditary graph class. ANNOTATED ODD CYCLE TRANSVERSAL is $\mathcal{H}$-nice.

*Proof.* Let $\mathbf{G} = (G, X, \rho)$ be a bounded graph, let $\mathbf{X} = (G[X], X, \rho_X)$ be a trivial bounded graph and let $\{\mathbf{G}_i = (G_i, X_i, \rho_i) \mid i \in [d]\}$ be a collection of bounded graphs, such that $\mathbf{G} = \mathbf{X} \oplus (\oplus_{i \in [d]} \mathbf{G}_i)$, let $(A, B)$ be a partition of $X$ such that for all $i \in [d]$, $|X_i \setminus A| \le 1$, and let $\mathcal{A} = (S, X^1, X^2) \in \mathcal{P}_3(\mathcal{A})$. Suppose that we know, for every $i \in [d]$ and each $\mathcal{X}_i \in \mathcal{P}_3(X_i)$, the value $\hat{p}_{\text{foct,min}}(G_i, \mathcal{X}_i)$.
Let $\mathbf{G}'$ and $\mathbf{X}'$ be the bounded graphs obtained from $\mathbf{G}$ and $\mathbf{X}$ respectively, by adding two new isolated vertices $u_1$ and $u_2$ in the boundary (with unused labels). Let $\mathcal{A}' = (S, X^1 \cup \{u_1\}, X^2 \cup \{u_2\})$. This operation is done to ensure that $X'_i = X_i \cup \{u_i\}$ is non-empty for $i \in [2]$. Obviously, $\hat{\mathbf{p}}_{\text{foct,min}}(\mathbf{G} \oplus \mathbf{F}, \mathcal{A}) = \hat{\mathbf{p}}_{\text{foct,min}}(\mathbf{G}' \oplus \mathbf{F}, \mathcal{A}')$.

Let $v_1, \dots, v_{|B|}$ be the vertices of $B$. For $i \in [|B|]$, let $I_i = \{j \in [d] \mid X_j \setminus A = \{v_i\}\}$. Let $I_0 = \{j \in [d] \mid X_j \subseteq A\}$. Obviously, $(I_i)_{i \in [0, |B|]}$ is a partition of $[d]$.

Let us show that item (iii) holds. Let $(\mathbf{H}_{-1}, S_{-1}, s_{-1}, E_{-1}) = (\mathbf{G}', S, 0, \emptyset)$. For $i$ going from 0 up to $|B|$, we construct $(\mathbf{H}_i, S_{i-1}, s_i, E_i)$ from $(\mathbf{H}_{i-1}, S_i, s_{i-1}, E_{i-1})$ such that for any bounded graph $\mathbf{F}$ with underlying graph $\mathbf{F}$ and compatible with $\mathbf{G}$,

$$ \hat{\mathbf{p}}_{\text{foct,min}}(\mathbf{G} \oplus \mathbf{F}, \mathcal{A}) = \hat{\mathbf{p}}_{\text{foct,min}}(\mathbf{H}_i \oplus \mathbf{F}_i, \mathcal{A}_i) + s_i, $$

where $\mathbf{F}_i$ is the bounded graph obtained from $\mathbf{F}$ by adding the edges in $E_i$ and $\mathcal{A}_i = (S_i, X^1 \cup \{u_1\}, X^2 \cup \{u_2\})$. This is obviously true for $i = -1$.

Let $i \in [0, |B|]$. By induction, we have

$$ \hat{\mathbf{p}}_{\text{foct,min}}(\mathbf{G} \oplus \mathbf{F}, \mathcal{A}) = \hat{\mathbf{p}}_{\text{foct,min}}(\mathbf{H}_{i-1} \oplus \mathbf{F}_{i-1}, \mathcal{A}_{i-1}) + s_{i-1}. $$

Let $\mathbf{G}'_i = \mathbb{1}_{\{j \in I_i\}} \mathbf{G}_j$. Let $\mathbf{H}'_i$ be the bounded graph with underlying graph $\mathbf{H}'_i$ such that $\mathbf{H}_{i-1} = \mathbf{H}'_i \oplus \mathbf{G}'_i$.

Suppose first that $i = 0$. Let $\mathcal{P}_0 = (S^0, X_1^0, X_2^0) \in \mathcal{P}_3(X \cup \{u_1, u_2\})$ be such that $\mathcal{A}' \subseteq \mathcal{P}_0$ and $\hat{\mathbf{p}}_{\text{foct,min}}(\mathbf{G}' \oplus \mathbf{F}, \mathcal{A}') = \hat{\mathbf{p}}_{\text{foct,min}}(\mathbf{G}' \oplus \mathbf{F}, \mathcal{P}_0)$. According to Lemma 4.9,

$$ \begin{aligned} \hat{\mathbf{p}}_{\text{foct,min}}(\mathbf{G}' \oplus \mathbf{F}, \mathcal{P}_0) &= \hat{\mathbf{p}}_{\text{foct,min}}(\mathbf{F}, \mathcal{P}_0) + \hat{\mathbf{p}}_{\text{foct,min}}(\mathbf{G}', \mathcal{P}_0) - |S^0 \cap X| \\ &= \hat{\mathbf{p}}_{\text{foct,min}}(\mathbf{F}, \mathcal{P}_0) - |S^0 \cap X| + \hat{\mathbf{p}}_{\text{foct,min}}(\mathbf{H}'_0, \mathcal{P}_0) \\ &\quad + \sum_{j \in I_0} (\hat{\mathbf{p}}_{\text{foct,min}}(\mathbf{G}_j, \mathcal{P}_0 \cap X_j) - |S^0 \cap X_j|) \\ &= \hat{\mathbf{p}}_{\text{foct,min}}(\mathbf{H}'_0 \oplus \mathbf{F}, \mathcal{P}_0) + \sum_{j \in I_0} (\hat{\mathbf{p}}_{\text{foct,min}}(\mathbf{G}_j, \mathcal{P}_0 \cap X_j) - |S \cap X_j|), \end{aligned} $$

because $S^0 \setminus S \subseteq B$ and $X_j \cap B = \emptyset$.

Since this is the case for all such $\mathcal{P}_0$, it implies that

$$ \hat{\mathbf{p}}_{\text{foct,min}}(\mathbf{G}' \oplus \mathbf{F}, \mathcal{A}') = \hat{\mathbf{p}}_{\text{foct,min}}(\mathbf{H}'_0 \oplus \mathbf{F}, \mathcal{A}') + \sum_{j \in I_0} (\hat{\mathbf{p}}_{\text{foct,min}}(\mathbf{G}_j, \mathcal{P}_0 \cap X_j) - |S \cap X_j|). $$

Therefore, if $\mathbf{H}_0 = \mathbf{H}'_0$, $S_0 = S$, $s_0 = \sum_{j \in I_0} (\hat{\mathbf{p}}_{\text{foct,min}}(\mathbf{G}_j, \mathcal{P}_0 \cap X_j) - |S \cap X_j|)$, and $E_0 = \emptyset$, then

$$ \hat{\mathbf{p}}_{\text{foct,min}}(\mathbf{G} \oplus \mathbf{F}, \mathcal{A}) = \hat{\mathbf{p}}_{\text{foct,min}}(\mathbf{H}_0 \oplus \mathbf{F}_0, \mathcal{A}_0) + s_0. $$

Otherwise, $i \in [|B|]$ and $X_j \setminus A = \{v_i\}$ for each $j \in I_i$. Let $X_i^S = (S_{i-1} \cup \{v_i\}, X^1 \cup \{u_1\}, X^2 \cup \{u_2\})$, $X_i^1 = (S_{i-1}, X^1 \cup \{u_1, v_i\}, X^2 \cup \{u_2\})$, and $X_i^2 = (S_{i-1}, X^1 \cup \{u_1\}, X^2 \cup \{u_2, v_i\})$. For $a \in \{S, 1, 2\}$, let $s_i^a = \hat{\mathbf{p}}_{\text{foct,min}}(\mathbf{G}'_i, \mathcal{X}_i^a \cap X_i')$. By Lemma 4.9,

$$ s_i^S = \sum_{j \in I_i} (\hat{\mathbf{p}}_{\text{foct,min}}(\mathbf{G}_j, \mathcal{X}_i^S \cap X_j) - |S_{i-1} \cap X_j| - 1) + |S_{i-1} \cap X_i'| + 1 $$

and, for $a \in \{1, 2\}$,

$$ s_i^a = \sum_{j \in I_i} (\hat{\mathbf{p}}_{\text{foct,min}}(\mathbf{G}_j, \mathcal{X}_i^a \cap X_j) - |S_{i-1} \cap X_j|) + |S_{i-1} \cap X_i'|. $$

Therefore, $s_i^a$ can be computed for $a \in \{S, 1, 2\}$ in time $O(|A| \cdot |I_i|)$. For $a \in \{1, 2\}$, let $\mathbf{H}_i^a$ and $\mathbf{F}_i^a$ be the bounded graphs obtained from $\mathbf{H}'_i$ and $\mathbf{F}_{i-1}$, respectively, by adding the edge $v_i u_a$. Let $\mathcal{P}_i = (S^i, X_1^i, X_2^i) \in$
$\mathcal{P}_3(X \cup \{u_1, u_2\} \setminus \{v_i\})$ be such that $\mathcal{A}_{i-1} \subseteq \mathcal{P}_i$ and $\hat{\mathbf{p}}_{\text{foct,min}}(\mathbf{H}_{i-1} \oplus \mathbf{F}_{i-1}, \mathcal{A}_{i-1}) = \hat{\mathbf{p}}_{\text{foct,min}}(\mathbf{H}_{i-1} \oplus \mathbf{F}_{i-1}, \mathcal{P}_i)$. Let $\mathcal{P}_i^S = (S^i \cup \{v_i\}, X_1^i, X_2^i)$, $\mathcal{P}_i^1 = (S^i, X_1^i \cup \{v_i\}, X_2^i)$, and $\mathcal{P}_i^2 = (S^i, X_1^i, X_2^i \cup \{v_i\})$. Note that for $a \in \{S, 1, 2\}$, we have $s_i^a = \hat{\mathbf{p}}_{\text{foct,min}}(G'_i, \mathcal{P}_i^a \cap X'_i)$. Then, using Lemma 4.10,

$$ \begin{aligned} \hat{\mathbf{p}}_{\text{foct,min}}(\mathbf{H}_{i-1} \oplus \mathbf{F}_{i-1}, \mathcal{P}_i) &= \hat{\mathbf{p}}_{\text{foct,min}}((\mathbf{H}'_i \boxplus \mathbf{F}_{i-1}) \oplus \mathbf{G}'_i, \mathcal{P}_i) \\ &= \begin{cases} s_S + \hat{\mathbf{p}}_{\text{foct,min}}(\mathbf{H}'_i \oplus \mathbf{F}_{i-1}, \mathcal{P}_i^S) - \bar{s} - 1 & \text{if } s_i^S \le s_i^1, s_i^2, \\ s_1 + \hat{\mathbf{p}}_{\text{foct,min}}(\mathbf{H}'_i \oplus \mathbf{F}_{i-1}, \mathcal{P}_i) - \bar{s} & \text{if } s_i^1 = s_i^2 < s_i^S, \\ s_1 + \hat{\mathbf{p}}_{\text{foct,min}}(\mathbf{H}_i^2 \oplus \mathbf{F}_i^2, \mathcal{P}_i) - \bar{s} & \text{if } s_i^1 < s_i^S, s_i^2, \text{ and} \\ s_2 + \hat{\mathbf{p}}_{\text{foct,min}}(\mathbf{H}_i^1 \oplus \mathbf{F}_i^1, \mathcal{P}_i) - \bar{s} & \text{otherwise.} \end{cases} \end{aligned} $$

Since this is the case for any such $\mathcal{P}_i$, we have that

$$ \begin{aligned} \hat{\mathbf{p}}_{\text{foct,min}}(\mathbf{G} \oplus \mathbf{F}, \mathcal{A}) &= \hat{\mathbf{p}}_{\text{foct,min}}(\mathbf{H}_{i-1} \oplus \mathbf{F}_{i-1}, \mathcal{A}_{i-1}) + s_{i-1} \\ &= \hat{\mathbf{p}}_{\text{foct,min}}(\mathbf{H}_i \oplus \mathbf{F}_i, \mathcal{A}_i) + s_i, \end{aligned} $$

where

$$ (\mathbf{H}_i, S_i, s_i, E_i) = \begin{cases} (\mathbf{H}'_i, S_{i-1} \cup \{v\}, s_{i-1} + s_S - \bar{s} - 1, E_{i-1}) & \text{if } s_i^S \le s_i^1, s_i^2, \\ (\mathbf{H}'_i, S_{i-1}, s_{i-1} + s_1 - \bar{s}, E_{i-1}) & \text{if } s_i^1 = s_i^2 < s_i^S, \\ (\mathbf{H}_i^2, S_{i-1}, s_{i-1} + s_1 - \bar{s}, E_{i-1} \cup \{v_i u_2\}) & \text{if } s_i^1 < s_i^S, s_i^2, \\ (\mathbf{H}_i^1, S_{i-1}, s_{i-1} + s_2 - \bar{s}, E_{i-1} \cup \{v_i u_1\}) & \text{otherwise.} \end{cases} $$

Let $S_B = S_{|B|} \setminus S \subseteq B$. Let $\mathbf{H}_B = \mathbf{H}_{|B|} \setminus S_B$. We have $(\mathbf{H}_{|B|} \oplus \mathbf{F}_{|B|}) \setminus S_B = (\mathbf{H}_{|B|} \oplus \mathbf{F}) \setminus S_B = (\mathbf{H}_{|B|} \setminus S_B) \triangleright \mathbf{F} = \mathbf{H}_B \triangleright \mathbf{F}$. Observe that

$$ \begin{aligned} \hat{\mathbf{p}}_{\text{foct,min}}(\mathbf{H}_{|B|} \oplus \mathbf{F}_{|B|}, \mathcal{A}_{|B|}) &= \hat{\mathbf{p}}_{\text{foct,min}}((\mathbf{H}_{|B|} \oplus \mathbf{F}_{|B|}) \setminus S_B, \mathcal{A}_{|B|} \setminus S_B) + |S_B| \\ &= \hat{\mathbf{p}}_{\text{foct,min}}(\mathbf{H}_B \triangleright \mathbf{F}, \mathcal{A}') + |S_B|. \end{aligned} $$

Hence,

$$ \hat{\mathbf{p}}_{\text{foct,min}}(\mathbf{G} \oplus \mathbf{F}, \mathcal{A}) = \hat{\mathbf{p}}_{\text{foct,min}}(\mathbf{H}_B \triangleright \mathbf{F}, \mathcal{A}') + |S_B| + s_{|B|}, $$

so item (iii) holds.

Observe that $\mathbf{H}_B$ is isomorphic to the bounded graph obtained from $\mathbf{X}$ by adding two new vertices and the at most $|B|$ edges in $E_{|B|}$, and removing the vertices in $S_B$. Hence, $|V(H_B)| \le |X| + 2$ and $|E(H_B)| \le |E(G[X])| + |B|$, so item (ii) holds. Moreover, $|\cup \mathcal{A}'| = |\cup \mathcal{A}| + 2$, so item (i) holds. Suppose that $F \setminus A \in \mathcal{H}$. Observe that, since the edges in $E_{|B|}$ all have one endpoint in $\{u_1, u_2\}$, $(\mathbf{H}_B \triangleright \mathbf{F}) \setminus (\cup \mathcal{A}) \setminus \{u_1, u_2\}$ is isomorphic to $(F \setminus A) \setminus S_B$. Since $\mathcal{H}$ is hereditary, $(\mathbf{H}_B \triangleright \mathbf{F}) \setminus (\cup \mathcal{A}') \in \mathcal{H}$, and thus, item (iv) holds. Thus, $(\mathbf{H}_B, \mathcal{A}', |S_B| + s_{|B|})$ is an $\mathcal{H}$-nice reduction of $(G, \mathcal{A})$ with respect to ANNOTATED ODD CYCLE TRANSVERSAL.

At each step $i$, $(H_i, S_i, s_i, E_i)$ is computable in time $O(|A| \cdot |I_i|)$, so the computation takes time $O(|A| \cdot d)$. Hence, ANNOTATED ODD CYCLE TRANSVERSAL is $\mathcal{H}$-nice. $\square$

In the next lemma, we adapt the seminal proof of Reed, Smith and Vetta [11] that uses iterative compression to solve ANNOTATED ODD CYCLE TRANSVERSAL in FPT-time parameterized by oct.

Given a graph $G$ and two sets $A, B \subseteq V(G)$, an $(A, B)$-cut is a set $X \subseteq V(G)$ such that there are no paths from a vertex in $A$ to a vertex in $B$ in $V(G) \setminus X$.

**Lemma 4.12.** There is an algorithm that, given a graph $G$, $(a$ weight function $w: V(G) \to \mathbb{N},)$ and three disjoint sets $S, A, B \subseteq V(G)$, such that $G \setminus (S \cup A \cup B)$ is bipartite, solves ANNOTATED ODD CYCLE TRANSVERSAL (resp. WEIGHTED ANNOTATED ODD CYCLE TRANSVERSAL) on $(G, S, A, B)$ in time $O((m+k^2)^{1+o(1)})$, where $k = |A \cup B|$.
*Proof.* We can assume that $S = \emptyset$, given that $S^*$ is an optimal solution for $(G, S, A, B)$ if and only if $S^* \setminus S$ is an optimal solution for $(G \setminus S, \emptyset, A, B)$.

Let $G^+$ be the graph obtained from $G$ by joining each $a \in A$ with each $b \in B$. Let $X = A \cup B$. Let $(S_1, S_2)$ be a partition witnessing the bipartiteness of $G \setminus X = G^+ \setminus X$. We construct an auxiliary bipartite graph $G'$ from $G^+$ as follows. The vertex set of the auxiliary graph is $V' = V(G) \setminus X \cup \{x_1, x_2 \mid x \in X\}$. We maintain a one-to-one correspondence between the edges of $G^+$ and the edges of $G'$ by the following scheme (and with the same weight):

* for each edge $e$ of $G^+ \setminus X$, there is a corresponding edge in $G'$ with the same endpoints,

* for each edge $e \in E(G^+)$ joining a vertex $y \in S_i$ to a vertex $x \in X$, the corresponding edge in $G'$ joins $y$ to $x_{3-i}$, and

* for each edge $e \in E(G^+)$ joining two vertices $a \in A$ and $b \in B$, the corresponding edge of $G'$ joins $a_1$ to $b_2$.

For $i \in \{1, 2\}$, let $X_i = \{x_i \mid x \in X\}$, $A_i = \{a_i \mid a \in A\}$, $B_i = \{b_i \mid b \in B\}$. Note that $G'$ is a bipartite graph, witnessed by the partition $(S_1 \cup X_1, S_2 \cup X_2)$. Let $Y_1 = A_1 \cup B_2$ and $Y_2 = A_2 \cup B_1$. Note also that there is no edge joining $Y_1$ and $Y_2$, so there exists a $(Y_1, Y_2)$-cut in $G'$ that is actually contained in $V(G^+) \setminus X$, and hence in $V(G) \setminus X$. Let us show that $S^* \subseteq V(G) \setminus X$ is a $(Y_1, Y_2)$-cut in $G'$ if and only if $S^*$ is an odd cycle transversal of $G$ with $A$ on one side of the bipartition and $B$ on the other one.

**Claim 4.1** If $S^* \subseteq V(G) \setminus X$ is a cutset separating $Y_1$ from $Y_2$ in $G'$, then $S^*$ is an odd cycle transversal of $G$ with $A$ on one side of the bipartition and $B$ on the other one.

*Proof of claim.* Let $C$ be an odd cycle of $G^+$. Suppose toward a contradiction that $C \cap S^* = \emptyset$. $G^+ \setminus X$ is bipartite, so $C$ intersects $X$. Moreover, we assumed $G^+[X]$ to be bipartite since $A$ and $B$ are two disjoint independent sets, so $C$ intersects $V(G^+) \setminus X$. Hence, if we divide $C$ into paths whose endpoints are in $X$ and whose internal vertices are in $V(G^+) \setminus X$, each such path in $G'$ has either both endpoints in $Y_1$ or both endpoints in $Y_2$, since it is not intersected by the cutset $S^*$. More specifically, each such path in $G'$ has either both endpoints in $A_i$, or both endpoints in $B_i$, or one in $A_i$ and one in $B_{3-i}$, for $i \in \{1, 2\}$. A path with both endpoints in $A_i$ or $B_i$ is even, since the internal vertices are alternatively vertices of $S_i$ and $S_{3-i}$, with the first and the last in $S_{3-i}$. A path with one endpoint in $A_i$ and one in $B_{3-i}$ is odd by a similar reasoning, but the number of such paths must be even in order to have a cycle. Therefore, the cycle $C$ is even. Hence the contradiction. So $S^*$ is an odd cycle transversal of $G^+$. Given that we added in $G^+$ all edges between $A$ and $B$ and that $A, B \subseteq V(G^+) \setminus S^*$, $A$ and $B$ belong to different sides of the bipartition. An odd cycle of $G$ is also an odd cycle of $G^+$, so $S^*$ is also an odd cycle transversal of $G$, with $A$ and $B$ on different sides of the bipartition.
$\diamond$

**Claim 4.2.** If $S^* \subseteq V(G) \setminus X$ is an odd cycle transversal of $G$ with $A$ and $B$ on different sides of the bipartition, then $S^*$ is a cutset separating $Y_1$ from $Y_2$ in $G'$.

*Proof of claim.* Suppose toward a contradiction that there is a path $P$ between $Y_1$ and $Y_2$ that does not intersect $S^*$. Choose $P$ of minimum length. Hence, the internal vertices of $P$ belong to $G \setminus X$. The endpoints $u$ and $v$ of $P$ are such that, either $u \in A_i$ and $v \in A_{3-i}$, or $u \in B_i$ and $v \in B_{3-i}$, or $u \in A_i$ and $v \in B_i$, or $u \in B_i$ and $v \in A_i$, for $i \in \{1, 2\}$. By symmetry, we can assume without loss of generality that $u \in A_1$ and $v \in A_2$ or $v \in B_1$. If $v \in A_2$, then $P$ is an odd path since $G \setminus X$ is bipartite. However, since $G \setminus S^*$ is bipartite, with $A$ on one side of the bipartition, $P$ is an even path. If $v \in B_1$, then $P$ is an even path since $G \setminus X$ is bipartite. However, since $G \setminus S^*$ is bipartite, with $A$ and $B$ on different sides of the bipartition, $P$ is an odd path. Hence the contradiction.
$\diamond$

The graph $G'$ has $n' = n + |X|$ vertices and at most $m' = m + |X|^2/4$ edges. Finding a minimum (weighted) vertex-cut can be reduced to the problem of finding a minimum (weighted) edge-cut. To do so, we transform $G'$ into an arc-weighted directed graph $G''$, by first replacing every edge by two parallel arcs in opposite directions, and then replacing every vertex $v$ of $G'$ by an arc ($v_{in}, v_{out}$), such that the arcs incoming
(resp. outgoing) to $v$ are now incoming to $v_{in}$ (resp. outgoing of $v_{out}$). We give weight $w(v)$ to $(v_{in}, v_{out})$, and weight $w(V(G))+1$ to the other arcs. Then, computing a minimum (weighted) vertex-cut in $G'$ is equivalent to computing a minimum (weighted) edge-cut in $G''$, which can be done in time $O((m')^{1+o(1)})$ [27]. Hence, the running time of the algorithm is $O((m + |X|^2)^{1+o(1)})$. □

We apply Lemma 4.11 and Lemma 4.12 to the dynamic programming algorithm of Lemma 4.1 to obtain the following result.

**Corollary 4.4.** *Given a graph $G$ and a bipartite tree decomposition of $G$ of width $k$, there is an algorithm that solves ODD CYCLE TRANSVERSAL on $G$ in time $O(3^k \cdot (m + k^2 \cdot n)^{1+o(1)})$.*

### 4.4.4. Maximum Weighted Cut

The MAXIMUM WEIGHTED CUT problem is defined as follows.

**MAXIMUM WEIGHTED CUT**

**Input:** A graph $G$ and a weight function $w: E(G) \to \mathbb{N}$.

**Objective:** Find an edge cut of maximum weight.

Let $H$ be a graph. We define $f_{cut}$ as the 2-partition-evaluation function where, for every graph $G$ with edge weight $w$ and for every $\mathcal{P} = (X_1, X_2) \in \mathcal{P}_2(V(G))$,

$$f_{cut}(G, \mathcal{P}) = w(\mathcal{P}) = w(E(X_1, X_2)).$$

Hence, MAXIMUM WEIGHTED CUT is the problem of computing $p_{f_{cut},max}(G)$. We call its annotated extension ANNOTATED MAXIMUM WEIGHTED CUT. In other words, ANNOTATED MAXIMUM WEIGHTED CUT is defined as follows.

**ANNOTATED MAXIMUM WEIGHTED CUT**

**Input:** A graph $G$, a weight function $w: E(G) \to \mathbb{N}$, and two disjoint sets $X_1, X_2 \subseteq V(G)$.

**Objective:** Find an edge cut of maximum weight such that the vertices in $X_1$ belongs to one side of the cut, and the vertices in $X_2$ belong to the other side.

For simplicity, given a set $X \subseteq V(G)$ and $\mathcal{X} = (A, B) \in \mathcal{P}_2(X)$, we write $w(\mathcal{X})$, to denote the sum of the weights of the edges with one endpoint in $A$ and the other in $B$.

We first prove that ANNOTATED MAXIMUM WEIGHTED CUT has the gluing property.

**Lemma 4.13 (Gluing property).** ANNOTATED MAXIMUM WEIGHTED CUT has the gluing property. More precisely, given two bounded graphs $\mathbf{F} = (F, B_F, \rho_F)$ and $\mathbf{G} = (G, B_G, \rho_G)$, a weight function $w: E(\mathbf{F} \oplus \mathbf{G}) \to \mathbb{N}$, a set $X \subseteq V(\mathbf{F} \oplus \mathbf{G})$ such that $B_F \cap B_G \subseteq X$, and $\mathcal{X} = (X_1, X_2) \in \mathcal{P}_2(X)$, if we set $\bar{w} = w(\mathcal{X} \cap B_F \cap B_G)$, then we have

$$\hat{p}_{f_{cut},max}(\mathbf{F} \oplus \mathbf{G}, \mathcal{X}, w) = \hat{p}_{f_{cut},max}(F, \mathcal{X} \cap V(F), w) + \hat{p}_{f_{cut},max}(G, \mathcal{X} \cap V(G), w) - \bar{w}.$$

*Proof.* Let $\mathcal{P} \in \mathcal{P}_2(V(\mathbf{F} \oplus \mathbf{G}))$ be such that $\mathcal{X} \subseteq \mathcal{P}$ and $\hat{p}_{f_{cut},max}(\mathbf{F} \oplus \mathbf{G}, \mathcal{X}, w) = f_{cut}(\mathbf{F} \oplus \mathbf{G}, \mathcal{P}, w)$. Then,

$$\begin{align*}
\hat{p}_{f_{cut},max}(\mathbf{F} \oplus \mathbf{G}, \mathcal{X}, w) &= w(\mathcal{P}) \\
&= w(\mathcal{P} \cap V(F)) + w(\mathcal{P} \cap V(G)) - \bar{w} \\
&\leq \hat{p}_{f_{cut},max}(F, \mathcal{X} \cap V(F), w) + \hat{p}_{f_{cut},max}(G, \mathcal{X} \cap V(G), w) - \bar{w}.
\end{align*}$$
Reciprocally, for $H \in \{F, G\}$, let $\mathcal{P}_H = (X_1^H, X_2^H) \in \mathcal{P}_2(V(H))$ be such that $\mathcal{X} \cap V(H) \subseteq \mathcal{P}_H$ and $\hat{\mathbf{p}}_{\text{cut,max}}(H, \mathcal{X} \cap V(H), w) = f_{\text{oct}}(H, \mathcal{P}_H, w)$. Then, since $\mathcal{P}_H \cap B_F \cap B_G = \mathcal{X} \cap B_F \cap B_G$ for $H \in \{F, G\}$, we have

$$ \begin{aligned} \hat{\mathbf{p}}_{\text{cut,max}}(\mathbf{F} \oplus \mathbf{G}, \mathcal{X}, w) &\geq w(E(X_1^F \cup X_1^G, X_2^F \cup X_2^G)) \\ &= w(E(X_1^F, X_2^F)) + w(E(X_1^G, X_2^G)) - \bar{w} \\ &= \hat{\mathbf{p}}_{\text{cut,max}}(F, \mathcal{X} \cap V(F), w) + \hat{\mathbf{p}}_{\text{cut,max}}(G, \mathcal{X} \cap V(G), w) - \bar{w}. \end{aligned} $$

□

We now show how to reduce a graph $\mathbf{F} \oplus \mathbf{G}$ to a graph $F'$ when the boundary of $\mathbf{F}$ and $\mathbf{G}$ has a single vertex $v$ that is not annotated. See Figure 13 for an illustration.

<figure><img src="image_14.png" /><figcaption>Figure 13: Illustration of the gadgetization for WEIGHTED MAX CUT.</figcaption></figure>

**Lemma 4.14 (Gadgetization).** Let $\mathbf{F} = (F, B_F, \rho_F)$ and $\mathbf{G} = (G, B_G, \rho_G)$ be two bounded graphs. Let $w: E(\mathbf{F} \oplus \mathbf{G}) \to \mathbb{N}$ be a weight function and let $X \subseteq V(\mathbf{F} \oplus \mathbf{G})$ be such that $B_F \cap B_G \subseteq X$. Let also $v \in B_F \cap B_G$ and let $\mathcal{X} = (X_1, X_2) \in \mathcal{P}_2(X \setminus \{v\})$. Suppose that there is $v_1 \in X_1 \cap B_F \cap B_G$ and $v_2 \in X_2 \cap B_F \cap B_G$ adjacent to $v$ with $w(vv_1) = w(vv_2) = 0$. We set $\mathcal{X}^1 = (X_1 \cup \{v\}, X_2)$ and $\mathcal{X}^2 = (X_1, X_2 \cup \{v\})$. We also set, for $a \in [2]$, $g_a = \hat{\mathbf{p}}_{\text{cut,max}}(G, \mathcal{X}^a \cap V(G), w)$, we set $\bar{w} = w(\mathcal{X} \cap B_F \cap B_G)$, and we set $w'(F) \to \mathbb{N}$ such that $w'(vv_1) = g_2 - \bar{w}, w'(vv_2) = g_1 - \bar{w}$, and $w'(e) = w(e)$ otherwise. Then

$$ \hat{\mathbf{p}}_{\text{cut,max}}(\mathbf{F} \oplus \mathbf{G}, \mathcal{X}, w) = \hat{\mathbf{p}}_{\text{cut,max}}(F, \mathcal{X}, w'). $$

*Proof.* For $a \in [2]$, let $f_a = \hat{\mathbf{p}}_{\text{cut,max}}(F, \mathcal{X}^a \cap V(F), w)$. Note that in $F$ with partition $\mathcal{X}$, if $v$ is on the same side as $X_1$, then we must count the weight of the edge $vv_2$, but not the weight of $vv_1$, and vice versa when exchanging 1 and 2. Thus, using Lemma 4.13, we have

$$ \begin{aligned} \hat{\mathbf{p}}_{\text{cut,max}}(\mathbf{F} \oplus \mathbf{G}, \mathcal{X}, w) &= \max\{\hat{\mathbf{p}}_{\text{cut,max}}(\mathbf{F} \oplus \mathbf{G}, \mathcal{X}^1, w), \hat{\mathbf{p}}_{\text{cut,max}}(\mathbf{F} \oplus \mathbf{G}, \mathcal{X}^2, w)\} \\ &= \max\{f_1 + g_1 - \bar{w}, f_2 + g_2 - \bar{w}\} \\ &= \max\{f_1 + w'(vv_2), f_2 + w'(vv_1)\} \\ &= \max\{\hat{\mathbf{p}}_{\text{cut,max}}(F, \mathcal{X}^1, w'), \hat{\mathbf{p}}_{\text{cut,max}}(F, \mathcal{X}^2, w')\} \\ &= \hat{\mathbf{p}}_{\text{cut,max}}(F, \mathcal{X}, w'). \end{aligned} $$

□

Using Lemma 4.13 and Lemma 4.14, we prove that ANNOTATED MAXIMUM WEIGHTED CUT is $\mathcal{H}$-nice. Essentially, given an instance $(\mathbf{G} = \mathbf{X} \oplus (\oplus_{i \in [d]} \mathbf{G}_i), (A, B), \mathcal{A}, w)$, we reduce $\mathbf{G}$ to $\mathbf{X}$ where we add two new vertices in $\mathcal{A}$ and add all edges between these new vertices and the vertices in $B$. We then show that if the appropriate weight is given to each new edge, then the resulting bounded graph is an equivalent instance to $\mathbf{G}$ modulo some constant $s$.

**Lemma 4.15 (Nice problem).** Let $\mathcal{H}$ be a graph class. ANNOTATED MAXIMUM WEIGHTED CUT is $\mathcal{H}$-nice.
Proof. Let $\mathbf{G} = (G, X, \rho)$ be a bounded graph, let $w: E(G) \to \mathbb{N}$ be a weight function, let $\mathbf{X} = (G[X], X, \rho_X)$ be a trivial bounded graph and let $\{\mathbf{G}_i = (G_i, X_i, \rho_i) \mid i \in [d]\}$ be a collection of bounded graphs, such that $\mathbf{G} = \mathbf{X} \oplus (\oplus_{i \in [d]} \mathbf{G}_i)$, let $(A, B)$ be a partition of $X$ such that for all $i \in [d]$, $|X_i \setminus A| \le 1$, and let $\mathcal{A} = (X^1, X^2) \in \mathcal{P}_2(A)$. Suppose that we know, for every $i \in [d]$ and each $\mathcal{X}_i \in \mathcal{P}_3(X_i)$, the value $\hat{\rho}_{f_{\text{cut},\max}}(G_i, \mathcal{X}_i, w)$.

Let $\bar{\mathbf{G}}, \bar{\mathbf{X}}$, and $\bar{\mathbf{G}}_i$ be the bounded graphs obtained from $\mathbf{G}, \mathbf{X}$, and $\mathbf{G}_i$, respectively, by adding two new vertices $u_1$ and $u_2$ in the boundary (with unused labels) and making them adjacent to every vertex in $B$. We extend $w$ to $E(G')$ such that any edge adjacent to $u_1$ or $u_2$ has weight zero. Let $\mathcal{A}' = (X^1 \cup \{u_1\}, X^2 \cup \{u_2\})$. This operation is done to ensure that $X'_i = X^i \cup \{u_i\}$ is non-empty for $i \in [2]$. For any bounded graph $\mathbf{F}$ compatible with $G$, let $\bar{\mathbf{F}}$ be the bounded graph obtained similarly to $\bar{\mathbf{G}}$. Obviously, $\hat{\rho}_{f_{\text{cut},\max}}(\mathbf{G} \oplus \mathbf{F}, \mathcal{A}, w) = \hat{\rho}_{f_{\text{cut},\max}}(\bar{\mathbf{G}} \oplus \bar{\mathbf{F}}, \mathcal{A}', w) = \hat{\rho}_{f_{\text{cut},\max}}(\bar{\mathbf{G}} \triangleright \mathbf{F}, \mathcal{A}', w)$.

Let $v_1, \dots, v_{|B|}$ be the vertices of $B$. For $i \in [|B|]$, let $I_i = \{j \in [d] \mid X_j \setminus A = \{v_i\}\}$. Let $I_0 = \{j \in [d] \mid X_j \subseteq A\}$. Obviously, $(I_i)_{i \in [0,|B|]}$ is a partition of $[d]$.

Let us show that item (iii) holds. Let $(\mathbf{H}_{-1}, s_{-1}, w_{-1}) = (\bar{\mathbf{G}}, 0, w)$. For $i$ going from 0 up to $|B|$, we will construct $(\mathbf{H}_i, s_i, w_i)$ from $(\mathbf{H}_{i-1}, s_{i-1}, w_{i-1})$ such that $w_i$ and $w_{i-1}$ may only differ on $v_i u_1$ and $v_i u_2$ and such that for any bounded graph $\mathbf{F}$ compatible with $\mathbf{G}$ and with underlying graph $\mathbf{F}$,

$$ \hat{\rho}_{f_{\text{cut},\max}}(\mathbf{G} \oplus \mathbf{F}, \mathcal{A}) = \hat{\rho}_{f_{\text{cut},\max}}(\mathbf{H}_i \oplus \bar{\mathbf{F}}, \mathcal{A}', w_i) + s_i. $$

This is obviously true for $i = -1$.

Let $i \in [0, |B|]$. Let $\mathbf{G}'_i = \oplus_{j \in I_i} \bar{\mathbf{G}}_j$. Let $\mathbf{H}_i$ be the bounded graph such that $\mathbf{H}_{i-1} = \mathbf{H}_i \oplus \mathbf{G}_i$. By induction, we have

$$ \hat{\rho}_{f_{\text{cut},\max}}(\mathbf{G} \oplus \mathbf{F}, \mathcal{A}, w) = \hat{\rho}_{f_{\text{cut},\max}}(\mathbf{H}_{i-1} \oplus \bar{\mathbf{F}}, \mathcal{A}', w_{i-1}) + s_{i-1}. $$

Suppose first that $i = 0$. Let $\mathcal{P}_0 = (X_1^0, X_2^0) \in \mathcal{P}_2(X \cup \{u_1, u_2\})$ be such that $\mathcal{A}' \subseteq \mathcal{P}_0$ and $\hat{\rho}_{f_{\text{cut},\max}}(\bar{\mathbf{G}} \oplus \bar{\mathbf{F}}, \mathcal{A}', w) = \hat{\rho}_{f_{\text{cut},\max}}(\bar{\mathbf{G}} \oplus \bar{\mathbf{F}}, \mathcal{P}_0, w)$. According to Lemma 4.13,

$$ \begin{aligned} \hat{\rho}_{f_{\text{cut},\max}}(\bar{\mathbf{G}} \oplus \bar{\mathbf{F}}, \mathcal{P}_0, w) &= \hat{\rho}_{f_{\text{cut},\max}}(\bar{\mathbf{F}}, \mathcal{P}_0, w) + \hat{\rho}_{f_{\text{cut},\max}}(\bar{\mathbf{G}}, \mathcal{P}_0, w) - w(E(\mathcal{P}_0 \cap X)) \\ &= \hat{\rho}_{f_{\text{cut},\max}}(\bar{\mathbf{F}}, \mathcal{P}_0, w) - w(E(\mathcal{P}_0 \cap X)) + \hat{\rho}_{f_{\text{cut},\max}}(\mathcal{H}_0, \mathcal{P}_0, w) \\ &\quad + \sum_{j \in I_0} (\hat{\rho}_{f_{\text{cut},\max}}(G_j, \mathcal{P}_0 \cap X_j, w) - w(\mathcal{P}_0 \cap X_j)) \\ &= \hat{\rho}_{f_{\text{cut},\max}}(\mathbf{H}_0 \oplus \bar{\mathbf{F}}, \mathcal{P}_0, w) + \sum_{j \in I_i} (\hat{\rho}_{f_{\text{cut},\max}}(G_j, \mathcal{A} \cap X_j, w) - w(\mathcal{A} \cap X_j)). \end{aligned} $$

Since this is the case for all such $\mathcal{P}_0$, it implies that

$$ \hat{\rho}_{f_{\text{cut},\max}}(\bar{\mathbf{G}} \oplus \bar{\mathbf{F}}, \mathcal{A}', w) = \hat{\rho}_{f_{\text{cut},\max}}(\mathbf{H}_0 \oplus \bar{\mathbf{F}}, \mathcal{A}', w) + \sum_{j \in I_i} (\hat{\rho}_{f_{\text{cut},\max}}(G_j, \mathcal{A} \cap X_j, w) - w(\mathcal{A} \cap X_j)). $$

Therefore, if $w_0 = w$ and $s_0 = s_{-1} + \sum_{j \in I_i} (\hat{\rho}_{f_{\text{cut},\max}}(G_j, \mathcal{A} \cap X_j, w) - w(\mathcal{A} \cap X_j))$, then

$$ \hat{\rho}_{f_{\text{cut},\max}}(\mathbf{G} \oplus \mathbf{F}, \mathcal{A}, w) = \hat{\rho}_{f_{\text{cut},\max}}(\mathbf{H}_0 \oplus \bar{\mathbf{F}}, \mathcal{A}, w_0) + s_0. $$

Otherwise, $i \in [|B|]$ and $X_j \setminus A = \{v_i\}$ for each $j \in I_i$. Let $X'_i = \bigcup_{j \in I_i} X_j$. Let $\mathcal{X}_i^1 = (X^1, X^2 \cup \{v_i\})$ and $\mathcal{X}_i^2 = (X^1 \cup \{v_i\}, X^2)$. Let $g_i^1 = \hat{\rho}_{f_{\text{cut},\max}}(G'_i, \mathcal{X}_i^1 \cap X'_i, w)$ and $g_i^2 = \hat{\rho}_{f_{\text{cut},\max}}(G'_i, \mathcal{X}_i^2 \cap X'_i, w)$. For $a \in [2]$, $g_i^a$ can be computed in time $O(|A| \cdot |I_i|)$ since, by Lemma 4.13,

$$ \begin{aligned} g_i^a &= \hat{\rho}_{f_{\text{cut},\max}}(\oplus_{j \in I_i} \bar{\mathbf{G}}_j, \mathcal{X}_i^a \cap X'_i, w) \\ &= \sum_{j \in I_i} (\hat{\rho}_{f_{\text{cut},\max}}(\bar{\mathbf{G}}_j, \mathcal{X}_i^a \cap X'_i \cap V(\bar{\mathbf{G}}_j)) - w(\mathcal{X}_i^a \cap X'_i \cap V(\bar{\mathbf{G}}_j))) + w(\mathcal{X}_i^a \cap X'_i) \\ &= \sum_{j \in I_i} (\hat{\rho}_{f_{\text{cut},\max}}(G_j, \mathcal{X}_i^a \cap X_j, w) - w(\mathcal{X}_i^a \cap X_j)) + w(\mathcal{X}_i^a \cap X'_i). \end{aligned} $$
Let $w_i : E(\mathbf{H}_i \oplus \bar{\mathbf{F}}) \to \mathbb{N}$ be such that $w_i(v_i u_1) = g_i^2 - w(\mathcal{X}_i^a \cap X_i')$, $w_i(v_i u_2) = g_i^1 - w(\mathcal{X}_i^a \cap X_i')$, and $w_i(e) = w_{i-1}(e)$ otherwise. Let $\mathcal{P}_i = (R^i, S^i) \subseteq \mathcal{P}_2(X \cup \{u_1, u_2\} \setminus \{v_i\})$ be such that $\mathcal{A}' \subseteq \mathcal{P}_i$ and $\hat{\mathbf{p}}_{\text{cut,max}}(\mathbf{H}_{i-1} \oplus \bar{\mathbf{F}}, \mathcal{A}, w_{i-1}) = \hat{\mathbf{p}}_{\text{cut,max}}(\mathbf{H}_{i-1} \oplus \bar{\mathbf{F}}, \mathcal{P}_i, w_{i-1})$. Then, using Lemma 4.14,

$$ \hat{\mathbf{p}}_{\text{cut,max}}(\mathbf{H}_{i-1} \oplus \bar{\mathbf{F}}, \mathcal{P}_i, w_{i-1}) = \hat{\mathbf{p}}_{\text{cut,max}}((\mathbf{H}_i \boxplus \bar{\mathbf{F}}) \oplus \mathbf{G}_i', \mathcal{P}_i, w_{i-1}) \\ = \hat{\mathbf{p}}_{\text{cut,max}}(\mathbf{H}_i \oplus \bar{\mathbf{F}}, \mathcal{P}_i, w_i). $$

Since this is the case for all such $\mathcal{P}_i$, it implies that

$$ \hat{\mathbf{p}}_{\text{cut,max}}(\mathbf{H}_{i-1} \oplus \bar{\mathbf{F}}, \mathcal{A}', w_{i-1}) = \hat{\mathbf{p}}_{\text{cut,max}}(\mathbf{H}_i \oplus \bar{\mathbf{F}}, \mathcal{A}', w_i). $$

Therefore, given $s_i = s_{i-1}$,

$$ \hat{\mathbf{p}}_{\text{cut,max}}(\mathbf{G} \oplus \bar{\mathbf{F}}, \mathcal{A}, w) = \hat{\mathbf{p}}_{\text{cut,max}}(\mathbf{H}_i \oplus \bar{\mathbf{F}}, \mathcal{A}', w_i) + s_i. $$

Note that $\mathbf{H}_{|B|}$ is isomorphic to $\bar{\mathbf{X}}$. We thus have

$$ \hat{\mathbf{p}}_{\text{cut,max}}(\mathbf{G} \oplus \bar{\mathbf{F}}, \mathcal{A}, w) = \hat{\mathbf{p}}_{\text{cut,max}}(\bar{\mathbf{X}} \triangleright \bar{\mathbf{F}}, \mathcal{A}', w_{|B|}) + s_{|B|}, $$

so item (iii) holds.

We have $|V(\bar{\mathbf{X}})| \le |X| + 2$ and $|E(\bar{\mathbf{X}})| \le |E(G[X])| + 2|B|$. Moreover, $|\cup \mathcal{A}'| = |\cup \mathcal{A}| + 2$. Therefore, item (i) and (ii) hold. Suppose that $F \setminus A \in \mathcal{H}$. Observe that, since the edges added in $\bar{\mathbf{X}}$ compared to $\mathbf{X}$ all have one endpoint in $\{u_1, u_2\}$, $(\mathbf{X}' \triangleright \bar{\mathbf{F}}) \setminus (\cup \mathcal{A}) \setminus \{u_1, u_2\}$ is isomorphic to $F \setminus A$ and thus belong to $\mathcal{H}$. So item (iv) holds. Thus, $(\mathbf{X}', \mathcal{A}', s_{|B|}, w_{|B|})$ is an $\mathcal{H}$-nice reduction of $(G, \mathcal{A}, w)$ with respect to ANNOTATED MAXIMUM WEIGHTED CUT.

Computing $(\mathbf{H}_i, s_i, w_i)$ takes time $\mathcal{O}(|A| \cdot |I_i|)$ at each step $i$, so the computation takes time $\mathcal{O}(|A| \cdot d)$. Hence, ANNOTATED MAXIMUM WEIGHTED CUT is $\mathcal{H}$-nice. $\square$

MAXIMUM WEIGHTED CUT is an NP-hard problem [28]. However, there exists a polynomial-time algorithm when restricted to some graph classes. In particular, Grötschel and Pulleyblank [22] proved that MAXIMUM WEIGHTED CUT is solvable in polynomial-time on weakly bipartite graphs, and Guenin [23] proved that weakly bipartite graphs are exactly $K_5$-odd-minor-free graphs, which gives the following result.

**Proposition 4.1** ([22, 23]). There is a constant $c \in \mathbb{N}$ and an algorithm that solves MAXIMUM WEIGHTED CUT on $K_5$-odd-minor-free graphs in time $\mathcal{O}(n^c)$.

Moreover, we observe the following.

**Lemma 4.16.** A graph $G$ such that $\text{oct}(G) \le 2$ does not contain $K_5$ as an odd-minor.

*Proof.* Suppose that $G$ contains $K_5$ as an odd-minor and let $\eta$ be an odd $K_5$-expansion of $G$. Let $u, v \in V(G)$ be such that $G' = G \setminus \{u, v\}$ is bipartite. Given that $\eta$ has at least three nodes that do not intersect $\{u, v\}$, it implies that $K_3$ is an odd-minor of $G'$, contradicting its bipartiteness. $\square$

Combining Proposition 4.1 and Lemma 4.16, we have that ANNOTATED MAXIMUM WEIGHTED CUT is FPT parameterized by oct.

**Lemma 4.17.** There is an algorithm that, given a graph $G$, a weight function $w : E(G) \to \mathbb{N}$, and two disjoint sets $X_1, X_2 \subseteq V(G)$, such that $G' = G \setminus (X_1 \cup X_2)$ is bipartite, solves ANNOTATED MAXIMUM WEIGHTED CUT on $(G, X_1, X_2, w)$ in time $\mathcal{O}(k \cdot n' + n'^c)$, where $k = |X_1 \cup X_2|$, $n' = |V(G')|$, and $c$ is the constant of Proposition 4.1.

*Proof.* Let $G''$ be the graph obtained from $G$ by identifying all vertices in $X_1$ (resp. $X_2$) to a new vertex $x_1$ (resp. $x_2$). Let $w' : V(G'') \to \mathbb{N}$ be such that $w'(x_1 x_2) = \sum_{e \in E(G)} w(e) + 1$, $w'(x_i u) = \sum_{x \in X_i} w(xu)$ for
$i \in [2]$ and $u \in N_G(X_i)$, and $w'(e) = w(e)$ otherwise. Let $(X_1^*, X_2^*) \in \mathcal{P}_2(V(G))$ be such that $(X_1, X_2) \subseteq (X_1^*, X_2^*)$. For $i \in [2]$, let $X_i' = X_i^* \setminus X_i$. Then

$$ 
\begin{aligned}
w(X_1^*, X_2^*) &= w(X_1, X_2) + w(X_1', X_2') + \sum_{xy \in E(X_1, X_2')} w(xy) + \sum_{xy \in E(X_1', X_2)} w(xy) \\
&= w(X_1, X_2) + w'(X_1', X_2') + \sum_{u \in X_2' \cap N_G(X_1)} w'(x_1 u) + \sum_{u \in X_1' \cap N_G(X_2)} w'(x_2 u) \\
&= w'(X_1' \cup \{x_1\}, X_2' \cup \{x_2\}) + w(X_1, X_2) - w'(x_1 x_2)
\end{aligned}
$$

Let $\bar{w}$ be the constant $w(X_1, X_2) - w'(x_1 x_2)$. Hence,

$$ f_{\text{cut}}(G, (X_1^*, X_2^*)) = f_{\text{cut}}(G'', (X_1' \cup \{x_1\}, X_2' \cup \{x_2\})) + \bar{w}, $$

and so $\hat{p}_{\text{cut,max}}(G, (X_1, X_2)) = \hat{p}_{\text{cut,max}}(G'', (\{x_1\}, \{x_2\})) + \bar{w}$. Moreover, given that the weight of the edge $x_1 x_2$ is larger than the sum of all other weights, $x_1$ and $x_2$ are never on the same side of a maximum cut in $G''$. Hence, $\hat{p}_{\text{cut,max}}(G'', (\{x_1\}, \{x_2\})) = p_{\text{cut,max}}(G'')$, and therefore,

$$ \hat{p}_{\text{cut,max}}(G, (X_1, X_2)) = p_{\text{cut,max}}(G'') + \bar{w}. $$

Constructing $G''$ takes time $O(k \cdot n)$ and computing $\bar{w}$ takes time $O(k^2)$. Since $\text{oct}(G'') = 2$, according to Proposition 4.1 and Lemma 4.16, an optimal solution to MAXIMUM WEIGHTED CUT on $G''$ can be found in time $O(n'^c)$, and thus, an optimal solution to ANNOTATED MAXIMUM WEIGHTED CUT on $(G, X_1, X_2)$ can be found in time $O(k \cdot (k + n') + n'^c)$. $\square$

We apply Lemma 4.15 and Lemma 4.17 to the dynamic programming algorithm of Lemma 4.1 to obtain the following result.

**Corollary 4.5.** Given a graph $G$ and a bipartite tree decomposition of $G$ of width $k$, there is an algorithm that solves MAXIMUM WEIGHTED CUT on $G$ in time $O(2^k \cdot (k \cdot (k+n') + n^c))$, where $c$ is the constant of Proposition 4.1.

## 5. XP-algorithms for packing problems

Let $\mathcal{G}$ be a graph class. We define the $\mathcal{G}$-PACKING problem as follows.

### $\mathcal{G}$-PACKING

**Input:** A graph $G$.

**Objective:** Find the maximum number $k$ of pairwise-disjoint subgraphs $H_1, \dots, H_k$ such that, for each $i \in [k]$, $H_i \in \mathcal{G}$.

Let $H$ be a graph. If $\mathcal{G} = \{H\}$ (resp. $\mathcal{G}$ is the class of all graphs containing $H$ as a minor/odd-minor/induced subgraph), then we refer to the corresponding problem as $H$-SUBGRAPH-PACKING (resp. $H$-MINOR-PACKING/$H$-ODD-MINOR-PACKING/$H$-INDUCED-SUBGRAPH-PACKING). We remark, in particular, that $K_3$-ODD-MINOR-PACKING is exactly ODD CYCLE PACKING.

If in the definition of $\mathcal{G}$-PACKING we add the condition that there is no edge in the input graph between vertices of different $H_i$'s, then we refer to the corresponding problem as $H$-SCATTERED-PACKING, where we implicitly assume that we refer to the subgraph relation, and where we do not specify a degree of “scatteredness”, as it is usual in the literature when dealing, for instance, with the scattered version of INDEPENDENT SET. For instance, $K_2$-SCATTERED-PACKING is exactly INDUCED MATCHING.

As we prove in Lemma 6.4, $H$-MINOR-PACKING is para-NP-complete parameterized by $\text{btw}$ when $H$ is 2-connected. This is however not the case for $H$-SUBGRAPH-PACKING and $H$-ODD-MINOR-PACKING when $H$ is 2-connected non-bipartite: we provide below an XP-algorithm for both problems.
These algorithms have a similar structure to the dynamic programming algorithm of Lemma 4.1. Namely, for each node $t$ of the bipartite tree decomposition, we reduce $G_t$ to a smaller equivalent instance $G'_t$, and solve the problem on $G'_t$. The main observation here is that the maximum size of a packing is small when restricted to the bag of $t$. Thus, we guess the packing in each bag, and how it intersects the adhesion of $t$ and its neighbors. This guessing is the source of XP-time in our algorithms.

Recall that $\mathbf{p}_{f,\text{opt}}$ is defined in Subsection 4.1. Given a graph class $\mathcal{G}$, $\mathcal{G}$-PACKING, seen as an optimization problem, is the problem of computing $\mathbf{p}_{f,\text{pack,max}}(G)$, where, for every graph $G$, for every $(S, R) \in \mathcal{P}_2(V(G))$,

$$f_{\text{pack}}(G, (S, R)) = \begin{cases} |S| & \text{if there are } |S| \text{ disjoint subgraphs } H_1, \dots, H_{|S|} \text{ in } G \\ |H_i \cap S| = 1 \text{ and } H_i \in \mathcal{G} \text{ for } i \in [|S|], \\ 0 & \text{otherwise.} \end{cases}$$

In the above equation, the pair $(S, R)$ means that $S$ is the part that interacts with the solution, and $R$ is the remainder.

## 5.1. (Induced) Subgraph packing

Let $H$ be a graph. A partial copy of $H$ is a bounded graph $F$ such that there is a bounded graph $F'$ compatible with $F$ with $F \oplus F' = H$. Given a graph $G$ and a set $X \subseteq V(G)$, we denote by $C_{G,X}^H$ the set of all partial copies $F$ of $H$ such that $G[\text{bd}(F)]$ is a subgraph of $G[X]$.

**Lemma 5.1.** Let $\mathcal{H}$ be a graph class and let $H$ be a 2-connected graph with $h$ vertices that does not belong to $\mathcal{H}$. There is an algorithm that, given a graph $G$ and a 1-$\mathcal{H}$-tree decomposition of $G$ of width at most $k$, solves the following problem in time $n^{\mathcal{O}(h \cdot k)}$:

1. H-INDUCED-SUBGRAPH-PACKING, if $\mathcal{H}$ is hereditary.

2. H-SUBGRAPH-PACKING, if $\mathcal{H}$ is monotone.

3. H-SCATTERED-PACKING, if $\mathcal{H}$ is monotone.

*Proof.* The three cases follow from the same argument. When speaking of a “copy” of $H$ in $G$, we mean an induced subgraph of $G$ isomorphic to $H$ for Case 1, and a subgraph of $G$ isomorphic to $H$ for Case 2 and Case 3. If we speak of an $H$-packing, we mean an $H$-induced-subgraph packing in Case 1, an $H$-subgraph packing in Case 2, and an $H$-scattered packing in Case 3.

Let $(T, \alpha, \beta, r)$ be a rooted 1-$\mathcal{H}$-tree decomposition of $G$ of width at most $k$. Let $k \cdot H$ be the union of $k$ disjoint copies of $H$. For each $t \in V(T)$, in a bottom-up manner, for each $F \in C_{G,\delta_t}^{k \cdot H}$, we compute the maximum integer $s_F$, if it exists, such that there exists an $H$-packing $H_1, \dots, H_{s_F}$ in $G_t$ such that $F$ is a bounded (induced in Case 1) subgraph of $G_t \setminus \bigcup_{i \in [s_F]} V(H_i)$. Since $\delta_r = \emptyset$, $s_r^\emptyset$ is the optimum for $H$-(INDUCED-)SUBGRAPH-PACKING on $G$.

Let $t \in V(T)$. We observe that no copy of $H$ is fully contained in $G[\beta(t)]$. In Case 1, this follows immediately from the fact that $H \notin \mathcal{H}$, whereas $G[\beta(t)] \in \mathcal{H}$, and that $\mathcal{H}$ is hereditary. In Case 2 and Case 3, we additionally use the assumption that $\mathcal{H}$ is monotone. We call any copy of $H$ in $G_t$ that intersects $\alpha(t)$ a $t$-inner copy. Given that $H$ is 2-connected and that $H \notin \mathcal{H}$, for any copy of $H$ in $G_t$ that is not a $t$-inner copy, the definition of a 1-$\mathcal{H}$-tree decomposition implies that there is $t' \in \text{chr}_r(t)$ such that this copy is contained in $G_{t'} \setminus \alpha(t)$. We call these copies $t$-outer copies. See Figure 14 for an illustration. Given that $|\alpha(t)| \le k$, it follows that any $H$-subgraph-packing contains at most $k$ $t$-inner copies. For each $t$-inner copy $H'$ of $H$, let $Y_{H'}$ be the set of the children $t'$ of $t$ such that $H'$ intersects $G_{t'} \setminus \alpha(t)$. Since $H'$ has at most $h$ vertices, $|Y_{H'}| \le h$. Thus, for any maximum $H$-packing $S = \{H_1, \dots, H_r\}$ in $G$, the set $Y_t = \{t_1, \dots, t_{|Y_t|}\}$ of children of $t$ that intersect a $t$-inner copy in $S$ has size at most $h \cdot k$. We guess $Y_t$, and note that there are at most $n^{h \cdot k}$ choices. Let $Z_t = \text{chr}_r(t) \setminus Y_t$.

No $t$-inner copy of $S$ intersects $G_{t'} \setminus \delta_{t'}$ for $t' \in Z_t$. Thus, $S$ is maximum when restricted to $G_{t'} \setminus \delta_{t'}$. However, if there is a vertex $v_{t'}$ such that $\delta_{t'} \setminus \alpha(t) = \{v_{t'}\}$, there might still be one $t$-inner copy of $S$ that contains $v_{t'}$. We want to find a maximum $H$-packing on $G_{t'} \setminus \alpha(t)$ that is contained in a maximum $H$-packing
<figure><img src="image_15.png" /><figcaption>Figure 14: Illustration of *t*-inner copies (the blue cycles) and *t*-outer copies (the red cycles). The red regions correspond to $\alpha(t)$ and each blue vertex is the vertex in $\delta_{t'} \setminus \alpha(t)$ for some node $t'$ adjacent to *t*.</figcaption></figure>

of $G$ such that no $t$-inner copy intersecting $Z_t$ is in the packing. We compute inductively $s_{t'}^{+} = s_{t'}^{\mathbf{F}^{+}}$ and $s_{t'}^{-} = s_{t'}^{\mathbf{F}^{-}}$, where $\mathbf{F}^{+}$ and $\mathbf{F}^{-}$ are trivial bounded graphs with boundary $\delta_{t'} \cap \alpha(t)$ and $\delta_{t'}$, respectively. In other words, $s_{t'}^{+}$ (resp. $s_{t'}^{-}$) is the maximum size of an $H$-packing on $G_{t'} \setminus \alpha(t)$ (resp. $G_{t'} \setminus \delta_{t'}$). Note that $s_{t'}^{-} \le s_{t'}^{+} \le s_{t'}^{-} + 1$.

* If $s_{t'}^{-} = s_{t'}^{+}$, then it is optimal to choose a maximum $H$-subgraph-packing on $G_{t'} \setminus \delta_{t'}$. Therefore, we remove $V(G_{t'}) \setminus \delta_{t'}$ from $G$ and set $s_{t'} = s_{t'}^{-}$.

* Otherwise, $s_{t'}^{+} = s_{t'}^{-} + 1$. In this case, $v_{t'}$ has to be part of some copy of $H$ in $S$. So, we may assume that $S$ consists of a maximum $H$-packing in $G_{t'} \setminus \alpha(t')$ and a $t$-outer copy $H'$ of $H$ containing $v_{t'}$. Indeed, if a $t$-inner copy of $S$ intersects $v_{t'}$, then $S$ restricted to $G_{t'} \setminus \delta_{t'}$ has size $s_{t'}^{-}$. If we replace $H'$ and $S$ restricted to $G_{t'} \setminus \delta_{t'}$ by a maximum $H$-packing on $G_{t'} \setminus \alpha(t')$, then we obtain a packing of the same size. Therefore, we remove $(V(G_{t'}) \setminus \delta_{t'}) \cup \{v_{t'}\}$ from $G$ and set $s_{t'} = s_{t'}^{+}$. If there are $z_1, \dots, z_d \in Z_t$ such that $v_{z_1} = \dots = v_{z_d}$ and $s_{z_i}^{+} = s_{z_i}^{-} + 1$ for $i \in [d]$, then we choose one of them arbitrarily, say $z_1$, for which we set $s_{z_1} = s_{z_1}^{+}$, and we set $s_{z_i} = s_{z_i}^{-}$ otherwise, since $v_{z_1}$ is contained in only one copy of an $H$-packing.

Let $\mathbf{F} \in C_{G, \delta}^{k \cdot H}$. Let $\Delta = \delta_t \cup \bigcup_{t' \in Y_t} \delta_{t'}$. Now that we have dealt with the children containing no $t$-inner copy, we only have a few children left. To reduce the size of $G_t$, we will guess the partial $t$-inner copies in each child in $Y_t$. $\mathcal{F}_{\mathbf{F}}$ defined below is the set of all such possible guesses. We set $\mathcal{F} = \{(\mathbf{F}_{t'})_{t' \in Y_t} \mid \forall t' \in Y_t, \mathbf{F}_{t'} \in C_{G, \delta_{t'}}^{k \cdot H}\}$. For each $\mathcal{L} = (\mathbf{F}_{t'})_{t' \in Y_t} \in \mathcal{F}$, we say that $\mathcal{L}$ is compatible with $\mathbf{F}$ if there is $\mathbf{F}_{\mathcal{L}} \in C_{G, \Delta}^{k \cdot H}$ and a partition $(U, U_{t_1}, \dots, U_{t_{|Y|}})$ of the connected components of $\mathbf{F}_{\mathcal{L}} \setminus \Delta$ such that

* $\mathbf{F}_{\mathcal{L}}[V(U) \cup (\delta_t \cap V(F))] = \mathbf{F}$ and

* for $t' \in Y$, $\mathbf{F}_{\mathcal{L}}[V(U_{t'}) \cup (\delta_{t'} \cap V(F_{t'}))] = \mathbf{F}_{t'}$.

Let $\mathcal{F}_{\mathbf{F}}$ be the set of all $\mathcal{L} \in \mathcal{F}$ compatible with $\mathbf{F}$. Let $\mathcal{L} \in \mathcal{F}_{\mathbf{F}}$. Since we guessed how the $t$-inner copies of $S$ interact with each $t' \in Y_t$, we can now compute the $t$-outer copies of $S$ in $G_{t'}$. This is done iteratively by computing $s_{t'}^{\mathbf{F}_{t'}}$. Let $G_{\mathcal{L}}$ be the graph obtained from $\mathbf{G}_t$ by replacing $\mathbf{G}_{t'}$ by $\mathbf{F}_{t'}$ for each $t' \in Y_t$ and removing the vertices of $\Delta \setminus V(F_{\mathcal{L}})$.

Then we guess a set $W$ of $|V(F)| \le h \cdot k$ vertices of $G_{\mathcal{L}}$ that realize $\mathbf{F}$ (there are at most $n^{h \cdot k}$ possible choices) and we remove $W$ from $G_{\mathcal{L}}$ to obtain $G_{\mathcal{L}}^{W}$. Then we compute the size $s_W$ of a maximum $H$-packing
on $G_{\mathcal{L}}^W$. For each $i \in [k]$, we check whether we can find $i$ disjoint copies of $H$ in $G_{\mathcal{L}}^W$ by brute-force. Let $s_{\mathcal{L}} = \max_W s_W + \sum_{t' \in Y_t} s_{t'}^{\mathbf{F}_{t'}} + \sum_{t' \in Z_t} s_{t'\cdot}$. Then it follows that $s_{t}^{\mathbf{F}} = \max_{\mathcal{L} \in \mathcal{F}_{\mathbf{F}}} s_{\mathcal{L}}$.

It remains to upper-bound the running time. There are at most $n^{h \cdot k}$ choices for $Y_t$. Let $h' = h \cdot k$ be the number of vertices of $H'$ and $d = |\Delta| \le k+|Y_t|+1 = \mathcal{O}(h \cdot k)$. There are at most $d! \cdot \binom{d}{h'} \cdot 2^{h'} \cdot |Y_t|^{h'} = (h \cdot k)^{\mathcal{O}(h \cdot k)}$ choices for $\mathbf{F}_{\mathcal{L}}$, and thus for $\mathcal{L}$ and $\mathbf{F}$. There are at most $n^{h \cdot k}$ choices for $W$. Computing $s_W$ takes time at most $(n+h \cdot k)^{\mathcal{O}(h \cdot k)}$, since $G_{\mathcal{L}}^W$ has size at most $n+h \cdot k$. Hence, the running time of the algorithm is upper-bounded by $(h \cdot k \cdot n)^{\mathcal{O}(h \cdot k)}$, which is $n^{\mathcal{O}(h \cdot k)}$ since $k \le n$ by definition and we may assume that $h \le n$. $\square$

**Remark.** Note that the above algorithm has two guessing phases that require XP-time. For the case of *H*-SUBGRAPH-PACKING, however, we can get rid of the second guessing stage using color-coding [29], which allows us to find a subgraph with $\ell$ vertices and treewidth $t$ inside an $n$-vertex graph in time $2^{\mathcal{O}(\ell)} \eta^{\mathcal{O}(t)}$. Since the disjoint union of $k$ copies of $H$ has treewidth less than $h = |V(H)|$ and $h \cdot k$ vertices, the second XP guessing stage can be replaced by an algorithm running in $2^{\mathcal{O}(h \cdot k)} n^{\mathcal{O}(h)}$ time, which is FPT in our parameterization as $h$ is a fixed constant.

## 5.2. Odd-minor-packing

The algorithm for *H*-ODD-MINOR-PACKING is very similar to the one for *H*-SUBGRAPH-PACKING. The main difference is the use of an FPT-algorithm of Kawarabayashi, Reed, and Wollan [7] solving the PARITY $k$-DISJOINT PATHS defined below. We say that the parity of a path is zero if its length is even, and one otherwise.

**PARITY $k$-DISJOINT PATHS**

**Input:** A graph $G$, two disjoint sets $S = \{s_1, \dots, s_k\}$, $T = \{t_1, \dots, t_k\} \subseteq V(G)$, and values $j_1, \dots, j_k \in \{0, 1\}$.

**Objective:** Find, if it exists, $k$ internally-vertex-disjoint paths $P_1, \dots, P_k$ from $S$ to $T$ in $G$ such that $\chi_i$ has endpoints $s_i$ and $t_i$, and parity $j_i$ for $i \in [k]$.

**Proposition 5.1 ([7]).** There is an algorithm running in time $O_k(m \cdot \alpha(m, n) \cdot n)$ for the PARITY $k$-DISJOINT PATHS problem, where $\alpha$ is the inverse of the Ackermann function.

Given that an odd-minor preserves the cycle parity (Lemma 3.1), we make the following observation.

**Observation 5.1.** Any odd-minor of a bipartite graph is bipartite.

Given an odd $H$-expansion $\eta$ for some graph $H$ in a graph $G$, the branch vertices of $\eta$ are the vertices of $\eta$ of degree at least three and the ones incident to an edge not contained in a node of $\eta$.

**Lemma 5.2.** Let $H$ and $G$ be two graphs such that $H$ is an odd-minor of $G$ with $h$ vertices. Any odd $H$-expansion in $G$ has at most $h \cdot (2h - 3)$ branch vertices.

*Proof.* Let $\eta$ be an odd $H$-expansion in $G$. At most $h-1$ vertices of each node of $\eta$ are adjacent to vertices of another node. These $h-1$ vertices are the leaves of the tree induced by the vertices of the node in $G$. By an easy induction, the number of vertices of degree at least three in a tree is at most the number of leaves minus one. Therefore, there are at most $h-1+h-2=2h-3$ branch vertices in each node of $\eta$. Since $\eta$ has $h$ nodes, the result follows. $\square$

Let $H$ be a graph. A *partial odd-model* of $H$ is an odd-minor-minimal bounded graph $\mathbf{F}$ such that there is a *bounded graph* $\mathbf{F}'$ compatible with $\mathbf{F}$ and such that $H$ is an odd-minor of $\mathbf{F} \oplus \mathbf{F}'$. Given a graph $G$ and a set $X \subseteq V(G)$, we denote by $M_{G,X}^H$ the set of all bounded graphs $\mathbf{F}$ such that $G[\text{bd}(\mathbf{F})]$ is a subgraph of $G[X]$.

**Lemma 5.3.** Let $H$ be a 2-connected non-bipartite graph with $h$ vertices. There is an algorithm that, given a graph $G$ and a bipartite tree decomposition of $G$ of width at most $k$, solves *H*-ODD-MINOR-PACKING in time $O_k(n^{\mathcal{O}(h^2 \cdot k)})$.
**Proof.** Let $(T, \alpha, \beta, r)$ be a rooted bipartite tree decomposition of $G$ of width at most $k$. Let $k \cdot H$ be the union of $k$ disjoint copies of $H$. For each $t \in V(T)$, in a bottom-up manner, for each $\mathbf{F} \in \mathcal{M}_{G, \delta_t}^{k \cdot H}$, we compute the maximum integer $s_t^{\mathbf{F}}$, if it exists, such that there exists an $H$-odd-minor-packing $H_1, \dots, H_{s_t^{\mathbf{F}}}$ in $G_t$ where $\mathbf{F}$ is a bounded odd-minor of $G_t \setminus \bigcup_{i \in [s_t^{\mathbf{F}}]} V(H_i)$. Since $\delta_r = \emptyset$, it implies that $s_r^{\emptyset}$ is the optimum for $H$-ODD-MINOR-PACKING on $G$.

Let $t \in V(T)$. Given that $H$ is non-bipartite, according to Observation 5.1, no odd $H$-expansion is contained in $G[\beta(t)]$. We call any odd $H$-expansion in $G_t$ that intersects $\alpha(t)$ a *t*-inner odd-model. Given that $H$ is 2-connected and non-bipartite, for any odd $H$-expansion in $G_t$ that is not a *t*-inner odd-model, there is a $t' \in \text{ch}_r(t)$ such that this odd $H$-expansion is contained in $G_{t'} \setminus \alpha(t)$. We call these odd $H$-expansions *t*-outer odd-models. Given that $|\alpha(t)| \le k$, it follows that at most $k$ many *t*-inner odd-models can be packed at once. Since a *t*-inner odd-model of $H$ has at most $h' = h \cdot (2h - 3)$ branch vertices by Lemma 5.2, for any maximum $H$-odd-minor-packing $S = \{H_1, \dots, H_r\}$ in $G$, the set $Y_t = \{t_1, \dots, t_{|Y_t|}\}$ of children of $t$ that intersect a *t*-inner odd-model in $S$ has size at most $h' \cdot k + k$. The additive term $k$ refers to the fact that each path of the packing between branch vertices may go in and out of a child, but has to intersect at least one vertex in $\alpha(t)$ when crossing, so at most $|\alpha(t)|$ children can be intersected by a *t*-inner odd-model this way. We guess $Y_t$, and note that there are at most $n^{\mathcal{O}(h^2 \cdot k)}$ choices. Let $Z_t = \text{ch}_r(t) \setminus Y_t$.

We proceed similarly to the proof of Lemma 5.1. We compute inductively $s_{t'}^{+} = s_{t'}^{\mathbf{F}^{+}}$ and $s_{t'}^{-} = s_{t'}^{\mathbf{F}^{-}}$, where $\mathbf{F}^{+}$ and $\mathbf{F}^{-}$ are trivial bounded graphs with boundary $\delta_{t'} \cap \alpha(t)$ and $\delta_{t'}$, respectively. In other words, $s_{t'}^{+}$ (resp. $s_{t'}^{-}$) is the maximum size of an $H$-odd-minor-packing on $G_{t'} \setminus \alpha(t)$ (resp. $G_{t'} \setminus \delta_{t'}$). Thus, we observe that $s_{t'}^{-} \le s_{t'}^{+} \le s_{t'}^{-} + 1$.

* If $s_{t'}^{-} = s_{t'}^{+}$, then we remove $V(G_{t'}) \setminus \delta_{t'}$ from $G$ and set $s_{t'} = s_{t'}^{-}$.

* Otherwise, $s_{t'}^{+} = s_{t'}^{-} + 1$. Then, we remove $(V(G_{t'}) \setminus \delta_{t'}) \cup \{v_{t'}\}$ from $G$ and set $s_{t'} = s_{t'}^{+}$. If there are $z_1, \dots, z_d \in Z_t$ such that $v_{z_1} = \dots = v_{z_d}$ and $s_{z_i}^{+} = s_{z_i}^{-} + 1$ for $i \in [d]$, then we choose one of them arbitrarily, say $z_1$, for which we set $s_{z_1} = s_{z_1}^{+}$, and we set $s_{z_i} = s_{z_i}^{-}$ otherwise, since $v_{z_1}$ is contained in only one odd $H$-expansion of an $H$-odd-minor-packing.

Let $\mathbf{F} \in \mathcal{M}_{G, \delta_t}^{k \cdot H}$. Let $\Delta = \delta_t \cup \bigcup_{t' \in Y_t} \delta_{t'}$. Now that we have dealt with the children containing no *t*-inner odd-model, we only have a few children left. To reduce the size of $G_t$, we will guess the partial *t*-inner copies in each child in $Y_t$. $\mathcal{F}_{\mathbf{F}}$, defined as in the proof of Lemma 5.1 but replacing partial copies with partial odd-models, is the set of all possible guesses.

Let $\mathcal{L} \in \mathcal{F}_{\mathbf{F}}$. Since we guessed how the *t*-inner odd-models of $\mathcal{H}$ interact with each $t' \in Y_t$, we can now compute the *t*-outer odd-models of $\mathcal{H}$ in $G_{t'}$. This is done iteratively by computing $s_{t'}^{\mathbf{F}_{t'}}$. Let $G_{\mathcal{L}}$ be the graph obtained from $G_t$ by replacing $G_{t'}$ by $\mathbf{F}_{t'}$ for each $t' \in Y_t$ and removing the vertices of $\Delta \setminus V(F_{\mathcal{L}})$.

Then we guess a set $W$ of $|V(F)| \le h' \cdot k$ vertices of $G_{\mathcal{L}}$ that would be the branch vertices of the *t*-inner odd-models, and of $\mathbf{F}$. There are at most $n^{\mathcal{O}(h^2 \cdot k)}$ possible such choices. Let $s_W$ be the size of the $H$-odd-minor-packing on $G_{\mathcal{L}}$ corresponding to this choice of $W$, if it exists. We can check its existence using Proposition 5.1. To do so, we guess which vertices in $W$ are joined by a path, and what is the parity of the path, so that we obtain $s_W$ disjoint odd $H$-expansions in $G_{\mathcal{L}}$. Since $G_{\mathcal{L}}^W$ has size at most $n + h' \cdot k$, this takes time $\mathcal{O}_k((n + h' \cdot k)^{\mathcal{O}(1)})$. Let $s_{\mathcal{L}} = \max_W s_W + \sum_{t' \in Y_t} s_{t'}^{\mathbf{F}_{t'}} + \sum_{t' \in Z_t} s_{t'}$. Then it follows that $s_t^{\mathbf{F}} = \max_{\mathcal{L} \in \mathcal{F}_{\mathbf{F}}} s_{\mathcal{L}}$.

It remains to upper-bound the running time. There are $n^{\mathcal{O}(h^2 \cdot k)}$ choices for $Y_t$. There are $(h^2 \cdot k)^{\mathcal{O}(h^2 \cdot k)}$ choices for $\mathbf{F}_{\mathcal{L}}$, and thus for $\mathcal{L}$ and $\mathbf{F}$. There are at most $n^{\mathcal{O}(h^2 \cdot k)}$ choices for $W$. Computing $s_W$ takes time $\mathcal{O}_k((n + h^2 \cdot k)^{\mathcal{O}(1)})$. Hence, the running time of the algorithm is $\mathcal{O}_k((h^2 \cdot k \cdot n)^{\mathcal{O}(h^2 \cdot k)})$, which is $\mathcal{O}_k(n^{\mathcal{O}(h^2 \cdot k)})$ as $k \le n$ and we may assume that $h \le n$. $\square$

## 6. NP-completeness on graphs of bounded btw

In this section we present our hardness results. For any graph $G$, it holds that $\text{btw}(G) \le \text{oct}(G)$. Thus, for a problem $\Pi$ to be efficiently solvable on graphs of bounded btw, $\Pi$ needs to be efficiently solvable on graphs
of bounded **oct**, and first and foremost on bipartite graphs. Unfortunately, many problems are **NP**-complete on bipartite graphs (or on graphs of small **oct**), and hence **para-NP**-complete parameterized by **btw**. In this section we provide a non-exhaustive list of such problems. In fact, there also exist problems that are trivial or polynomially solvable on bipartite graphs, but are **para-NP**-complete parameterized by **btw**, such as the 3-COLORING problem discussed in Subsection 6.1.

## 6.1. Coloring

The 3-COLORING problem is defined as follows.

**3-COLORING**

**Input:** A graph $G$.

**Question:** Is $G$ 3-colorable?

Bipartite graphs are 2-colorable, so we could hope for positive results about 3-COLORING on graphs of bounded **oct**, or even bounded **btw**. In fact, we have the following result.

**Lemma 6.1.** *If a graph has bipartite treewidth at most $k$, then it is $(k+2)$-colorable.*

*Proof.* Let $\mathcal{T} = (T, \alpha, \beta)$ be a bipartite tree decomposition of $G$ of width at most $k$. We proceed by induction on $|V(T)|$. For the base case, suppose that $T$ has a unique node $t$. $G[\beta(t)]$ is bipartite, so it is 2-colorable. Thus, if we color each vertex in $\alpha(t)$ with a unique new color, given that $|\alpha(t)| \le k$, we can extend the 2-coloring of $G[\beta(t)]$ to a $(k+2)$-coloring of $G$. Now suppose that $T$ has $\ell \ge 2$ nodes.

Let $t$ be a leaf of $T$. Let $H = G[\bigcup_{t' \in V(T) \setminus \{t\}} (\alpha \cup \beta)(t')].$ $(T \setminus \{t\}, \alpha', \beta')$, where $\alpha'$ and $\beta'$ are the restrictions of $\alpha$ and $\beta$ to $T \setminus \{t\}$, respectively, is a bipartite tree decomposition of $H$ of width at most $k$. By induction, $H$ admits an $(k+2)$-coloring $c$. Let $\delta$ be the adhesion of $t$ and its neighbor. Let $a = |\alpha(t) \cap \delta| \le k$. Given that $|\delta \cap \beta(t)| \le 1$, it follows that $|\delta| \le a+1$. We extend $c$ to a coloring $c'$ of $G[V(H) \cup \alpha(t)]$ by coloring each one of the at most $k-a$ vertices in $\alpha(t) \setminus \delta$ with a unique color that $c$ does not use in $\delta$. Given that no vertex in $\alpha(t) \setminus \delta$ is adjacent to a vertex in $H \setminus \delta$, this coloring is proper.

If $a+1$ colors are used in $\delta$, then it means that there is a (unique) vertex $v \in \delta \cap \beta(t)$. In this case, at node $t$, there is at least $(k+2)-(a+1)-(k-a)=1$ unused color. Otherwise, at most $a$ colors are used in $\delta$, and thus, there are at least $(k+2)-a-(k-a)=2$ unused colors at node $t$. Let $(A, B)$ be a partition witnessing the bipartiteness of $G[\beta(t)]$ such that $v \in A$, if it exists. We color the vertices of $A$ with the color of $v$, if it exists, or one of the two unused color and the vertices of $B$ with the last unused color. Given that the vertices in $A$ (resp. $B$) are not pairwise adjacent and that the vertices in $\beta(t) \setminus \{v\}$ are not adjacent to vertices in $H \setminus \delta$, the coloring remains proper and uses at most $k+2$ colors. $\square$

The result of Lemma 6.1 is tight since any even cycle has bipartite treewidth zero and is 2-colorable, and any odd cycle has bipartite treewidth one and is 3-colorable. Unfortunately, despite of Lemma 6.1, the problem is **para-NP**-complete parameterized by **oct**.

**Lemma 6.2.** *3-COLORING is NP-complete even for graphs of oct at most three.*

*Proof.* We present a reduction from the LIST-3-COLORING problem that is defined as follows.

**LIST-3-COLORING**

**Input:** A graph $G$ and a set $L(v)$ of colors in $[3]$ for each $v \in V(G)$.

**Question:** Is there a proper 3-coloring $c$ of $G$ such that $c(v) \in L(v)$ for each $v \in V(G)$?

The LIST-3-COLORING problem is **NP**-complete even when restricted to planar 3-regular bipartite graphs [30]. Let $(G, L)$ be such an instance of LIST-3-COLORING. Let $G^+$ be the graph obtained from $G$ by adding three vertices $v_1, v_2$, and $v_3$ that are pairwise adjacent and such that for each $v \in V(G)$, $v$ is adjacent to $v_i$ for $i \in [3] \setminus L(v)$. See Figure 15 for an illustration. It is easy to see that $G^+$ admits a proper 3-coloring $c$ if and only if $(G, L)$ admits a proper list coloring $c'$, and, in this case, necessarily, $c_{|V(G)} = c'$. Given that LIST-3-COLORING is **NP**-complete on bipartite graphs and that $\text{oct}(G^+) \le 3$, 3-COLORING is **NP**-complete even for graphs of **oct** at most three. $\square$