{"id":"arxiv/2604.03452","url":"https://arxiv.org/abs/2604.03452","tags":["math.OC"],"score":0,"title":"SDP Approach to Quadratic Vertex-Disjoint Paths Problem","domain":"math.OC","source":"arxiv","authors":["Mingming Xu","Hao Hu"],"reviews":0,"subject":"math.OC","summary":"We study the quadratic $k$-vertex-disjoint paths problem (Q-$k$-VDP), which seeks $k$ vertex-disjoint paths in a directed graph that minimize a nonconvex quadratic objective function. We formulate the problem as a binary quadratic program and apply a systematic graph reduction to manage its dimensionality. To obtain a tractable bounding model, we drop the subtour-elimination constraints and derive a semidefinite programming (SDP) relaxation. We then solve this relaxed model within a branch-and-bound framework, where the bounds are computed from the SDP relaxation using a tailored alternating…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-04-03","reactions":{}}