{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,31]],"date-time":"2026-01-31T06:06:18Z","timestamp":1769839578218,"version":"3.49.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2021,10,8]],"date-time":"2021-10-08T00:00:00Z","timestamp":1633651200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["NDSEG Fellowship 32 CFR 168a"],"award-info":[{"award-number":["NDSEG Fellowship 32 CFR 168a"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000936","name":"Gordon and Betty Moore Foundation","doi-asserted-by":"publisher","award":["GBMF4560"],"award-info":[{"award-number":["GBMF4560"]}],"id":[{"id":"10.13039\/100000936","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2021,12,31]]},"abstract":"<jats:p>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.<\/jats:p>\n          <jats:p>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 8,000 graph instances are evaluated, compared to the previous canonical corpus of 100 graphs.<\/jats:p>\n          <jats:p>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.<\/jats:p>","DOI":"10.1145\/3467968","type":"journal-article","created":{"date-parts":[[2021,10,8]],"date-time":"2021-10-08T14:36:26Z","timestamp":1633703786000},"page":"1-24","source":"Crossref","is-referenced-by-count":4,"title":["An Updated Experimental Evaluation of Graph Bipartization Methods"],"prefix":"10.1145","volume":"26","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4947-666X","authenticated-orcid":false,"given":"Timothy D.","family":"Goodrich","sequence":"first","affiliation":[{"name":"North Carolina State University, Raleigh, NC, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eric","family":"Horton","sequence":"additional","affiliation":[{"name":"North Carolina State University, Raleigh, NC, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Blair D.","family":"Sullivan","sequence":"additional","affiliation":[{"name":"North Carolina State University and University of Utah, Salt Lake City, UT"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,10,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060675"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.09.023"},{"key":"e_1_2_1_3_1","unstructured":"Takuya Akiba and Yoichi Iwata. 2017. Vertex Cover Solver. Retrieved from https:\/\/github.com\/wata-orz\/vertex_cover.  Takuya Akiba and Yoichi Iwata. 2017. Vertex Cover Solver. Retrieved from https:\/\/github.com\/wata-orz\/vertex_cover."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1103\/RevModPhys.74.47"},{"key":"e_1_2_1_5_1","unstructured":"John E. Beasley. 1998. Heuristic algorithms for the unconstrained binary quadratic programming problem.  John E. Beasley. 1998. Heuristic algorithms for the unconstrained binary quadratic programming problem."},{"key":"e_1_2_1_6_1","unstructured":"John E. Beasley. 2018. OR-Library. Retrieved from http:\/\/people.brunel.ac.uk\/ mastjjb\/jeb\/info.html.  John E. Beasley. 2018. OR-Library. Retrieved from http:\/\/people.brunel.ac.uk\/ mastjjb\/jeb\/info.html."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0172505"},{"key":"e_1_2_1_8_1","first-page":"343","article-title":"Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design. Quantum Info","volume":"10","author":"Choi Vicky","year":"2011","journal-title":"Process."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00012580"},{"key":"e_1_2_1_10_1","unstructured":"Iain Dunning Swati Gupta and John Silberholz. 2015. What Works Best When? A Framework for Systematic Heuristic Evaluation. Retrieved from http:\/\/www.optimization-online.org\/DB_FILE\/2015\/05\/4895.pdf.  Iain Dunning Swati Gupta and John Silberholz. 2015. What Works Best When? A Framework for Systematic Heuristic Evaluation. Retrieved from http:\/\/www.optimization-online.org\/DB_FILE\/2015\/05\/4895.pdf."},{"key":"e_1_2_1_11_1","first-page":"17","article-title":"On the evolution of random graphs","volume":"5","author":"Erdos Paul","year":"1960","journal-title":"Publ. Math. Inst. Hung. Acad. Sci."},{"key":"e_1_2_1_12_1","first-page":"336","article-title":"Adaptive memory tabu search for binary quadratic programs. Manage","volume":"44","author":"Glover Fred","year":"1998","journal-title":"Sci."},{"key":"e_1_2_1_13_1","first-page":"61","article-title":"Linear Programming Kit (GLPK)","volume":"4","author":"GNU.","year":"2017","journal-title":"Version"},{"key":"e_1_2_1_14_1","volume-title":"Sullivan","author":"Goodrich Timothy D.","year":"2018"},{"key":"e_1_2_1_15_1","first-page":"5","article-title":"Optimizing adiabatic quantum program compilation using a graph-theoretic framework","volume":"17","author":"Goodrich Timothy D.","year":"2018","journal-title":"Quant. Info. Process."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11128-016-1513-7"},{"key":"e_1_2_1_17_1","unstructured":"Falk H\u00fcffner. 2006. occ. Retrieved from http:\/\/theinf1.informatik.uni-jena.de\/occ\/.  Falk H\u00fcffner. 2006. occ. Retrieved from http:\/\/theinf1.informatik.uni-jena.de\/occ\/."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00177"},{"key":"e_1_2_1_19_1","unstructured":"IBM. 2017. CPLEX Optimization Studio 12.8. Retrieved from https:\/\/www.ibm.com\/analytics\/data-science\/prescriptive-analytics\/cplex-o ptimizer.  IBM. 2017. CPLEX Optimization Studio 12.8. Retrieved from https:\/\/www.ibm.com\/analytics\/data-science\/prescriptive-analytics\/cplex-o ptimizer."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.127"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Yoichi Iwata Yutaro Yamaguchi and Yuichi Yoshida. 2017. 0\/1\/all CSPs Half-Integral A-path Packing and Linear-Time FPT Algorithms.  Yoichi Iwata Yutaro Yamaguchi and Yuichi Yoshida. 2017. 0\/1\/all CSPs Half-Integral A-path Packing and Linear-Time FPT Algorithms.","DOI":"10.1109\/FOCS.2018.00051"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.7566\/JPSJ.88.061007"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/21.87054"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2635810"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1970-125-1"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2566616"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10217-2_37"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201912)","volume":"434","author":"Lokshtanov Daniel","year":"2012"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215074"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.3389\/fphy.2014.00005"},{"key":"e_1_2_1_31_1","volume-title":"Macready","author":"Neven Hartmut","year":"2008"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178454"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2003.10.009"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.3390\/e19090500"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevX.5.031040"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.102"},{"key":"e_1_2_1_37_1","unstructured":"Sebastian Wernicke. 2003. On the algorithmic tractability of single nucleotide polymorphism (SNP) analysis and related problems.  Sebastian Wernicke. 2003. On the algorithmic tractability of single nucleotide polymorphism (SNP) analysis and related problems."}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3467968","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3467968","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3467968","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:19:05Z","timestamp":1750191545000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3467968"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,8]]},"references-count":37,"alternative-id":["10.1145\/3467968"],"URL":"https:\/\/doi.org\/10.1145\/3467968","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10,8]]}}}