<figure><img src="image_16.png" /><figcaption>Figure 15: Example of the construction of $G^+$.</figcaption></figure>

## 6.2. Hardness of covering problems

[31]. However, for some graph classes $\mathcal{G}$, it might change when we restrict the input graph to be bipartite. VERTEX DELETION TO $\mathcal{G}$ is polynomial-time solvable and those for which VERTEX DELETION TO $\mathcal{G}$ remains NP-complete.

A problem $\Pi$ is said to be *trivial* on a graph class $\mathcal{G}$ if the solution to $\Pi$ is the same for every graph $G \in \mathcal{G}$. Otherwise, $\Pi$ is called *nontrivial* on $\mathcal{G}$. Given a graph $G$, let $\nu(G) = |\{N_G(v) | v \in V(G)\}|$. Given a graph class $\mathcal{G}$, let $\nu(\mathcal{G}) = \sup\{\nu(G) | G \in \mathcal{G}\}$.

**Proposition 6.1 ([16]).** Let $\mathcal{G}$ be a hereditary graph class such that VERTEX DELETION TO $\mathcal{G}$ is nontrivial on bipartite graphs.

* If $\nu(\mathcal{G}) = +\infty$, then VERTEX DELETION TO $\mathcal{G}$ is NP-complete on bipartite graphs.

* If $\nu(\mathcal{G}) < +\infty$, then VERTEX DELETION TO $\mathcal{G}$ is polynomial time-solvable on bipartite graphs.

Hence, here is a non-exhaustive list of problems that are NP-complete on bipartite graphs: VERTEX DELETION TO $\mathcal{G}$ where $\mathcal{G}$ is a minor-closed graph class that contains edges (and hence FEEDBACK VERTEX SET, VERTEX PLANARIZATION, H-MINOR-COVER for $H$ containing $P_3$ as a subgraph), H-SUBGRAPH-COVER, H-INDUCED-SUBGRAPH-COVER, and H-ODD-MINOR-COVER for $H$ bipartite graph containing $P_3$ as a (necessarily induced) subgraph, VERTEX DELETION TO GRAPHS OF DEGREE AT MOST $p$ for $p \ge 1$, VERTEX DELETION TO GRAPHS OF GIRTH AT LEAST $p$ for $p \ge 6$ (note that the smallest non-trivial lower bound on the length of a cycle in a bipartite graph is six, or equivalently five).

As a consequence of the above results, all the above problems, when parameterized by bipartite treewidth, are para-NP-complete.

## 6.3. Hardness of packing problems

Kirkpatrick and Hell [24, Theorem 4.2] proved that if $H$ is a graph that contains a $P_3$ (the path on three vertices) as a subgraph, then the problem of partitioning the vertex set of an input graph $G$ into subgraphs isomorphic to $H$ is NP-complete. Let us call this problem $H-PARTITION$. This immediately implies that the $H$-SUBGRAPH-PACKING problem is NP-complete if $H$ contains a $P_3$. In the next lemma we observe that the reduction of Kirkpatrick and Hell [24] can be carefully analyzed so that the same result also applies to bipartite input graphs, and to the induced packing version as well.

**Lemma 6.3.** Let $H$ be a bipartite graph containing $P_3$ as a subgraph. Then $H-PARTITION$ is NP-complete on bipartite graphs. As a consequence, $H$-SUBGRAPH-PACKING and $H$-INDUCED-SUBGRAPH-PACKING are NP-complete on bipartite graphs.

*Proof.* We proceed to discuss the proof for the $H$-SUBGRAPH-PACKING problem, and finally we observe that the same proof applies to the induced subgraph version. The reduction of Kirkpatrick and Hell [24, Lemma 4.1] is from the $h$-DIMENSIONAL MATCHING problem, where $h = |V(H)|$. In this problem, we are given a set of $h$-tuples $\mathcal{T} \subseteq [p]^h$, where $p$ is any positive integer, and the goal is to decide whether there exists a subset $S \subseteq \mathcal{T}$ with $|S| = p$ such that no two elements in $S$ agree in any coordinate. This problem is well-known
to be NP-complete for any $h \ge 3$ [28], which is guaranteed by the hypothesis of the lemma. We need to
introduce some notation. Given a vertex $v \in H$, we denote by $H_v$ the graph obtained from $H$ by adding a
new vertex $v'$ adjacent to $N_H(v)$ (that is, $v'$ becomes a false twin of $v$). Vertices $v, v'$ are called the *connector
vertices of $H_v$* and the newly introduced vertex $v'$ is called the *twin vertex* of $H_v$. Given a vertex $v \in H$, we
denote by $H\langle v \rangle$ the graph obtained from $H$ by adding, for every vertex $u \in V(H)$, a distinct copy of $H_v$ and
identifying vertex $v$ of $H_v$ with $u$. The $h$ twin vertices of the copies of $H_v$, which were not identified with
any vertex, are called the *connector vertices of $H\langle v \rangle$*. In this construction, we call the initial copy of $H$ the
*base copy* of $H$ in $H\langle v \rangle$.

The reduction of Kirkpatrick and Hell [24, Lemma 4.1] proceeds as follows. Let $v^*$ be any vertex of $H$ that is not a cut-vertex and belongs to a biconnected component of $H$ containing at most one cut-vertex, which is always guaranteed to exist. Given an instance $\mathcal{T} \subseteq [p]^h$ of $h$-DIMENSIONAL MATCHING, we construct a graph $G$ as follows. We start with an independent set of size $hp$ whose elements are labeled with pairs $(i, j)$ with $i \in [h]$ and $j \in [p]$. For each $h$-tuple $(t_1, \dots, t_h) \in \mathcal{T}$ we introduce a distinct copy of $H\langle v^* \rangle$ and we identify its $h$ connector vertices arbitrarily with the $h$ vertices labeled $(1, t_1), \dots, (h, t_h)$. It is proved in [24] that $V(G)$ can be partitioned into copies of $H$ if and only if $\mathcal{T}$ is a yes-instance of $h$-DIMENSIONAL MATCHING.

All we need to show is that, if $H$ is bipartite, then the constructed graph $G$ is bipartite as well. For this,
we proceed to define a bipartition function $b: V(G) \rightarrow \{0,1\}$ such that for every edge $uv \in E(G)$ it holds
that $b(u) \neq b(v)$. Since $H$ is bipartite, such a function exists for $H$; we denote it by $b_H$. We start by defining
$b$ restricted to each of the copies $H\langle v^* \rangle$ introduced in the construction (all copies are labeled equally). Recall
that each such copy contains a copy of $H_{v^*}$ for every vertex $v \in V(H)$. We proceed to define $b$ so that
the twin vertex of every copy of $H_{v^*}$ lies on the same side as the vertex of $H$ to which this copy has been
attached. Formally, for every vertex $u$ in the base copy of $H$ in $H\langle v^* \rangle$, we define $b(u) = b_H(u)$. Consider
any vertex $u$ in the base copy of $H$, and let $v$ be any vertex in the copy of $H_{v^*}$ that has been attached to
$u$, different from the twin vertex of that copy. If $b_H(u) = b_H(v^*)$, we let $b(v) = b_H(v)$, otherwise we let
$b(v) = 1 - b_H(v)$. That is, in the latter case, when $u$ and $v^*$ do not agree in $H$, we swap the bipartition
of that copy, except for its twin vertex. Finally, let $w$ be the twin vertex of the copy of $H_{v^*}$ attached to $u$.
We define $b(w) = b(u)$, and note that this is always possible since the two connector vertices of each copy
of $H_{v^*}$ are false twins. It can be easily verified that, for each copy of $H\langle v^* \rangle$, the defined function $b$ induces
a proper bipartition. To conclude the proof, we need to guarantee that, when identifying the connector
vertices of distinct copies of $H\langle v^* \rangle$ according to the $h$-tuples in $\mathcal{T}$, we do not identify two vertices $u$ and
$v$ with $b(u) \neq b(v)$. For this, we use the following trick. Let us consider any fixed ordering of $V(H)$. In
the construction of $G$ described above, for each $h$-tuple $(t_1, \dots, t_h) \in \mathcal{T}$ and its associated copy of $H\langle v^* \rangle$,
instead of identifying its $h$ connector vertices arbitrarily with the $h$ vertices in the independent set labeled
$(1, t_1), \dots, (h, t_h)$, we do it as follows. Each connector vertex $w$ in $H\langle v^* \rangle$ is naturally associated with a vertex
$u$ of the base copy of $H$ to which its copy of $H_{v^*}$ has been attached. Suppose that vertex $u$ is the $i$-th vertex
in the considered ordering of $V(H)$. We then identify the connector vertex $w$ with the vertex labeled $(i, t_i)$
in the independent set. This way, there is no conflict between the function $b$ defined for different copies of
$H\langle v^* \rangle$, and it indeed holds that $b(u) \neq b(v)$ whenever $uv \in E(G)$, concluding the proof.

Finally, to prove the same result for $H$-INDUCED-SUBGRAPH-PACKING, we use exactly the same construction as above, and it suffices to observe that, in a yes-instance, each of the copies of $H$ in $G$ is induced. Indeed, in the proof of [24, Lemma 4.1], the idea of the construction is the following. If a tuple $(t_1, \dots, t_h) \in \mathcal{T}$ is taken into the solution, then in its associated copy of $H\langle v^* \rangle$, the copies of $H$ chosen for the packing are, on the one hand, the base copy of $H$ and, on the other hand, the copy of $H$ in each $H_{v^*}$ containing the connector vertex. For a tuple $(t_1, \dots, t_h) \in \mathcal{T}$ that is not taken into the solution, in its associated copy of $H\langle v^* \rangle$, the copies of $H$ chosen for the packing are just the copy of $H$ in each $H_{v^*}$ not containing the connector vertex. In both cases, each of the chosen copies of $H$ is an induced subgraph of $G$, and the lemma follows. $\square$

Lemma 6.3 is tight for connected graphs $H$. Indeed, if $H$ is connected and $P_3$ is not a subgraph of $H$, then $H$ is either a vertex or an edge. In the former case, the problem is trivial, and the latter is MAXIMUM MATCHING, which is polynomially-time-solvable on general graphs [32].
In the next lemma, we derive from Lemma 6.3 that $H$-MINOR-PACKING is also para-NP-complete parameterized by btw when $H$ contains a $P_3$.

**Lemma 6.4.** Let $H$ be a bipartite graph containing $P_3$ as a subgraph. Then $H$-MINOR-PACKING is NP-complete on bipartite graphs.

*Proof.* We reduce from $H$-PARTITION restricted to bipartite graphs, which is NP-complete by Lemma 6.3. Let $G$ be a bipartite graph as an instance of $H$-PARTITION. Then $G$ has a minor-packing of size at least $|V(G)|/|V(H)|$ if and only if $V(G)$ can be partitioned into copies of $H$, and the lemma follows. $\square$

Note that a similar result to Lemma 6.4 would hold for $H$-INDUCED-MINOR-PACKING.

As a corollary of Lemma 6.4, $H$-ODD-MINOR-PACKING is para-NP-complete parameterized by btw when $H$ is bipartite and contains $P_3$ as a subgraph.

**Lemma 6.5.** Let $H$ be a bipartite graph containing $P_3$ as a subgraph. Then $H$-ODD-MINOR-PACKING is NP-complete on bipartite graphs.

*Proof.* 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. $\square$

As stated in Corollary 4.3, (WEIGHTED) INDEPENDENT SET is solvable in FPT-time when parameterized by btw. Can we go beyond? Unfortunately, $d$-SCATTERED SET, that is, the problem of asking for a set of vertices of size at least $k$ that are pairwise within distance at least $d$, is NP-complete for $d \ge 3$ even for bipartite planar graphs of maximum degree three [33] (when $d=2$, this corresponds to INDEPENDENT SET), so we cannot hope to go further than $d$-SCATTERED SET, parameterized by btw, is para-NP-complete, when $d \ge 3$.

Similarly, INDUCED MATCHING, that is, the problem of finding an induced matching with $k$ edges, is NP-complete on bipartite graphs [25]. In the next lemma, we reduce from INDUCED MATCHING to prove that $H$-SCATTERED-PACKING is para-NP-complete parameterized by btw when $H$ is 2-connected and bipartite.

**Lemma 6.6.** Let $H$ be a 2-connected bipartite graph with at least one edge. Then $H$-SCATTERED-PACKING is NP-complete on bipartite graphs.

*Proof.* We reduce from INDUCED MATCHING on bipartite graphs, which is NP-complete [25], as follows. Let $uv \in E(H)$ and let $H' = H \setminus \{u, v\}$. Let $G$ be a bipartite graph as an instance of INDUCED MATCHING. We build $G'$ as an instance of $H$-SCATTERED-PACKING as follows. Let $e_1, \dots, e_m$ be the edges of $G$. $G'$ is obtained from the disjoint union of $G$ and $m$ graphs $H_1, \dots, H_m$ isomorphic to $H'$ by adding the appropriate edges between $e_i$ and $H_i$ for $i \in [m]$ to create a graph isomorphic to $H$. Note that $G'$ is bipartite.

Given an induced matching $\{e_i \mid i \in I \subseteq [m]\}$ in $G$, $\{G'[e_i \cup V(H_i)] \mid i \in I\}$ is an $H$-scattered packing of the same size in $G'$. Conversely, given an $H$-scattered packing in $G'$, given that $|V(H')| = |V(H)| - 2$ and that $H$ is 2-connected, any occurrence of $H$ in the packing intersects at least one edge of $G$. Hence, this gives rise to an induced matching of the same size in $G$. Thus, for any $k \in \mathbb{N}$, $(G, k)$ is a yes-instance for INDUCED MATCHING if and only if $(G', k)$ is a yes-instance for $H$-SCATTERED-PACKING. $\square$

For $q \ge 2$, it turns out that even asking that the graph $H$ to be packed or covered is non-bipartite is not enough to make the problem tractable. As an illustration of this phenomenon, in the next lemma we prove that $H$-SCATTERED-PACKING is para-NP-complete parameterized by $q$(-torso)-$B$-treewidth for $q \ge 2$ even if $H$ is not bipartite (Lemma 6.7).

**Lemma 6.7.** Let $H$ be a 2-connected graph containing an edge, and let $q \in \mathbb{N}_{\ge 2}$. Then $H$-SCATTERED-PACKING is para-NP-complete parameterized by $(q, B)^{(*)}$-tw.
*Proof.* INDUCED MATCHING is NP-complete on bipartite graphs [25]. Let $H' = H \setminus \{u, v\}$, where $uv \in E(H)$. We reduce from INDUCED MATCHING as follows. Let $G$ be a bipartite graph as an instance of INDUCED MATCHING. We build $G'$ as in the proof of Lemma 6.6, so that, for any $k \in \mathbb{N}$, $(G, k)$ is a yes-instance for INDUCED MATCHING if and only if $(G', k)$ is a yes-instance for $H$-SUBGRAPH-COVER.

Let us show that $(q, \mathcal{B})^{(*)}$-tw$(G') \le (q, \mathcal{B})^{(*)}$-tw$(H)$. Let $\mathcal{T} = (T, \alpha, \beta)$ be a $q$(-torso)-$\mathcal{B}$-tree decomposition of $H$. Since $uv \in E(H)$, there is $t_0 \in V(T)$ such that $u, v \in (\alpha \cup \beta)(t_0)$. Then we build a $q$(-torso)-$\mathcal{B}$-tree decomposition of $G'$ as follows. Let $T'$ be the tree obtained by taking $|E(G')|$ copies of $T$ and making the node $t_0$ of each such copy adjacent to a new node $r$. We set $\beta'(r) = V(G')$, $\alpha'(r) = \emptyset$, and $\alpha'$ and $\beta'$ take the same values as $\alpha$ and $\beta$, respectively, for the other nodes of $T'$. There are at most two vertices in the adhesion of $r$ and any other node, and they are in $\beta(r)$. Moreover, $\text{torso}_G(V(G')) = G' \in \mathcal{B}$. Hence, $(T', \alpha', \beta')$ is a $q$(-torso)-$\mathcal{B}$-tree decomposition of $G'$ of width at most $(q, \mathcal{B})^{(*)}$-tw$(H)$. $\square$

# 7. Further research

In this paper we study the complexity of several problems parameterized by bipartite treewidth, denoted by btw. In particular, our results extend the graph classes for which VERTEX COVER/INDEPENDENT SET, MAXIMUM WEIGHTED CUT, and ODD CYCLE TRANSVERSAL are polynomial-time solvable. A number of interesting questions remain open.

Except for 3-COLORING, all the problems we consider are covering and packing problems. We are still far from a full classification of the variants that are para-NP-complete, and those that are not (FPT or XP). For instance, concerning $H$-SUBGRAPH-COVER, we provided FPT-algorithms when $H$ is a clique (Corollary 4.1). This case is particularly well-behaved because we know that in a tree decomposition every clique appears in a bag. On the other hand, as an immediate consequence of the result of Yannakakis [16] (Proposition 6.1), we know that $H$-SUBGRAPH-COVER is para-NP-complete for every bipartite graph $H$ containing $P_3$ (cf. Subsection 6.2). We do not know what happens when $H$ is non-bipartite and is not a clique. An apparently simple but challenging case is $C_5$-SUBGRAPH-COVER (or any other larger odd cycle). The main difficulty seems to be that $C_5$-SUBGRAPH-COVER does not have the gluing property, which is the main ingredient in this paper to show that a problem is nice, and therefore to obtain an FPT-algorithm. We do not exclude the possibility that the problem is para-NP-complete, as we were not able to obtain even an XP algorithm.

Concerning the packing problems, $H$-(INDUCED-)SUBGRAPH/SCATTERED/ODD-MINOR-PACKING, we provide XP-algorithms for them in Section 5 when $H$ is non-bipartite. Unfortunately, we do not know whether any of them admit an FPT-algorithm, although we suspect that it is indeed the case. We would like to mention that it is possible to apply the framework of equivalence relations and representatives (see for instance [34–36]) to obtain an FPT-algorithm for $K_t$-SUBGRAPH-PACKING parameterized by btw. However, since a number of definitions and technical details are required to present this algorithm, we decided not to include it in this paper. However, when $H$ is not a clique, we do not know whether $H$-SUBGRAPH-PACKING admits an FPT-algorithm. A concrete case that we do not know how to solve is when $H$ is the *paw*, i.e., the 4-vertex graph consisting of one triangle and one pendent edge.

Beyond bipartite tree decompositions, we introduce a more general type of decompositions that we call $q$(-torso)-$\mathcal{H}$-tree decompositions. For $\mathcal{B}$ being the class of bipartite graphs, we prove in Lemma 6.7 that for every $q \ge 2$ and every 2-connected graph $H$ with an edge, $H$-SCATTERED-PACKING is para-NP-complete parameterized by $q$(-torso)-$\mathcal{B}$-treewidth. It should be possible to prove similar results for other covering and packing problems considered in this article.

Most of our para-NP-completeness results consist in proving NP-completeness on bipartite graph (i.e., those with bipartite treewidth zero). There are two exceptions. On the one hand, the NP-completeness of 3-COLORING on graphs with odd cycle transversal at most three (Lemma 6.2) and Lemma 6.7 mentioned above for $H$-SCATTERED-PACKING parameterized by $q$-$\mathcal{B}$-treewidth for every integer $q \ge 2$. It is worth noting that none of our hardness results really exploit the structure of bipartite tree decompositions (i.e., for $q = 1$), beyond being bipartite or having bounded odd cycle transversal. Hence, an interesting question would be whether there is a problem that is NP-complete on graph of bounded bipartite treewidth, but not on graphs of bounded odd cycle transversal.
Finally, as mentioned in the introduction, the goal of this article is to make a first step toward efficient algorithms to solve problems related to odd-minors. We already show in this paper that bipartite treewidth can be useful in this direction, by providing an XP-algorithm for *H-ODD-MINOR-PACKING*. Bipartite treewidth, or strongly related notions, also plays a strong role in the recent series of papers about odd-minors by Campbell, Gollin, Hendrey, and Wiederrecht [10, 17]. This looks like an emerging topic that is worth investigating.

**Acknowledgments.** We thank Sebastian Wiederrecht for his many helpful remarks, and the referees for their thorough reading of the manuscript.

## References

[1] H. Hadwiger, Über eine Klassifikation der Streckenkomplexe, Vierteljschr. Naturforsch. Ges. Zürich 88 (1943) 133–142. URL: https://www.ngzh.ch/archiv/1943_88/88_2/88_17.pdf.

[2] T. R. Jensen, B. Toft, Graph coloring problems, Wiley, 2011. doi:10.1002/9781118032497.

[3] J. Geelen, B. Gerards, B. A. Reed, P. D. Seymour, A. Vetta, On the odd-minor variant of Hadwiger's conjecture, Journal of Combinatorial Theory, Series B 99 (2009) 20–29. doi:10.1016/j.jctb.2008.03.006.

[4] R. Steiner, Improved bound for improper colourings of graphs with no odd clique minor, Combinatorics, Probability and Computing 32 (2023) 326–333. doi:10.1017/S0963548322000268.

[5] E. D. Demaine, M. Hajiaghayi, K. Kawarabayashi, Decomposition, approximation, and coloring of odd-minor-free graphs, in: Proc. of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2010, pp. 329–344. doi:10.1137/1.9781611973075.28.

[6] T. Huynh, The Linkage Problem for Group-labelled Graphs, Ph.D. thesis, University of Waterloo, 2009. URL: http://hdl.handle.net/10012/4716.

[7] K. Kawarabayashi, B. A. Reed, P. Wollan, The graph minor algorithm with parity conditions, in: Proc. of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, 2011, pp. 27–36. doi:10.1109/FOCS.2011.52.

[8] S. Tazari, Faster approximation schemes and parameterized algorithms on (odd-)H-minor-free graphs, Theoretical Computer Science 417 (2012) 95–107. doi:10.1016/j.tcs.2011.09.014.

[9] K. Kawarabayashi, B. A. Reed, An (almost) linear time algorithm for odd cyles transversal, in: Proc. of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2010, pp. 365–378. doi:10.1137/1.9781611973075.31.

[10] R. Campbell, J. P. Gollin, K. Hendrey, S. Wiederrecht, Odd-Minors II: Bipartite treewidth (2023). Manuscript under preparation (private communication).

[11] B. A. Reed, K. Smith, A. Vetta, Finding odd cycle transversals, Operations Research Letters 32 (2004) 299–301. doi:10.1016/j.orl.2003.10.009.

[12] D. Lokshtanov, N. S. Narayanaswamy, V. Raman, M. S. Ramanujan, S. Saurabh, Faster parameterized algorithms using linear programming, ACM Transactions on Algorithms 11 (2014) 15:1–15:31. doi:10.1145/2566616.

[13] E. Eiben, R. Ganian, T. Hamm, O. Kwon, Measuring what matters: A hybrid approach to dynamic programming with treewidth, Journal of Computer and System Sciences 121 (2021) 57–75. doi:10.1016/j.jcss.2021.04.005.
[14] B. M. P. Jansen, J. J. H. de Kroon, FPT algorithms to compute the elimination distance to bipartite graphs and more, in: Proc. of the 47th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), volume 12911 of LNCS, 2021, pp. 80–93. doi:10.1007/978-3-030-86838-3\_6.

[15] A. Agrawal, L. Kanesh, D. Lokshtanov, F. Panolan, M. S. Ramanujan, S. Saurabh, M. Zehavi, Deleting, eliminating and decomposing to hereditary classes are all fpt-equivalent, in: Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2022, pp. 1976–2004. doi:10.1137/1.9781611977073.79.

[16] M. Yannakakis, Node-deletion problems on bipartite graphs, SIAM Journal on Computing 10 (1981) 310–327. doi:10.1137/0210022.

[17] J. P. Gollin, S. Wiederrecht, Odd-Minors I: Excluding small parity breaks, CoRR abs/2304.04504 (2023). arXiv:2304.04504.

[18] J. Chuzhoy, Z. Tan, Towards tight(er) bounds for the Excluded Grid Theorem, Journal of Combinatorial Theory, Series B 146 (2021) 219–265. doi:10.1016/j.jctb.2020.09.010.

[19] N. Robertson, P. D. Seymour, R. Thomas, Quickly excluding a planar graph, Journal of Combinatorial Theory, Series B 62 (1994) 323–348. doi:10.1006/jctb.1994.1073.

[20] V. King, S. Rao, R. E. Tarjan, A faster deterministic maximum flow algorithm, Journal of Algorithms 17 (1994) 447–474. doi:10.1006/jagm.1994.1044.

[21] J. B. Orlin, Max flows in $O(nm)$ time, or better, in: Proc. of the 45th annual ACM Symposium on Theory of Computing Conference (STOC), ACM, 2013, pp. 765–774. doi:10.1145/2488608.2488705.

[22] M. Grötschel, W. R. Pulleyblank, Weakly bipartite graphs and the max-cut problem, Operations Research Letters 1 (1981) 23–27. doi:10.1016/0167-6377(81)90020-1.

[23] B. Guenin, A characterization of weakly bipartite graphs, Journal of Combinatorial Theory, Series B 83 (2001) 112–168. doi:10.1006/jctb.2001.2051.

[24] D. G. Kirkpatrick, P. Hell, On the complexity of general graph factor problems, SIAM Journal on Computing 12 (1983) 601–609. doi:10.1137/0212040.

[25] K. Cameron, Induced matchings, Discrete Applied Mathematics 24 (1989) 97–102. doi:10.1016/0166-218X(92)90275-F.

[26] R. Diestel, Graph Theory, volume 173, Springer-Verlag, 5th edition, 2017. doi:10.1007/978-3-662-53622-3.

[27] L. Chen, R. Kyng, Y. P. Liu, R. Peng, M. P. Gutenberg, S. Sachdeva, Maximum flow and minimum-cost flow in almost-linear time, Journal of the ACM 72 (2025) 19:1–19:103. doi:10.1145/3728631.

[28] R. M. Karp, Reducibility among combinatorial problems, in: 50 Years of Integer Programming 1958-2008 - From the Early Years to the State-of-the-Art, Springer, 2010, pp. 219–241. doi:10.1007/978-3-540-68279-0\_8.

[29] N. Alon, R. Yuster, U. Zwick, Color-coding, Journal of the ACM 42 (1995) 844–856. doi:10.1145/210332.210337.

[30] M. Chlebík, J. Chlebíková, Hard coloring problems in low degree planar bipartite graphs, Discrete Applied Mathematics 154 (2006) 1960–1965. doi:10.1016/j.dam.2006.03.014.

[31] J. M. Lewis, M. Yannakakis, The node-deletion problem for hereditary properties is NP-complete, Journal of Computer and System Sciences 20 (1980) 219–230. doi:10.1016/0022-0000(80)90060-4.
[32] S. Micali, V. V. Vazirani, An $O(\sqrt{|V||E|})$ Algorithm for Finding Maximum Matching in General Graphs, in: Proc. of the 21st Annual Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, 1980, pp. 17–27. doi:10.1109/SFCS.1980.12.

[33] H. Eto, F. Guo, E. Miyano, Distance-d independent set problems for bipartite and chordal graphs, Journal of Combinatorial Optimization 27 (2014) 88–99. doi:10.1007/s10878-012-9594-4.

[34] V. Garnero, C. Paul, I. Sau, D. M. Thilikos, Explicit linear kernels via dynamic programming, SIAM Journal on Discrete Mathematics 29 (2015) 1864–1894. doi:10.1137/140968975.

[35] V. Garnero, C. Paul, I. Sau, D. M. Thilikos, Explicit linear kernels for packing problems, Algorithmica 81 (2019) 1615–1656. doi:10.1007/s00453-018-0495-5.

[36] J. Baste, I. Sau, D. M. Thilikos, A complexity dichotomy for hitting connected minors on bounded treewidth graphs: the chair and the banner draw the boundary, in: Proc. of the 31st ACM-SIAM Symposium on Discrete Algorithms (SODA), 2020, pp. 951–970. doi:10.1137/1.9781611975994.57.