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

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

doi:10.1007/978-3-031-32726-1_33

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: Chapter in Book/Report/Conference proceeding › Conference paper › peer-review

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
Title of host publication	Integer Programming and Combinatorial Optimization - 24th International Conference, IPCO 2023, Proceedings
Editors	Alberto Del Pia, Volker Kaibel
Place of Publication	Cham
Publisher	Springer
Pages	466-479
Number of pages	14
ISBN (Electronic)	978-3-031-32726-1
ISBN (Print)	978-3-031-32725-4
DOIs	https://doi.org/10.1007/978-3-031-32726-1_33
Publication status	Published - 2023
Event	24th Conference on Integer Programming and Combinatorial Optimization: IPCO 2023 - University of Wisconsin-Madison, Madison, United States Duration: 21 Jun 2023 → 23 Jun 2023

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	13904 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	24th Conference on Integer Programming and Combinatorial Optimization
Abbreviated title	IPCO 2023
Country/Territory	United States
City	Madison
Period	21/06/23 → 23/06/23

Keywords

higher-order shortest path problem
linearization
quadratic shortest path problem

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Fields of Expertise

Information, Communication & Computing

Access to Document

10.1007/978-3-031-32726-1_33

Cite this

Çela , E. ., Klinz, B., Lendl, S., Woeginger, G. J., & Wulf, L. (2023). A linear time algorithm for linearizing quadratic and higher-order shortest path problems. In A. Del Pia, & V. Kaibel (Eds.), Integer Programming and Combinatorial Optimization - 24th International Conference, IPCO 2023, Proceedings (pp. 466-479). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13904 LNCS). Springer. https://doi.org/10.1007/978-3-031-32726-1_33

A linear time algorithm for linearizing quadratic and higher-order shortest path problems. / Çela , Eranda ; Klinz, Bettina ; Lendl, Stefan et al.
Integer Programming and Combinatorial Optimization - 24th International Conference, IPCO 2023, Proceedings. ed. / Alberto Del Pia; Volker Kaibel. Cham: Springer, 2023. p. 466-479 (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

Çela , E , Klinz, B , Lendl, S, Woeginger, GJ & Wulf, L 2023, A linear time algorithm for linearizing quadratic and higher-order shortest path problems. in A Del Pia & V Kaibel (eds), Integer Programming and Combinatorial Optimization - 24th International Conference, IPCO 2023, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13904 LNCS, Springer, Cham, pp. 466-479, 24th Conference on Integer Programming and Combinatorial Optimization, Madison, Wisconsin, United States, 21/06/23. https://doi.org/10.1007/978-3-031-32726-1_33

Çela E , Klinz B , Lendl S, Woeginger GJ, Wulf L. A linear time algorithm for linearizing quadratic and higher-order shortest path problems. In Del Pia A, Kaibel V, editors, Integer Programming and Combinatorial Optimization - 24th International Conference, IPCO 2023, Proceedings. Cham: Springer. 2023. p. 466-479. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-32726-1_33

Çela , Eranda ; Klinz, Bettina ; Lendl, Stefan et al. / A linear time algorithm for linearizing quadratic and higher-order shortest path problems. Integer Programming and Combinatorial Optimization - 24th International Conference, IPCO 2023, Proceedings. editor / Alberto Del Pia ; Volker Kaibel. Cham : Springer, 2023. pp. 466-479 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{36cd64f27fab49dcbbea4ccd18c18cf0,

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 = "higher-order shortest path problem, linearization, quadratic shortest path problem",

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

year = "2023",

doi = "10.1007/978-3-031-32726-1_33",

language = "English",

isbn = "978-3-031-32725-4",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "466--479",

editor = "{Del Pia}, Alberto and Volker Kaibel",

booktitle = "Integer Programming and Combinatorial Optimization - 24th International Conference, IPCO 2023, Proceedings",

note = "24th Conference on Integer Programming and Combinatorial Optimization : IPCO 2023, IPCO 2023 ; Conference date: 21-06-2023 Through 23-06-2023",

}

TY - GEN

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

Y1 - 2023

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 - higher-order shortest path problem

KW - linearization

KW - quadratic shortest path problem

UR - http://www.scopus.com/inward/record.url?scp=85163393004&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-32726-1_33

DO - 10.1007/978-3-031-32726-1_33

M3 - Conference paper

SN - 978-3-031-32725-4

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 466

EP - 479

BT - Integer Programming and Combinatorial Optimization - 24th International Conference, IPCO 2023, Proceedings

A2 - Del Pia, Alberto

A2 - Kaibel, Volker

PB - Springer

CY - Cham

T2 - 24th Conference on Integer Programming and Combinatorial Optimization

Y2 - 21 June 2023 through 23 June 2023

ER -

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

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Fields of Expertise

Access to Document

Other files and links

Fingerprint

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

Cite this