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.

Presented in IPEC 2023