Oliver Bachtler

• Let \(G\) be a graph whose edges are partially coloured, that is, some are assigned a colour whilst others remain uncoloured, and let \(\mathcal{G}\) be a class of graphs. A \(\mathcal{G}\)-decomposition of \(G\) is a collection \(D=\{G_1,\ldots,G_k\}\) of edge-disjoint subgraphs of \(G\) that are in \(\mathcal{G}\), contain all coloured edges, and satisfy that any colour is completely contained in a single subgraph. The problem of determining whether \(G\) has such a decomposition is called \(\mathcal{G}\)-\(\mathtt{Dec}\) and finding one with at least a specified amount of elements is denoted by \(\mathtt{Max}\)-\(\mathcal{G}\)-\(\mathtt{Dec}\). This thesis deals with the complexity of these problems for specific choices of \(\mathcal{G}\), originally motivated by a problem in train scheduling. The graph classes considered are simple cycles, cycles, paths, and trees and we look at both directed and undirected graphs. As one might expect, the general versions are all NP-complete, which is why we restrict the amount of colours or the amount of edges of each colour to find out at precisely what point the problems actually become hard. For the maximisation versions we impose additional requirements on the underlying graph, assuming it is Eulerian for the first two and a tree for the last two subgraph types. Furthermore, we explicitly study all decompositions on series-parallel graphs. The results we obtain differ for each subgraph type, but overall the directed case is significantly harder to solve than the undirected one, requiring only very few coloured edges, usually two to four, to become NP-hard. In comparison, for undirected graphs, we did not find a single instance with a constant amount of coloured edges that was hard. Thanks to their nice structure, series-parallel graphs yield linear time algorithms for all of the graph classes we regarded as long as the amount of colours is bounded by a constant. Removing this requirement usually makes the problems hard.