TY - GEN
T1 - Dynamic Programming on Bipartite Tree Decompositions
AU - Jaffke, Lars
AU - Morelle, Laure
AU - Sau, Ignasi
AU - Thilikos, Dimitrios M.
N1 - Publisher Copyright:
© 2023 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.
PY - 2023/12
Y1 - 2023/12
N2 - We revisit a graph width parameter that we dub bipartite treewidth, along with its associated graph decomposition that we call 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 para-NP-completeness results, FPT-algorithms, and XP-algorithms, as well as several open problems. In particular, we show that Kt-Subgraph-Cover, Weighted Vertex Cover/Independent Set, Odd Cycle Transversal, and 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 H-Subgraph- Packing, H-Induced-Packing, H-Scattered-Packing, and H-Odd-Minor-Packing problems: if H is bipartite, then the problem is 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-H-treewidth by replacing the bipartite graph class by any graph class H. Most of the technology developed here also works for this more general parameter.
AB - We revisit a graph width parameter that we dub bipartite treewidth, along with its associated graph decomposition that we call 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 para-NP-completeness results, FPT-algorithms, and XP-algorithms, as well as several open problems. In particular, we show that Kt-Subgraph-Cover, Weighted Vertex Cover/Independent Set, Odd Cycle Transversal, and 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 H-Subgraph- Packing, H-Induced-Packing, H-Scattered-Packing, and H-Odd-Minor-Packing problems: if H is bipartite, then the problem is 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-H-treewidth by replacing the bipartite graph class by any graph class H. Most of the technology developed here also works for this more general parameter.
KW - bipartite graphs
KW - dynamic programming
KW - independent set
KW - maximum cut
KW - odd cycle transversal
KW - odd-minors
KW - packing
KW - tree decomposition
KW - vertex cover
UR - http://www.scopus.com/inward/record.url?scp=85180557060&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85180557060&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.IPEC.2023.26
DO - 10.4230/LIPIcs.IPEC.2023.26
M3 - Conference contribution
AN - SCOPUS:85180557060
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 18th International Symposium on Parameterized and Exact Computation, IPEC 2023
A2 - Misra, Neeldhara
A2 - Wahlstrom, Magnus
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 18th International Symposium on Parameterized and Exact Computation, IPEC 2023
Y2 - 6 September 2023 through 8 September 2023
ER -