QUBO formulations of the longest path problem.

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 | ⌊ log 2 ⁡ k ⌋ + 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 Q matrix representing the problem are made explicit in the paper. [ABSTRACT FROM AUTHOR]