TY - JOUR
T1 - Concatenated k-path covers
AU - Beck, Moritz
AU - Lam, Kam-Yiu
AU - Ng, Joseph Kee Yin
AU - Storandt, Sabine
AU - Zhu, Chun Jiang
PY - 2023/1/31
Y1 - 2023/1/31
N2 - Given a graph G(V,E), a k-Path Cover is defined as a subset C of the nodes V such that every simple path in G consisting of k nodes contains at least one node from C. Similarly, a k-Shortest Path Cover has to contain at least one node of every shortest path in G that consists of k nodes. In this paper, we extend the notion of k-(Shortest) Path Covers such that the objects to be covered don't have to be single paths but can be concatenations of up to p simple (or shortest) paths. For the generalized problem of computing concatenated p | k-Shortest Path Covers, we present theoretical results regarding the VC-dimension of the concatenated path set in dependency of p in undirected as well as directed graphs. By proving a low VC-dimension in both settings, we enable the design of efficient approximation algorithms. Furthermore, we discuss how a pruning algorithm originally developed for k-Path Cover computation can be abstracted and modified in order to also solve concatenated p | k-Path Cover problems. A crucial ingredient for the pruning algorithm to work efficiently is a path concatenation recognition algorithm. We describe general recognition algorithms for simple path concatenations as well as shortest path concatenations. Subsequently, we present more refined results for interesting special cases as piecewise shortest paths, hyperpaths, round tours, and trees. An extensive experimental study on different graph types proves the applicability and efficiency of our approaches. © 2023 Informa UK Limited, trading as Taylor & Francis Group.
AB - Given a graph G(V,E), a k-Path Cover is defined as a subset C of the nodes V such that every simple path in G consisting of k nodes contains at least one node from C. Similarly, a k-Shortest Path Cover has to contain at least one node of every shortest path in G that consists of k nodes. In this paper, we extend the notion of k-(Shortest) Path Covers such that the objects to be covered don't have to be single paths but can be concatenations of up to p simple (or shortest) paths. For the generalized problem of computing concatenated p | k-Shortest Path Covers, we present theoretical results regarding the VC-dimension of the concatenated path set in dependency of p in undirected as well as directed graphs. By proving a low VC-dimension in both settings, we enable the design of efficient approximation algorithms. Furthermore, we discuss how a pruning algorithm originally developed for k-Path Cover computation can be abstracted and modified in order to also solve concatenated p | k-Path Cover problems. A crucial ingredient for the pruning algorithm to work efficiently is a path concatenation recognition algorithm. We describe general recognition algorithms for simple path concatenations as well as shortest path concatenations. Subsequently, we present more refined results for interesting special cases as piecewise shortest paths, hyperpaths, round tours, and trees. An extensive experimental study on different graph types proves the applicability and efficiency of our approaches. © 2023 Informa UK Limited, trading as Taylor & Francis Group.
KW - hitting set
KW - Shortest paths
KW - vc-dimension
UR - http://www.scopus.com/inward/record.url?scp=85148102144&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85148102144&origin=recordpage
U2 - 10.1080/23799927.2023.2173656
DO - 10.1080/23799927.2023.2173656
M3 - 21_Publication in refereed journal
JO - International Journal of Computer Mathematics: Computer Systems Theory
JF - International Journal of Computer Mathematics: Computer Systems Theory
SN - 2379-9927
ER -