CS Forum: Nicholas Korpelainen, University of Derby

CS department's public guest lecture on 'A boundary property for the algorithmic problem of partitioning a graph into paths of length at most k'. The lecture is open to everyone free-of-charge.

Dr. Nicholas Korpelainen
University of Derby

Host: Christopher Purcell
Time: 14:15 (coffee at 14:00)
Venue: T5, CS building

A boundary property for the algorithmic problem of partitioning a graph into paths of length at most k

Abstract:

The k-path partition problem (k-PP) asks for the minimum number of paths, each with at most k vertices, into which the vertices of a graph can be partitioned. This problem has applications in communication networks and vehicle routing. The problem is NP-complete even for some severely restricted hereditary graph classes (sets of graphs closed under vertex deletions). For example, the problem is NP-complete even when restricting to bipartite graphs of maximum degree at most three. Furthermore, one can find infinitely many distinct nested hereditary graph classes for which the problem remains NP-complete. Call the intersection of an infinite sequence of such hereditary graph classes a limit property for the problem. We are interested in minimal limit properties for the problem; these are known as boundary properties. The usefulness of the notion stems from the following lemma: for graph classes defined by forbidding finitely many induced subgraphs, the inclusion of a boundary property is a necessary and sufficient condition for NP-completeness. We generalise the notion, originally due to Alekseev, to arbitrary ideals of partially ordered sets (with exciting potential applications for other structures than just graphs). Then we present the first boundary class for k-PP and highlight some remaining open problems regarding the computational complexity of k-PP and other closely related problems (some of these interrelations have only been discovered in the past year).

Bio:

Nicholas is a Lecturer in Mathematics at the University of Derby, with research interests in discrete mathematics. He studied Mathematics at Trinity College, University of Cambridge, gaining BA, MA and MMath degrees. His PhD thesis, from the University of Warwick, involved work at the crossroads of applicable and theoretical mathematics (with implications for theoretical computer science). Nicholas worked as Research Associate in Combinatorics at The Open University, Milton Keynes (2012-2014) for an EPSRC grant that involved combining ideas from permutation theory and graph theory to help develop both disciplines. He will co-chair a conference on 'Theoretical and Computational Discrete Mathematics' at Derby in 2018 -- he also co-organised the previous iteration in 2016. Nicholas is interested in promoting mathematical beauty to the wider audience by organising regular problem-solving and board gaming events and by giving talks on the more aesthetic and recreational side of mathematics (for example at the MathsJam annual conference).