Preprocessing to reduce the search space for odd cycle transversal

DOI10.4230/LIPICS.IPEC.2024.15MaRDI QIDQ7255451zbMATH OpenFDO

Authors Bart M. P. Jansen, Yosuke Mizutani, Blair D. Sullivan, Ruben F. A. Verhaegh

Publication date 29 May 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.IPEC.2024.15

zbMATH Keywords

graph decompositionodd cycle transversalparameterized complexitysearch-space reductionwitness of optimality

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parameterized complexity, tractability and kernelization (68Q27) Algorithms in computer science (68Wxx)

Cites work

• Algorithm Engineering for Optimal Graph Bipartization
• An Updated Experimental Evaluation of Graph Bipartization Methods
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Compression via Matroids
• Crown structures for vertex cover kernelization
• Faster parameterized algorithms using linear programming
• Finding odd cycle transversals.
• FPT algorithms to compute the elimination distance to bipartite graphs and more
• Graph-Theoretic Concepts in Computer Science
• scientific article; zbMATH DE number 1261820 (Why is no real title available?)
• Optimizing adiabatic quantum program compilation using a graph-theoretic framework
• Parameterized algorithms
• Preprocessing to reduce the search space: antler structures for feedback vertex set
• Representative sets and irrelevant vertices: new tools for kernelization
• Search-space reduction via essential vertices
• Search-space reduction via essential vertices revisited: vertex multicut and cograph deletion
• Single-exponential FPT algorithms for enumerating secluded \(\mathcal{F}\)-free subgraphs and deleting to scattered graph classes

This page was built for publication: Preprocessing to reduce the search space for odd cycle transversal

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