Dynamic programming on bipartite tree decompositions

DOI10.1016/J.JCSS.2025.103722MaRDI QIDQ6885361zbMATH OpenFDO

Authors Lars Jaffke, Laure Morelle, Ignasi Sau, Dimitrios M. Thilikos

Publication date 11 December 2025

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

zbMATH Keywords

dynamic programmingindependent setpackingvertex coverbipartite graphsmaximum cuttree decompositionodd cycle transversalodd-minors

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parameterized complexity, tractability and kernelization (68Q27)

Cites work

• scientific article; zbMATH DE number 6737879 (Why is no real title available?)
• scientific article; zbMATH DE number 6297711 (Why is no real title available?)
• scientific article; zbMATH DE number 6297714 (Why is no real title available?)
• scientific article; zbMATH DE number 3102312 (Why is no real title available?)
• A characterization of weakly bipartite graphs
• A complexity dichotomy for hitting connected minors on bounded treewidth graphs: the chair and the banner draw the boundary
• Color-coding
• Deleting, eliminating and decomposing to hereditary classes are all FPT-equivalent
• Distance-\(d\) independent set problems for bipartite and chordal graphs
• Explicit linear kernels for packing problems
• Explicit linear kernels via dynamic programming
• FPT algorithms to compute the elimination distance to bipartite graphs and more
• Faster approximation schemes and parameterized algorithms on (odd-)H-minor-free graphs
• Faster parameterized algorithms using linear programming
• Finding odd cycle transversals.
• Hard coloring problems in low degree planar bipartite graphs
• Improved bound for improper colourings of graphs with no odd clique minor
• Induced matchings
• Maximum flow and minimum-cost flow in almost-linear time
• Measuring what matters: a hybrid approach to dynamic programming with treewidth
• Node-Deletion Problems on Bipartite Graphs
• On the Complexity of General Graph Factor Problems
• On the odd-minor variant of Hadwiger's conjecture
• Quickly excluding a planar graph
• Reducibility among combinatorial problems
• The Graph Minor Algorithm with Parity Conditions
• The node-deletion problem for hereditary properties is NP-complete
• Towards tight(er) bounds for the excluded grid theorem
• Weakly bipartite graphs and the max-cut problem

This page was built for publication: Dynamic programming on bipartite tree decompositions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6885361)