Predavatelj: Jan Katrenič (joint work with Ingo Schiermeyer)
Abstract: We consider the Minimum Rainbow Subgraph problem: Given a graph G of n vertices, whose edges are coloured with p colour, find a subgraph of minimum order and with p edges such that each colour occurs exactly once. We present some hardness results, approximation algorithms and parametrized complexity based on the maximum degree of the input graph.
