## Abstract

Given a directed graph G(V,E), a k-(Shortest) Path Cover is a subset C of the nodes V such that every simple (or shortest) path in G consisting of k nodes contains at least one node from C. In this paper, we extend the notion of k-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 k-(Shortest) Path Covers, we present theoretical results regarding the VC-dimension of the concatenated path set in dependency of p as well as (approximation) algorithms. Subsequently, we study interesting special cases of concatenated k-Path Covers, in particular, covers for piecewise shortest paths, round tours and trees. For those, we show how the pruning algorithm for k-Path Cover computation can be abstracted and modified in order to also solve concatenated k-Path Cover problems. An extensive experimental study on different graph types proves the applicability and efficiency of our approaches.

Original language | English |
---|---|

Title of host publication | 2019 Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments (ALENEX) |

Editors | Stephen Kobourov, Henning Meyerhenke |

Publisher | Society for Industrial and Applied Mathematics (SIAM) |

Pages | 81-91 |

Number of pages | 11 |

DOIs | |

Publication status | Published - 2 Jan 2019 |

Event | 21st Workshop on Algorithm Engineering and Experiments, ALENEX 2019 - San Diego, United States Duration: 7 Jan 2019 → 8 Jan 2019 https://epubs.siam.org/doi/book/10.1137/1.9781611975499 |

### Publication series

Name | Proceedings of the Workshop on Algorithm Engineering and Experiments |
---|---|

ISSN (Print) | 2164-0300 |

### Conference

Conference | 21st Workshop on Algorithm Engineering and Experiments, ALENEX 2019 |
---|---|

Country/Territory | United States |

City | San Diego |

Period | 7/01/19 → 8/01/19 |

Internet address |

## Scopus Subject Areas

- Engineering(all)
- Applied Mathematics