\(k\)-colour partitions of acyclic tournaments (Q1773195)

The authors consider a weighted digraph \(G_k\) with vertex set \(V=\{0,1,\dots, n+1\}\) and \(k\) coloured copies of the edge set \(E_m=\{(i,j)\in V\times V\mid i<j\}\) (\(1\leq m \leq k\)). The different copies of each edge can have different weights (costs), which are nonnegative and can be infinite. A \(k\)-colour partition (\(k\)-CP) of \(\{1,2,\dots, n\}\) is defined to be a set of \(k\) paths from 0 to \(n+1\), each path consisting of arcs from a single \(E_m\), one path for each \(m\), with each of the nodes 1 to \(n\) in exactly one of the paths. The focus of the paper is on minimum cost \(k\)-CPs. The authors show how to find a minimum cost \(k\)-CP, in time \({\mathcal O}(k^2n^{2k})\), by applying a shortest-path algorithm to an associated graph. They show that the problem of deciding whether a spanning subgraph of \(G_k\) includes a \(k\)-CP is NP-complete. They give a polyhedral description of the problem, that is, a half-space description for the convex hull of the incidence vectors of \(k\)-CPs.