[Proof Complexity] MIAO seminar Mon Nov 7 at 14:00 CET with Thore Husfeldt: The shortest even cycle problem is tractable

[Jakob Nordström]

Dear all,

On Monday November 7 at 14:00 Thore Husfeldt from the IT University of Copenhagen and Lund University will give a seminar on a delightfully simple problem (or perhaps rather deceptively simple): How can one find a shortest cycle in a directed graph with the added condition that the length of this cycle should be even? To find the answer, Thore will lead us on an exciting excursion into algebra, randomness, and other topics (but with the promise that no prerequisites are needed other than an open and curious mind). The title of the seminar is "The shortest even cycle problem is tractable", and you find the abstract at the bottom of this message.

We will run this as a hybrid seminar at Lund University. Local participants are welcome to seminar room E:2116 at Ole Römers väg 3. Other participants are welcome to join virtually at https://lu-se.zoom.us/j/61925271827. Please feel free to share this information with colleagues who you think might be interested. We are also hoping to record the seminar and post on the MIAO Research YouTube channel https://youtube.com/@MIAOresearch for people who would like to hear the talk but cannot attend.

Most of our seminars consist of two parts: first a 50-55-minute regular talk, and then after a break a ca-1-hour in-depth technical presentation with (hopefully) a lot of interaction. The intention is that the first part of the seminar will give all listeners a self-contained overview of some exciting research results, and after the break people who have the time and interest will get an opportunity to really get into the technical details. (However, for those who feel that the first part was enough, it is perfectly fine to just discretely drop out during the break. No questions asked; no excuses needed.)

More information about upcoming MIAO seminars can be found at http://www.jakobnordstrom.se/miao-seminars/. If you do not wish to receive these announcements, or receive several copies of them, please send a message to jn at di.ku.dk.

Best regards,
Jakob Nordström

**********

Monday Nov 7 at 14:00 in seminar room E:2116, Ole Römers väg 3, Lund University, and on Zoom
The shortest even cycle problem is tractable
(Thore Husfeldt, IT University of Copenhagen and Lund University)

Given a directed graph as input, we show how to efficiently find a shortest (directed, simple) cycle on an even number of vertices. As far as we know, no polynomial-time algorithm was previously known for this problem. In fact, finding any even cycle in a directed graph in polynomial time was open for more than two decades until Robertson, Seymour, and Thomas (Ann. of Math. (2) 1999) and, independently, McCuaig (Electron. J. Combin. 2004; announced jointly at STOC 1997) gave an efficiently testable structural characterisation of even-cycle-free directed graphs.

Almost no knowledge of graph algorithms is necessary to appreciate the result. The second hour will be more about algebra and combinatorics than algorithms — polynomials, matrix functions, and generating functions.

This is joint work with Andreas Björklund (Lund) and Petteri Kaski (Helsinki).


Jakob Nordström, Professor
University of Copenhagen and Lund University
Phone: +46 70 742 21 98
http://www.jakobnordstrom.se