A linear time algorithm for linearizing quadratic and higher-order shortest path problems

Eranda Çela; Bettina Klinz; Stefan Lendl; Gerhard J. Woeginger; Lasse Wulf

A linear time algorithm for linearizing quadratic and higher-order shortest path problems

Eranda Çela, Bettina Klinz, Stefan Lendl, Gerhard J. Woeginger, Lasse Wulf

Institute of Discrete Mathematics (5050)

Research output: Working paper › Preprint

Abstract

An instance of the NP-hard Quadratic Shortest Path Problem (QSPP) is called linearizable iff it is equivalent to an instance of the classic Shortest Path Problem (SPP) on the same input digraph. The linearization problem for the QSPP (LinQSPP) decides whether a given QSPP instance is linearizable and determines the corresponding SPP instance in the positive case. We provide a novel linear time algorithm for the LinQSPP on acyclic digraphs which runs considerably faster than the previously best algorithm. The algorithm is based on a new insight revealing that the linearizability of the QSPP for acyclic digraphs can be seen as a local property. Our approach extends to the more general higher-order shortest path problem.

Original language	English
Number of pages	14
Publication status	Published - 1 Mar 2023

Keywords

cs.DS
F.2.2; G.2.2

ASJC Scopus subject areas

Theoretical Computer Science

Fields of Expertise

Information, Communication & Computing

Access to Document

2303.00569v1Submitted manuscript, 209 KBLicence: Other

1 Conference paper

A linear time algorithm for linearizing quadratic and higher-order shortest path problems
Çela , E. ., Klinz, B., Lendl, S., Woeginger, G. J. & Wulf, L., 2023, Integer Programming and Combinatorial Optimization - 24th International Conference, IPCO 2023, Proceedings. Del Pia, A. & Kaibel, V. (eds.). Cham: Springer, p. 466-479 14 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 13904 LNCS).
Research output: Chapter in Book/Report/Conference proceeding › Conference paper › peer-review

Cite this

@techreport{960068626d124977a923b286760782bf,

title = "A linear time algorithm for linearizing quadratic and higher-order shortest path problems",

abstract = "An instance of the NP-hard Quadratic Shortest Path Problem (QSPP) is called linearizable iff it is equivalent to an instance of the classic Shortest Path Problem (SPP) on the same input digraph. The linearization problem for the QSPP (LinQSPP) decides whether a given QSPP instance is linearizable and determines the corresponding SPP instance in the positive case. We provide a novel linear time algorithm for the LinQSPP on acyclic digraphs which runs considerably faster than the previously best algorithm. The algorithm is based on a new insight revealing that the linearizability of the QSPP for acyclic digraphs can be seen as a local property. Our approach extends to the more general higher-order shortest path problem.",

keywords = "cs.DS, F.2.2; G.2.2",

author = "Eranda {\c C}ela and Bettina Klinz and Stefan Lendl and Woeginger, {Gerhard J.} and Lasse Wulf",

year = "2023",

month = mar,

day = "1",

language = "English",

type = "WorkingPaper",

}

TY - UNPB

T1 - A linear time algorithm for linearizing quadratic and higher-order shortest path problems

AU - Çela, Eranda

AU - Klinz, Bettina

AU - Lendl, Stefan

AU - Woeginger, Gerhard J.

AU - Wulf, Lasse

PY - 2023/3/1

Y1 - 2023/3/1

N2 - An instance of the NP-hard Quadratic Shortest Path Problem (QSPP) is called linearizable iff it is equivalent to an instance of the classic Shortest Path Problem (SPP) on the same input digraph. The linearization problem for the QSPP (LinQSPP) decides whether a given QSPP instance is linearizable and determines the corresponding SPP instance in the positive case. We provide a novel linear time algorithm for the LinQSPP on acyclic digraphs which runs considerably faster than the previously best algorithm. The algorithm is based on a new insight revealing that the linearizability of the QSPP for acyclic digraphs can be seen as a local property. Our approach extends to the more general higher-order shortest path problem.

AB - An instance of the NP-hard Quadratic Shortest Path Problem (QSPP) is called linearizable iff it is equivalent to an instance of the classic Shortest Path Problem (SPP) on the same input digraph. The linearization problem for the QSPP (LinQSPP) decides whether a given QSPP instance is linearizable and determines the corresponding SPP instance in the positive case. We provide a novel linear time algorithm for the LinQSPP on acyclic digraphs which runs considerably faster than the previously best algorithm. The algorithm is based on a new insight revealing that the linearizability of the QSPP for acyclic digraphs can be seen as a local property. Our approach extends to the more general higher-order shortest path problem.

KW - cs.DS

KW - F.2.2; G.2.2

M3 - Preprint

BT - A linear time algorithm for linearizing quadratic and higher-order shortest path problems

ER -

A linear time algorithm for linearizing quadratic and higher-order shortest path problems

Abstract

Keywords

ASJC Scopus subject areas

Fields of Expertise

Access to Document

Fingerprint

Research output

A linear time algorithm for linearizing quadratic and higher-order shortest path problems

Cite this