Special cases of the quadratic shortest path problem

Hao Hu () and Renata Sotirov ()
Additional contact information
Hao Hu: Tilburg University

Journal of Combinatorial Optimization, 2018, vol. 35, issue 3, No 6, 754-777

Abstract: Abstract The quadratic shortest path problem (QSPP) is the problem of finding a path with prespecified start vertex s and end vertex t in a digraph such that the sum of weights of arcs and the sum of interaction costs over all pairs of arcs on the path is minimized. We first consider a variant of the QSPP known as the adjacent QSPP. It was recently proven that the adjacent QSPP on cyclic digraphs cannot be approximated unless $$\hbox {P}=\hbox {NP}$$ P = NP . Here, we give a simple proof for the same result. We also show that if the quadratic cost matrix is a symmetric weak sum matrix and all s–t paths have the same length, then an optimal solution for the QSPP can be obtained by solving the corresponding instance of the shortest path problem. Similarly, it is shown that the QSPP with a symmetric product cost matrix is solvable in polynomial time. Further, we provide sufficient and necessary conditions for a QSPP instance on a complete symmetric digraph with four vertices to be linearizable. We also characterize linearizable QSPP instances on complete symmetric digraphs with more than four vertices. Finally, we derive an algorithm that examines whether a QSPP instance on the directed grid graph $$G_{pq}$$ G pq ( $$p,q\ge 2$$ p , q ≥ 2 ) is linearizable. The complexity of this algorithm is $${\mathcal {O}(p^{3}q^{2}+p^{2}q^{3})}$$ O ( p 3 q 2 + p 2 q 3 ) .

Keywords: Quadratic shortest path problem; Complexity; Directed graph; Linearizable instances (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-017-0219-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:35:y:2018:i:3:d:10.1007_s10878-017-0219-9

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-017-0219-9

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().