#
Shortest cycle through specified elements

##
Paweł Pszona

I will present a randomized algorithm that finds a shortest simple cycle
through a given set of $k$ marked elements (vertices and/or edges) in an
$n$-vertex
undirected graph, or determines that such cycle does not exist.
The algorithm works in time $2^{k}n^{O(1)}$, with one-sided errors with
exponentially small probability in $n$.

(From a
SODA 2012 paper by Andreas Björklund, Thore Husfeldt and
Nina Taslaman.)