k-Colour partitions of acyclic tournaments

Let G1 be the acyclic tournament with the topological sort 0 < 1 < 2 < < n < n + 1 de ned on node set N [ f0; n + 1g, where N = f1; 2; : : : ; ng. For integer k k dierent colours. A k-colour partition of N is a set of k paths from 0 to n + 1 such that all arcs of each path have the same colour, dierent paths have dierent colours, and every node of N is included in exactly one path. If there are costs associated with the arcs of Gk, the cost of a k-colour partition is the sum of the costs of its arcs. For determining minimum cost k-colour partitions we describe an O(k2n2k) algorithm, and show this is an NP-hard problem. We also study the convex hull of the incidence vectors of k-colour partitions. We derive the dimension, and establish a minimal equality set. For k > 2 we identify a class of facet inducing inequalities. For k = 2 we show that these inequalities turn out to be equations, and that no other facet de ning inequalities exists besides the trivial nonnegativity constraints.2, let Gk be the graph obtained by taking k copies of every arc in G1 and colouring every copy with one of