Dynamic programming on bipartite tree decompositions - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2023

Dynamic programming on bipartite tree decompositions

Lars Jaffke
Laure Morelle
Ignasi Sau

Abstract

We revisit a graph width parameter that we dub \emph{bipartite treewidth}, along with its associated graph decomposition that we call \emph{bipartite tree decomposition}. Bipartite treewidth can be seen as a common generalization of treewidth and the odd cycle transversal number. Intuitively, a bipartite tree decomposition is a tree decomposition whose bags induce almost bipartite graphs and whose adhesions contain at most one vertex from the bipartite part of any other bag, while the width of such decomposition measures how far the bags are from being bipartite. Adapted from a tree decomposition originally defined by Demaine, Hajiaghayi, and Kawarabayashi [SODA 2010] and explicitly defined by Tazari [Theor. Comput. Sci. 2012], bipartite treewidth appears to play a crucial role for solving problems related to odd-minors, which have recently attracted considerable attention. As a first step toward a theory for solving these problems efficiently, the main goal of this paper is to develop dynamic programming techniques to solve problems on graphs of small bipartite treewidth. For such graphs, we provide a number of \textsf{para-}\NP-completeness results, \FPT-algorithms, and \XP-algorithms, as well as several open problems. In particular, we show that {\sc $K_t$-Subgraph-Cover}, {\sc Weighted Vertex Cover/Independent Set}, {\sc Odd Cycle Transversal}, and {\sc Maximum Weighted Cut} are $\FPT$ parameterized by bipartite treewidth. We also provide the following complexity dichotomy when $H$ is a 2-connected graph, for each of the {\sc $H$-Subgraph-Packing}, {\sc $H$-Induced-Packing}, {\sc $H$-Scattered-Packing}, and {\sc $H$-Odd-Minor-Packing} problems: if $H$ is bipartite, then the problem is {\sf para-NP}-complete parameterized by bipartite treewidth while, if $H$ is non-bipartite, then the problem is solvable in \XP-time. Beyond bipartite treewidth, we define 1-$\Hcal$-treewidth by replacing the bipartite graph class by any graph class $\Hcal$. Most of the technology developed here also works for this more general parameter.
Fichier principal
Vignette du fichier
biptw_camera.pdf (864.02 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

lirmm-04253839 , version 1 (23-10-2023)

Identifiers

Cite

Lars Jaffke, Laure Morelle, Ignasi Sau, Dimitrios M. Thilikos. Dynamic programming on bipartite tree decompositions. IPEC 2023 - 18th International Symposium on Parameterized and Exact Computation, Sep 2023, Amsterdam, Netherlands. pp.16:1-16:22, ⟨10.4230/LIPIcs.IPEC.2023.26⟩. ⟨lirmm-04253839⟩
9 View
8 Download

Altmetric

Share

More