CS 269S, Spring 2014: Theory Seminar
ICS Building, Room 243, 1pm
May 16, 2013:

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.)