Special cases of the quadratic shortest path problem

Research output: Contribution to journalArticleScientificpeer-review

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 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 Gpq ( p,q≥2) is linearizable. The complexity of this algorithm is O(p3q2+p2q3).
Original languageEnglish
Pages (from-to)754-777
JournalJournal of Combinatorial Optimization
Volume35
Issue number3
DOIs
Publication statusPublished - Apr 2018

Fingerprint

Shortest Path Problem
Costs
Digraph
Polynomials
Path
Arc of a curve
Adjacent
Grid Graph
Symmetric Product
Vertex of a graph
Directed Graph
Polynomial time
Optimal Solution
Necessary Conditions

Keywords

  • quadratic shortest path problem
  • complexity
  • directed graph
  • linearizable instances

Cite this

@article{b01dab75c9e94e7abac7be8726417239,
title = "Special cases of the quadratic shortest path problem",
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 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 Gpq ( p,q≥2) is linearizable. The complexity of this algorithm is O(p3q2+p2q3).",
keywords = "quadratic shortest path problem, complexity, directed graph, linearizable instances",
author = "Renata Sotirov and Hao Hu",
year = "2018",
month = "4",
doi = "10.1007{\%}2Fs10878-017-0219-9",
language = "English",
volume = "35",
pages = "754--777",
journal = "Journal of Combinatorial Optimization",
issn = "1382-6905",
publisher = "Springer Netherlands",
number = "3",

}

Special cases of the quadratic shortest path problem. / Sotirov, Renata; Hu, Hao.

In: Journal of Combinatorial Optimization, Vol. 35, No. 3, 04.2018, p. 754-777.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - Special cases of the quadratic shortest path problem

AU - Sotirov, Renata

AU - Hu, Hao

PY - 2018/4

Y1 - 2018/4

N2 - 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 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 Gpq ( p,q≥2) is linearizable. The complexity of this algorithm is O(p3q2+p2q3).

AB - 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 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 Gpq ( p,q≥2) is linearizable. The complexity of this algorithm is O(p3q2+p2q3).

KW - quadratic shortest path problem

KW - complexity

KW - directed graph

KW - linearizable instances

U2 - 10.1007%2Fs10878-017-0219-9

DO - 10.1007%2Fs10878-017-0219-9

M3 - Article

VL - 35

SP - 754

EP - 777

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

SN - 1382-6905

IS - 3

ER -