\(k\)-colour partitions of acyclic tournaments

Paulo Barcia ; J. Orestes Cerdeira

The electronic journal of combinatorics, Tome 12 (2005)

Résumé

Let $G_{1}$ be the acyclic tournament with the topological sort $0 < 1 < 2 < \dots < n < n+1$ defined on node set $N\cup \{0,n+1\}$, where $N=\{1,2,\dots,n\}$. For integer $k\geq 2$, let $G_{k}$ be the graph obtained by taking $k$ copies of every arc in $G_{1}$ and colouring every copy with one of $k$ different 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, different paths have different colours, and every node of $N$ is included in exactly one path. If there are costs associated with the arcs of $G_{k}$, 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(k^{2}n^{2k})$ 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 defining inequalities exists besides the trivial nonnegativity constraints.

Détail

DOI : 10.37236/1902

Classification : 05C20, 90C57
Mots-clés : path partition, minimum cost, NP-complete