BARC/EADS Talk by Cornelius Brand
A unified algebraic approach to the longest path problem
Given a directed graph and an integer k, it is a classic NP-hard problem to determine the existence of a simple path of length k in the graph. In this talk, I want to demonstrate that on directed graphs, the two randomized state-of-the-art algorithms due to Williams and Björklund et al. are -- in a precise sense -- actually one and the same, and both arise in a particularly natural way as special cases when evaluating the so-called walk polynomial of a graph over a Grassmann-Algebra. They run in time 2^k * poly(n). To justify the considerably more abstract perspective, we will see that the technique lends itself to a simple derandomization in time 4^k * poly(n). Despite not matching the record bound due to Zehavi, it might be of independent interest, since it does not rely on any of the heavy combinatorial machinery which lead to previous slower deterministic algorithms. What is more, it allows to solve the unambiguous version of the problem (i.e., the input graph is promised to have either no or exactly one path of length k) in deterministic time 2^k * poly(n).
Joint work with Holger Dell and Thore Husfeldt.
Cornelius Brand is PhD student at Saarland University, Germany. His research interest is within lower bounds under #ETH, ETH and SETH, parameterized complexity, computing coefficients in representation theory (such as Kostka numbers and Littlewood-Richardson coefficients) and polynomial system solving.