Miniworkshop on 12.11.2015

Onlogo FNP 12.11.2015 as a part of our Foundation for Polish Science  Algorithmic Miniworkshop series we will host Ariel Gabizon from Technion. He will give a talk on his recent result on “Fast Algorithms for Parameterized Problems with Relaxed Disjointness Constraints”. The abstract is given below.

We plan to have a group discussion and joint lunch after his talk.


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