SDP Approach to Quadratic Vertex-Disjoint Paths Problem
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2604.03452
curl -X POST /api/v1/records/arxiv/2604.03452/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2604.03452/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'