An Updated Experimental Evaluation of Graph Bipartization Methods
Abstract
We experimentally evaluate the practical state-of-the-art in graph bipartization (Odd Cycle Transversal (OCT)), motivated by the need for good algorithms for embedding problems into near-term quantum computing hardware. We assemble a preprocessing suite of fast input reduction routines from the OCT and Vertex Cover (VC) literature and compare algorithm implementations using Quadratic Unconstrained Binary Optimization problems from the quantum literature. We also generate a corpus of frustrated cluster loop graphs, which have previously been used to benchmark quantum annealing hardware. The diversity of these graphs leads to harder OCT instances than in existing benchmarks.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Oct 08, 2021
- Source ID
- 10.1145/3467968
Entities
People
- Blair D Sullivan
- Eric Horton
- Timothy D Goodrich
Organizations
- Air Force Office of Scientific Research
- Gordon and Betty Moore Foundation
- North Carolina State University