Material Detail

This video was recorded at ALGO Annual Meeting 2012, Ljubljana. We give a historical account of the parametrized results for the k-Path problem: given a graph G and a positive integer k, is there a simple path in G of length k. Throughout the years several ingenious approaches have been used, steadily decreasing the run time bound. Moreover, the techniques used have often found lots of other applications. We will revisit some of the old results, as well as cover the state-of-the-art techniques based on algebraic sieves. We will also briefly talk about what is known about counting k-paths.

Disciplines:

• Science and Technology  / Computer Science