Abstract
The Odd Cycle Transversal (OCT) problem asks whether a given undirected graph can be made bipartite by deleting at most k vertices. Although iterative compression algorithms are widely used for solving OCT within fixed-parameter tractable (FPT) bounds, their practical performance is often limited by the exponential number of subsets explored during compression. This paper introduces a heuristic-guided enhancement to iterative compression that integrates structural graph measures — such as degree, betweenness, and closeness centrality — to prioritize promising subsets and prune infeasible configurations early. The proposed method also reuses partial flows and colorings to reduce redundant computations. Experimental results demonstrate substantial runtime improvements, achieving 2x–4x speedups on synthetic and real-world graphs without sacrificing solution quality. Beyond empirical validation, we provide a formal analysis of the heuristic search space and discuss conditions under which compression complexity is reduced.
Publication
Conference
IEEE ComComAp 2025 (Madrid, Spain)
Authors
Mahsa Sadeghi, Yangjun Chen
Affiliation
Applied Computer Science, University of Winnipeg, Canada
Keywords
Odd Cycle Transversal, Graph Bipartization, Iterative Compression, Heuristic Pruning, Graph Coloring, Algorithm Engineering, Network Reliability