An Updated Experimental Evaluation of Graph Bipartization Methods

DOI10.1145/3467968MaRDI QIDQ5102059zbMATH OpenOpenAlexFDO

Authors Timothy D. Goodrich, Eric Horton, Blair D. Sullivan

Publication date 6 September 2022

Published in ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1805.01041

zbMATH Keywords

integer linear programmingvertex covernear-term quantum computingodd-cycle transversal

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Quantum algorithms and complexity in the theory of computing (68Q12) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: 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, 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. 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 extend our results with a large corpus of synthetic graphs, establishing robustness and potential to generalize to other domain data. In total, over 8000 graph instances are evaluated, compared to the previous canonical corpus of 100 graphs. 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.

Recommendations

• Graph partitioning: an updated survey
• Evaluation of a Flow-Based Hypergraph Bipartitioning Algorithm
• Comparing recent methods in graph partitioning
• Faster graph bipartization
• scientific article; zbMATH DE number 1942408
• Research of multicriteria theoretical segmentation tasks on bipartite graphs
• A computational study of graph partitioning
• Graph Bipartization and via minimization
• Algorithm Engineering for Optimal Graph Bipartization
• Experimental and Efficient Algorithms

Cites work

• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• k-Degenerate Graphs
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• Adaptive memory tabu search for binary quadratic programs
• Algorithm Engineering for Optimal Graph Bipartization
• Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover
• Compression via Matroids
• Connected components in random graphs with given expected degree sequences
• Faster parameterized algorithms using linear programming
• Finding odd cycle transversals.
• Identifying the minor set cover of dense connected bipartite graphs via random matching edge sets
• LP-branching algorithms based on biased graphs
• Linear-time FPT algorithms via network flow
• Minor-embedding in adiabatic quantum computation. II: Minor-universal graph design
• Optimizing adiabatic quantum program compilation using a graph-theoretic framework
• Simpler parameterized algorithm for OCT
• Statistical mechanics of complex networks
• Subexponential parameterized odd cycle transversal on planar graphs
• \(O(\sqrt{\log n})\) approximation algorithms for Min UnCut, Min 2CNF deletion, and directed cut problems

Cited in

(1)

• Preprocessing to reduce the search space for odd cycle transversal

This page was built for publication: An Updated Experimental Evaluation of Graph Bipartization Methods

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