Evaluating Graph Bipartization Methods for Applications in Quantum Computing
Timothy D. Goodrich, Eric Horton, Blair D. Sullivan · arXiv (Cornell University) · 2018
We experimentally evaluate the practical state-of-the-art in graph bipartization (Odd Cycle Transversal), motivated by recent advances in near-term quantum computing hardware and the related embedding problems. We assemble a preprocessing suite of fast input reduction routines from the Odd Cycle Transversal (OCT) and Vertex Cover (VC) literature, allowing algorithm implementations to be compared using Quadratic Unconstrained Binary Optimization problems from the quantum literature. These problems represent a wide array of graph properties, leading to harder OCT instances than in previous benchmarks. In addition to combinatorial branching algorithms for solving OCT directly, we study various reformulations into other NP-hard problems such as VC and Integer Linear Programming (ILP), enabling the use of solvers such as CPLEX. We find that for heuristic solutions with time constraints under a second, iterative compression routines jump-started with a heuristic solution perform best, after which point using a highly tuned solver like CPLEX is worthwhile. Results on exact solvers are split between using ILP formulations on CPLEX and solving VC formulations with a branch-and-reduce solver. We compare our results to those on a corpus of synthetic graphs, establishing robustness and potential to generalize to other domain data. Finally, we provide all code and data in an open source suite, including a Python API for accessing reduction routines and branching algorithms, along with scripts for fully replicating our results.