Résumé
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 -Subgraph-Cover, Weighted Independent Set, Odd Cycle Transversal, and Maximum Weighted Cut are 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.