A Boundary Class for the k-Path Partition Problem
Presented by Mr. Nicholas KORPELAINEN
Type: Oral presentation
Track: Algorithmic Graph Theory
The k-path partition problem, i.e. finding the minimum number of paths of length at most k that partition a graph, is an algorithmic graph problem with many real-life applications, such as in route design or communication networks. We will discuss the complexity status of this problem for various hereditary graph classes. The concept of 'boundary classes' will be introduced -- these are defined as a workaround to the problem of defining a 'minimal' class within a family of (possibly infinite) classes. We find the first boundary class for the family of graph classes for which the k-path partition problem is NP-hard.