English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Given a directed graph, we show how to efficiently find a shortest (directed,simple) cycle on an even number of vertices. As far as we know, nopolynomial-time algorithm was previously known for this problem. In fact,finding any even cycle in a directed graph in polynomial time was open for morethan two decades until Robertson, Seymour, and Thomas (Ann. of Math. (2) 1999)and, independently, McCuaig (Electron. J. Combin. 2004; announced jointly atSTOC 1997) gave an efficiently testable structural characterisation ofeven-cycle-free directed graphs.  Methodologically, our algorithm relies on algebraic fingerprinting andrandomized polynomial identity testing over a finite field, and uses agenerating polynomial implicit in Vazirani and Yannakakis ( Discrete Appl.Math. 1989) that enumerates weighted cycle covers as a difference of apermanent and a determinant polynomial. The need to work with the permanent iswhere our main technical contribution occurs. We design a family of finitecommutative rings of characteristic 4 that simultaneously (i) give anondegenerate representation for the generating polynomial identity via thepermanent and the determinant, (ii) support efficient permanent computations,and (iii) enable emulation of finite-field arithmetic in characteristic 2. Hereour work is foreshadowed by that of Bj\"orklund and Husfeldt (SIAM J. Comput.2019), who used a considerably less efficient ring design to obtain apolynomial-time algorithm for the shortest two disjoint paths problem.  Building on work of Gilbert and Tarjan (Numer. Math. 1978) as well as Alonand Yuster (J. ACM 2013), we also show how ideas from the nested dissectiontechnique for solving linear equation systems leads to faster algorithm designswhen we have control on the separator structure of the input graph; forexample, this happens when the input has bounded genus.

The Shortest Even Cycle Problem is Tractable