Piotr Sankowski

We consider generalized versions of well-studied problems in parameterized complexity and exact exponential time algorithms. The generalizations are obtained by introducing a relaxation parameter, which relaxes the constraints on feasible solutions. For example, one can generalize Hamiltonian path to the problem of finding a spanning tree where all degrees are at most some integer d. Or one can generalize k-Path to the task of finding a walk of length k where any vertex is visited at most r times. This problem was first considered by Abasi et. al who showed a randomized algorithm where the running time improves with the parameter r. We derandomize their algorithm. We also obtain an algorithm for Bounded-Degree Spanning Tree, where the running time improves with the degree bound d, improving an algorithm of Fomin et al. with running time 2^{n+o(n)} for any d.On the way to obtain our results we generalize the notion of representative sets to multisets, and give an efficient algorithm to compute such representative sets. Both the generalization of representative sets to multisets and the algorithm to compute them may be of independent interest.Joint work with Daniel Lokshtanov and Michał Pilipcuzk