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

Institut für Diskrete Mathematik (5050)

Publikation: Beitrag in Buch/Bericht/Konferenzband › Beitrag in einem Konferenzband › Begutachtung

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.

Originalsprache	englisch
Titel	Graph-Theoretic Concepts in Computer Science
Untertitel	WG 2021
Redakteure/-innen	Łukasz Kowalik, Michał Pilipczuk, Pawel Rzążewski
Herausgeber (Verlag)	Springer
Seiten	245-256
Seitenumfang	12
ISBN (Print)	9783030868376
DOIs	https://doi.org/10.1007/978-3-030-86838-3_19
Publikationsstatus	Veröffentlicht - 20 Sept. 2021
Veranstaltung	47th International Workshop on Graph-Theoretic Concepts in Computer Science: WG 2021 - Warsaw, Polen Dauer: 23 Juni 2021 → 25 Juni 2021

Publikationsreihe

Name	Springer Lecture Notes in Computer Science
Herausgeber (Verlag)	Springer
Band	12911

Konferenz

Konferenz	47th International Workshop on Graph-Theoretic Concepts in Computer Science
Kurztitel	WG 2021
Land/Gebiet	Polen
Ort	Warsaw
Zeitraum	23/06/21 → 25/06/21

ASJC Scopus subject areas

Mathematik (insg.)

Fields of Expertise

Information, Communication & Computing

Treatment code (Nähere Zuordnung)

Basic - Fundamental (Grundlagenforschung)

Zugriff auf Dokument

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

Andere Dateien und Links

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

DK Diskrete Mathematik
Ebner, O., Lehner, F., Greinecker, F., Burkard, R., Wallner, J., Elsholtz, C., Woess, W., Raseta, M., Bazarova, A., Krenn, D., Lehner, F., Kang, M., Tichy, R., Sava-Huss, E., Klinz, B., Heuberger, C., Grabner, P., Barroero, F., Cuno, J., Kreso, D., Berkes, I. & Kerber, M.
1/05/10 → 30/06/24
Projekt: Forschungsprojekt

Dieses zitieren

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 (Hrsg.), Graph-Theoretic Concepts in Computer Science: WG 2021 (S. 245-256). (Springer Lecture Notes in Computer Science; Band 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. Hrsg. / Łukasz Kowalik; Michał Pilipczuk; Pawel Rzążewski. Springer, 2021. S. 245-256 (Springer Lecture Notes in Computer Science; Band 12911).

Publikation: Beitrag in Buch/Bericht/Konferenzband › Beitrag in einem Konferenzband › Begutachtung

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 (Hrsg.), Graph-Theoretic Concepts in Computer Science: WG 2021. Springer Lecture Notes in Computer Science, Bd. 12911, Springer, S. 245-256, 47th International Workshop on Graph-Theoretic Concepts in Computer Science, Warsaw, Polen, 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

Publikationsreihe

Konferenz

ASJC Scopus subject areas

Fields of Expertise

Treatment code (Nähere Zuordnung)

Zugriff auf Dokument

Andere Dateien und Links

Fingerprint

Projekte

DK Diskrete Mathematik

Dieses zitieren