English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

We experimentally evaluate the practical state-of-the-art in graphbipartization (Odd Cycle Transversal), motivated by recent advances innear-term quantum computing hardware and the related embedding problems. Weassemble a preprocessing suite of fast input reduction routines from the OddCycle Transversal (OCT) and Vertex Cover (VC) literature, and compare algorithmimplementations using Quadratic Unconstrained Binary Optimization problems fromthe quantum literature. We also generate a corpus of frustrated cluster loopgraphs, which have previously been used to benchmark quantum annealinghardware. The diversity of these graphs leads to harder OCT instances than inexisting benchmarks.  In addition to combinatorial branching algorithms for solving OCT directly,we study various reformulations into other NP-hard problems such as VC andInteger Linear Programming (ILP), enabling the use of solvers such as CPLEX. Wefind that for heuristic solutions with time constraints under a second,iterative compression routines jump-started with a heuristic solution performbest, after which point using a highly tuned solver like CPLEX is worthwhile.Results on exact solvers are split between using ILP formulations on CPLEX andsolving VC formulations with a branch-and-reduce solver. We extend our resultswith a large corpus of synthetic graphs, establishing robustness and potentialto generalize to other domain data. In total, over 8000 graph instances areevaluated, compared to the previous canonical corpus of 100 graphs.  Finally, we provide all code and data in an open source suite, including aPython API for accessing reduction routines and branching algorithms, alongwith scripts for fully replicating our results.

An Updated Experimental Evaluation of Graph Bipartization Methods