Representative sets for multisets.
Ariel Gabizon, Daniel Lokshtanov, Michał Pilipczuk · arXiv (Cornell University) · 2014
The notion of a $q$-representative set for a family of subsets has recently proven to be very useful in the design of parameterized and exact algorithms. We generalize this notion to families of $\mathit{multisets}$. We also give an efficient way to find a representative set for a family of multisets. As an application we give a deterministic algorithm for minimal weight r-SIMPLE k-PATH running in time $O^*(r^{O(k/r)})$ for $1<r\leq k$. This extends a result of Abasi et. al [ABGH14] that gave a \emph{randomized} algorithm of similar running time for the non-weighted case. We derive other algorithms for problems that can be viewed as augmenting a parameterized problem with a `relaxation' parameter. A corollary of our construction is an improved explicit construction of $\mathit{lopsided\; universal\; sets}$ [FLS14] for a certain range of parameters.