Linearizable Special Cases of the Quadratic Shortest Path Problem

Eranda Dragoti-Cela; Bettina Klinz; Stefan Lendl; James B. Orlin; Gerhard Woeginger; Lasse Wulf

doi:10.1007/978-3-030-86838-3_19

Linearizable Special Cases of the Quadratic Shortest Path Problem

Eranda Dragoti-Cela, Bettina Klinz, Stefan Lendl, James B. Orlin, Gerhard Woeginger, Lasse Wulf

Institute of Discrete Mathematics (5050)

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › peer-review

Abstract

The quadratic shortest path problem (QSPP) in a directed graph asks for a directed path from a given source vertex to a given sink vertex, so that the sum of the interaction costs over all pairs of arcs on the path is minimized. We consider special cases of the QSPP that are linearizable as a shortest path problem in the sense of Bookhold. If the QSPP on a directed graph is linearizable under all possible choices of the arc interaction costs, the graph is called universally linearizable.

We provide various combinatorial characterizations of universally linearizable graphs that are centered around the structure of source-to-sink paths and around certain forbidden subgraphs. Our characterizations lead to fast and simple recognition algorithms for universally linearizable graphs. Furthermore, we establish the intractability of deciding whether a concrete instance of the QSPP (with a given graph and given arc interaction costs) is linearizable.

Original language	English
Title of host publication	Graph-Theoretic Concepts in Computer Science
Subtitle of host publication	WG 2021
Editors	Łukasz Kowalik, Michał Pilipczuk, Pawel Rzążewski
Publisher	Springer
Pages	245-256
Number of pages	12
ISBN (Print)	9783030868376
DOIs	https://doi.org/10.1007/978-3-030-86838-3_19
Publication status	Published - 20 Sept 2021
Event	47th International Workshop on Graph-Theoretic Concepts in Computer Science: WG 2021 - Warsaw, Poland Duration: 23 Jun 2021 → 25 Jun 2021

Publication series

Name	Springer Lecture Notes in Computer Science
Publisher	Springer
Volume	12911

Conference

Conference	47th International Workshop on Graph-Theoretic Concepts in Computer Science
Abbreviated title	WG 2021
Country/Territory	Poland
City	Warsaw
Period	23/06/21 → 25/06/21

Keywords

quadratic shortest path problem
linearizable instances
Computational complexity
special cases

ASJC Scopus subject areas

General Mathematics

Fields of Expertise

Information, Communication & Computing

Treatment code (Nähere Zuordnung)

Basic - Fundamental (Grundlagenforschung)

Access to Document

10.1007/978-3-030-86838-3_19

Cite this

Dragoti-Cela, E., Klinz, B., Lendl, S., Orlin, J. B., Woeginger, G., & Wulf, L. (2021). Linearizable Special Cases of the Quadratic Shortest Path Problem. In Ł. Kowalik, M. Pilipczuk, & P. Rzążewski (Eds.), Graph-Theoretic Concepts in Computer Science: WG 2021 (pp. 245-256). (Springer Lecture Notes in Computer Science; Vol. 12911). Springer. https://doi.org/10.1007/978-3-030-86838-3_19

Linearizable Special Cases of the Quadratic Shortest Path Problem. / Dragoti-Cela, Eranda ; Klinz, Bettina ; Lendl, Stefan et al.
Graph-Theoretic Concepts in Computer Science: WG 2021. ed. / Łukasz Kowalik; Michał Pilipczuk; Pawel Rzążewski. Springer, 2021. p. 245-256 (Springer Lecture Notes in Computer Science; Vol. 12911).

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › peer-review

Dragoti-Cela, E , Klinz, B , Lendl, S, Orlin, JB, Woeginger, G & Wulf, L 2021, Linearizable Special Cases of the Quadratic Shortest Path Problem. in Ł Kowalik, M Pilipczuk & P Rzążewski (eds), Graph-Theoretic Concepts in Computer Science: WG 2021. Springer Lecture Notes in Computer Science, vol. 12911, Springer, pp. 245-256, 47th International Workshop on Graph-Theoretic Concepts in Computer Science, Warsaw, Poland, 23/06/21. https://doi.org/10.1007/978-3-030-86838-3_19

@inproceedings{1f07aecec0c94adda9bff8e4022853e8,

title = "Linearizable Special Cases of the Quadratic Shortest Path Problem",

abstract = "The quadratic shortest path problem (QSPP) in a directed graph asks for a directed path from a given source vertex to a given sink vertex, so that the sum of the interaction costs over all pairs of arcs on the path is minimized. We consider special cases of the QSPP that are linearizable as a shortest path problem in the sense of Bookhold. If the QSPP on a directed graph is linearizable under all possible choices of the arc interaction costs, the graph is called universally linearizable.We provide various combinatorial characterizations of universally linearizable graphs that are centered around the structure of source-to-sink paths and around certain forbidden subgraphs. Our characterizations lead to fast and simple recognition algorithms for universally linearizable graphs. Furthermore, we establish the intractability of deciding whether a concrete instance of the QSPP (with a given graph and given arc interaction costs) is linearizable.",

keywords = "quadratic shortest path problem, linearizable instances, Computational complexity, special cases",

author = "Eranda Dragoti-Cela and Bettina Klinz and Stefan Lendl and Orlin, {James B.} and Gerhard Woeginger and Lasse Wulf",

year = "2021",

month = sep,

day = "20",

doi = "10.1007/978-3-030-86838-3_19",

language = "English",

isbn = "9783030868376",

series = "Springer Lecture Notes in Computer Science",

publisher = "Springer",

pages = "245--256",

editor = "Kowalik, {{\L}ukasz } and Pilipczuk, {Micha{\l} } and Rz{\c a}{\.z}ewski, {Pawel }",

booktitle = "Graph-Theoretic Concepts in Computer Science",

note = "47th International Workshop on Graph-Theoretic Concepts in Computer Science : WG 2021, WG 2021 ; Conference date: 23-06-2021 Through 25-06-2021",

}

TY - GEN

T1 - Linearizable Special Cases of the Quadratic Shortest Path Problem

AU - Dragoti-Cela, Eranda

AU - Klinz, Bettina

AU - Lendl, Stefan

AU - Orlin, James B.

AU - Woeginger, Gerhard

AU - Wulf, Lasse

PY - 2021/9/20

Y1 - 2021/9/20

N2 - The quadratic shortest path problem (QSPP) in a directed graph asks for a directed path from a given source vertex to a given sink vertex, so that the sum of the interaction costs over all pairs of arcs on the path is minimized. We consider special cases of the QSPP that are linearizable as a shortest path problem in the sense of Bookhold. If the QSPP on a directed graph is linearizable under all possible choices of the arc interaction costs, the graph is called universally linearizable.We provide various combinatorial characterizations of universally linearizable graphs that are centered around the structure of source-to-sink paths and around certain forbidden subgraphs. Our characterizations lead to fast and simple recognition algorithms for universally linearizable graphs. Furthermore, we establish the intractability of deciding whether a concrete instance of the QSPP (with a given graph and given arc interaction costs) is linearizable.

AB - The quadratic shortest path problem (QSPP) in a directed graph asks for a directed path from a given source vertex to a given sink vertex, so that the sum of the interaction costs over all pairs of arcs on the path is minimized. We consider special cases of the QSPP that are linearizable as a shortest path problem in the sense of Bookhold. If the QSPP on a directed graph is linearizable under all possible choices of the arc interaction costs, the graph is called universally linearizable.We provide various combinatorial characterizations of universally linearizable graphs that are centered around the structure of source-to-sink paths and around certain forbidden subgraphs. Our characterizations lead to fast and simple recognition algorithms for universally linearizable graphs. Furthermore, we establish the intractability of deciding whether a concrete instance of the QSPP (with a given graph and given arc interaction costs) is linearizable.

KW - quadratic shortest path problem

KW - linearizable instances

KW - Computational complexity

KW - special cases

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

U2 - 10.1007/978-3-030-86838-3_19

DO - 10.1007/978-3-030-86838-3_19

M3 - Conference paper

SN - 9783030868376

T3 - Springer Lecture Notes in Computer Science

SP - 245

EP - 256

BT - Graph-Theoretic Concepts in Computer Science

A2 - Kowalik, Łukasz

A2 - Pilipczuk, Michał

A2 - Rzążewski, Pawel

PB - Springer

T2 - 47th International Workshop on Graph-Theoretic Concepts in Computer Science

Y2 - 23 June 2021 through 25 June 2021

ER -

Linearizable Special Cases of the Quadratic Shortest Path Problem

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Fields of Expertise

Treatment code (Nähere Zuordnung)

Access to Document

Other files and links

Fingerprint

Doctoral Program: Discrete Mathematics

Cite this

Linearizable Special Cases of the Quadratic Shortest Path Problem

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Fields of Expertise

Treatment code (Nähere Zuordnung)

Access to Document

Other files and links

Fingerprint

Projects

Doctoral Program: Discrete Mathematics

Cite this