×

zbMATH — the first resource for mathematics

QUBO formulations of the longest path problem. (English) Zbl 07325910
Summary: The longest path problem on graphs is an NP-hard optimization problem, and as such, it is not known to have an efficient classical solution in the general case. This study develops two quadratic unconstrained binary optimization (QUBO) formulations of this well-known problem. The first formulation is based on an approach outlined by (Bauckhage et al., 2018) for the shortest path problem and follows simply from the principle of assigning positions on the path to vertices; using \(k | V |\) binary variables, this formulation will find the longest path that visits exactly \(k\) of a graph’s \(| V |\) vertices, if such a path exists. As a point of theoretical interest, we present a second formulation based on degree constraints that is more complicated, but reduces the dependence of the number of variables on \(k\) to logarithmic; specifically, it requires \(|V| + 2 |E| \lfloor \log_2 k \rfloor + 3 |E|\) binary variables to encode the longest path problem. We adapt these basic formulations for several variants of the standard longest path problem. Scaling factors for penalty terms and preprocessing time required to construct the \(\mathbf Q\) matrix representing the problem are made explicit in the paper.
MSC:
68Qxx Theory of computing
PDF BibTeX Cite
Full Text: DOI
References:
[1] (2020), D-Wave announces general availability of first quantum computer built for business
[2] Alidaee, Bahram; Glover, Fred; Kochenberger, Gary A.; Rego, Cesar, A new modeling and solution approach for the number partitioning problem, Adv. Decis. Sci., 2005, 2, 113-121 (2005) · Zbl 1172.90511
[3] Alon, Noga; Yuster, Raphael; Zwick, Uri, Color-coding, J. ACM, 42, 4, 844-856 (1995) · Zbl 0885.68116
[4] Azaron, Amir; Katagiri, Hideki; Kato, Kosuke; Sakawa, Masatoshi, Longest path analysis in networks of queues: dynamic scheduling problems, Eur. J. Oper. Res., 174, 1, 132-149 (2006) · Zbl 1116.90025
[5] Bauckhage, Christian; Brito, Eduardo; Cvejoski, Kostadin; Ojeda, César, Towards shortest paths via adiabatic quantum computing, (Mining and Learning with Graphs (MLG). Mining and Learning with Graphs (MLG), London (2018))
[6] Bomze, Immanuel M.; Budinich, Marco; Pardalos, Panos M.; Pelillo, Marcello, The maximum clique problem, (Handbook of Combinatorial Optimization (1999), Springer), 1-74 · Zbl 1253.90188
[7] Born, Max; Fock, Vladimir, Beweis des adiabatensatzes, Z. Phys., 51, 165-180 (1928) · JFM 54.0994.03
[8] Boros, Endre; Crama, Yves; Rodríguez-Heck, Elisabeth, Compact quadratizations for pseudo-Boolean functions, J. Comb. Optim., 39, 687-707 (2020) · Zbl 1441.90092
[9] Boros, Endre; Hammer, Peter L., The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds, Ann. Oper. Res., 33, 3, 151-180 (1991) · Zbl 0741.90077
[10] Boros, Endre; Hammer, Peter L., Pseudo-Boolean optimization, Discrete Appl. Math., 123, 1, 155-225 (2002) · Zbl 1076.90032
[11] Chen, Jianer; Kneis, Joachim; Lu, Songjian; Mölle, Daniel; Richter, Stefan; Rossmanith, Peter; Sze, Sing-Hoi; Zhang, Fenghui, Randomized divide-and-conquer: improved path, matching, and packing algorithms, SIAM J. Comput., 38, 6, 2526-2547 (2009) · Zbl 1191.68849
[12] Cohen, Nathann, Several Graph Problems and Their Linear Program Formulations (2019)
[13] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford, Introduction to Algorithms (2009), MIT Press · Zbl 1187.68679
[14] Date, Prasanna; Arthur, Davis; Pusey-Nazzaro, Lauren, QUBO Formulations for Training Machine Learning Models (2020)
[15] Downey, R. G.; Fellows, M. R., Fixed-parameter intractability, (Proceedings of the Seventh Annual Structure in Complexity Theory Conference. Proceedings of the Seventh Annual Structure in Complexity Theory Conference, Boston, MA (1992)), 36-49
[16] Farhi, Edward; Goldstone, Jeffrey; Gutmann, Sam; Sipser, Michael, Quantum computation by adiabatic evolution (2000), MIT, Technical Report 2936
[17] Finnila, Aleta Berk; Gomez, M. A.; Sebenik, C.; Stenson, Catherine; Doll, Jimmie D., Quantum annealing: a new method for minimizing multidimensional functions, Chem. Phys. Lett., 219, 5-6, 343-348 (1994)
[18] Jensen, T. R.; Toft, B., Choosability versus chromaticity, Geombinatorics, 5, 45-64 (1995) · Zbl 0855.05055
[19] Jörg, T.; Krzakala, F.; Kurchan, J.; Maggs, A. C.; Pujos, J., Energy gaps in quantum first-order mean-field-like transitions: the problems that quantum annealing cannot solve, Europhys. Lett., 89, 4, Article 40004 pp. (2010)
[20] Kadowaki, Tadashi; Nishimori, Hidetoshi, Quantum annealing in the transverse Ising model, Phys. Rev. E, 58, 5, 5355 (1998)
[21] Karger, D.; Motwani, R.; Ramkumar, G. D.S., On approximating the longest path in a graph, Algorithmica, 18, 82-98 (1997) · Zbl 0876.68083
[22] Keshavarz-Kohjerdi, Fatemeh; Bagheri, Alireza; Asgharian-Sardroud, Asghar, A linear-time algorithm for the longest path problem in rectangular grid graphs, Discrete Appl. Math., 160, 3, 210-217 (2012) · Zbl 1237.05115
[23] Krauss, Thomas; McCollum, Joey, Solving the network shortest path problem on a quantum annealer, IEEE Trans. Quantum Eng., 1, Article 3101512 pp. (2020), 1-12
[24] Krauss, Thomas; McCollum, Joey; Pendery, Chapman; Litwin, Sierra; Michaels, Alan J., Solving the max-flow problem on a quantum annealing computer, IEEE Trans. Quantum Eng., 1, Article 3101910 pp. (2020), 1-10
[25] Lucas, Andrew, Ising formulations of many NP problems, Front. Phys., 2 (2014)
[26] Monien, B., How to find long paths efficiently, (Ausiello, G.; Lucertini, M., Analysis and Design of Algorithms for Combinatorial Problems. Analysis and Design of Algorithms for Combinatorial Problems, North-Holland Mathematics Studies, vol. 109 (1985), North-Holland), 239-254 · Zbl 0603.68069
[27] Ben Reichardt, W., The quantum adiabatic optimization algorithm and local minima, (STOC ’04: Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing. STOC ’04: Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, Chicago, IL (2004)), 502-510 · Zbl 1192.81098
[28] Sedgewick, Robert; Wayne, Kevin, Algorithms (2011), Addison-Wesley Professional
[29] Somma, Rolando D.; Nagaj, Daniel; Kieferová, Mária, Quantum speedup by quantum annealing, Phys. Rev. Lett., 109, 5, Article 1 pp. (2012)
[30] Dekel, Tsur, Faster deterministic parameterized algorithm for k-path, Theor. Comput. Sci., 790, 96-104 (2019) · Zbl 1430.68247
[31] Uehara, Ryuhei; Uno, Yushi, Efficient algorithms for the longest path problem, (Fleischer, Rudolf; Trippen, Gerhard, Algorithms and Computation (2005), Springer: Springer Berlin), 871-883 · Zbl 1116.05318
[32] Zwick, Uri, Exact and approximate distances in graphs – a survey, (auf der Heide, Friedhelm Meyer, Algorithms - ESA 2001 (2001), Springer: Springer Berlin), 33-48 · Zbl 1006.68543
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.