A shortcut to the shortest even cycle

Abstract

The problem of finding even cycles efficiently in a directed graph can be rewritten to a problem of finding the permanent and determinant of the graph’s adjacency matrix. Although this has been known for a long time, it did not solve the shortest even cycle problem, as mathematicians lacked an efficient method to compute the permanent.
In 1979 Valiant found out that in some specific cases, when one works modulo a power of 2, the permanent could be computed efficiently. Although this did not directly lead to a breakthrough in finding even cycles, it laid the groundwork for Björklund, Husfeldt and Kaski to solve the problem of finding the shortest even cycle. Instead of working with the integers modulo 2, Björklund, Husfeldt and Kaski used a polynomial quotient ring E4d , which is an extension of some polynomial quotient ring F2d . The polynomial quotient ring E4d , it turns out, benefits from having a characteristic of four and relies on F2d being a field. Surprisingly, these two properties are exactly what is needed to efficiently compute both the permanent and determinant.
The aim of this thesis is to give the reader a better understanding of the polynomial quotient rings F2d and E4d that are used by Björklund, Husfeldt and Kaski in. These structures are then used to explain the part of their algorithm that computes the determinant of matrices with entries in E4d . The reader is given a deeper insight into the algorithm by comparing it to the standard algorithm for computing the determinant learned in most linear algebra classes. By using the polynomial rings and algorithm for the determinant a Python script is written. This script can perform calculations within E4d and compute the determinant for a matrix with entries in E4d . Finally, the difference between computing the permanent and the determinant will be briefly explained.