The shortest even cycle problem is tractable

dc.contributorAalto-yliopistofi
dc.contributorAalto Universityen
dc.contributor.authorBjörklund, Andreasen_US
dc.contributor.authorHusfeldt, Thoreen_US
dc.contributor.authorKaski, Petterien_US
dc.contributor.departmentDepartment of Computer Scienceen
dc.contributor.editorLeonardi, Stefanoen_US
dc.contributor.editorGupta, Anupamen_US
dc.contributor.groupauthorComputer Science Professorsen
dc.contributor.groupauthorComputer Science - Algorithms and Theoretical Computer Science (TCS)en
dc.contributor.groupauthorProfessorship Kaski Petterien
dc.contributor.organizationLund Universityen_US
dc.date.accessioned2022-10-19T06:47:16Z
dc.date.available2022-10-19T06:47:16Z
dc.date.issued2022-09-06en_US
dc.descriptionFunding Information: We are grateful to the anonymous reviewers for bringing [10] to our attention. TH is supported by VILLUM Foundation grant 16582. Publisher Copyright: © 2022 Owner/Author.
dc.description.abstractGiven 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. Methodologically, our algorithm relies on the standard framework of algebraic fingerprinting and randomized polynomial identity testing over a finite field, and in fact relies on a generating polynomial implicit in a paper of Vazirani and Yannakakis (Discrete Appl. Math. 1989) that enumerates weighted cycle covers by the parity of their number of cycles as a difference of a permanent and a determinant polynomial. The need to work with the permanent-known to be #P-hard apart from a very restricted choice of coefficient rings (Valiant, Theoret. Comput. Sci. 1979)-is where our main technical contribution occurs. We design a family of finite commutative rings of characteristic 4 that simultaneously (i) give a nondegenerate representation for the generating polynomial identity via the permanent and the determinant, (ii) support efficient permanent computations by extension of Valiant's techniques, and (iii) enable emulation of finite-field arithmetic in characteristic 2. Here our work is foreshadowed by that of Björklund and Husfeldt (SIAM J. Comput. 2019), who used a considerably less efficient commutative ring design-in particular, one lacking finite-field emulation-to obtain a polynomial-time algorithm for the shortest two disjoint paths problem in undirected graphs. Building on work of Gilbert and Tarjan (Numer. Math. 1978) as well as Alon and Yuster (J. ACM 2013), we also show how ideas from the nested dissection technique for solving linear equation systems-introduced by George (SIAM J. Numer. Anal. 1973) for symmetric positive definite real matrices-leads to faster algorithm designs in our present finite-ring randomized context when we have control on the separator structure of the input graph; for example, this happens when the input has bounded genus.en
dc.description.versionPeer revieweden
dc.format.extent14
dc.format.extent117-130
dc.format.mimetypeapplication/pdfen_US
dc.identifier.citationBjörklund, A, Husfeldt, T & Kaski, P 2022, The shortest even cycle problem is tractable . in S Leonardi & A Gupta (eds), STOC 2022 - Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing . Proceedings of the Annual ACM Symposium on Theory of Computing, ACM, pp. 117-130, ACM Symposium on Theory of Computing, Rome, Italy, 20/06/2022 . https://doi.org/10.1145/3519935.3520030en
dc.identifier.doi10.1145/3519935.3520030en_US
dc.identifier.isbn9781450392648
dc.identifier.issn0737-8017
dc.identifier.otherPURE UUID: d66d23c1-e581-40d9-a3c5-4c7b0a18c9bfen_US
dc.identifier.otherPURE ITEMURL: https://research.aalto.fi/en/publications/d66d23c1-e581-40d9-a3c5-4c7b0a18c9bfen_US
dc.identifier.otherPURE LINK: http://www.scopus.com/inward/record.url?scp=85132773684&partnerID=8YFLogxKen_US
dc.identifier.otherPURE FILEURL: https://research.aalto.fi/files/89252922/The_Shortest_Even_Cycle_Problem_Is_Tractable.pdfen_US
dc.identifier.urihttps://aaltodoc.aalto.fi/handle/123456789/117288
dc.identifier.urnURN:NBN:fi:aalto-202210196076
dc.language.isoenen
dc.publisherACM
dc.relation.ispartofACM Symposium on Theory of Computingen
dc.relation.ispartofseriesSTOC 2022 - Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computingen
dc.relation.ispartofseriesProceedings of the Annual ACM Symposium on Theory of Computingen
dc.rightsopenAccessen
dc.subject.keyworddirected graphen_US
dc.subject.keywordparity cycle coveren_US
dc.subject.keywordpermanenten_US
dc.subject.keywordpolynomial-time algorithmen_US
dc.subject.keywordshortest even cycleen_US
dc.subject.keywordshortest two disjoint pathsen_US
dc.titleThe shortest even cycle problem is tractableen
dc.typeA4 Artikkeli konferenssijulkaisussafi
dc.type.versionpublishedVersion
Files