| 1. |
- Björklund, Andreas, et al.
(författare)
-
Shortest two disjoint paths in polynomial time
- 2019
-
Ingår i: SIAM Journal on Computing. - 0097-5397. ; 48:6, s. 1698-1710
-
Tidskriftsartikel (refereegranskat)abstract
- Given an undirected graph and two pairs of vertices (si, ti) for i ϵ{ 1, 2} we show that there is a polynomial time Monte Carlo algorithm that finds disjoint paths of smallest total length joining si and ti for i ϵ{1, 2}, respectively, or concludes that there most likely are no such paths at all. Our algorithm applies to both the vertex- and edge-disjoint versions of the problem. Our algorithm is algebraic and uses permanents over the polynomial ring Z4[X] in combination with the isolation lemma of Mulmuley, Vazirani, and Vazirani to detect a solution. To this end, we develop a fast algorithm for permanents over the ring Zt[X], where t is a power of 2, by modifying Valiant's 1979 algorithm for the permanent over Zt
|
|
| 2. |
- Björklund, Andreas, et al.
(författare)
-
The shortest even cycle problem is tractable
- 2022
-
Ingår i: STOC 2022 - Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. - New York, NY, USA : ACM. - 0737-8017. - 9781450392648 ; , s. 117-130
-
Konferensbidrag (refereegranskat)abstract
- 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. 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.
|
|
| 3. |
- Brand, Cornelius, et al.
(författare)
-
Extensor-Coding
- 2018
-
Ingår i: STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. - New York, NY, USA : ACM. - 9781450355599 ; , s. 535-544
-
Konferensbidrag (refereegranskat)abstract
- We devise an algorithm that approximately computes the number of paths of length k in a given directed graph with n vertices up to a multiplicative error of 1 ± . Our algorithm runs in time −24k(n + m) poly(k). The algorithm is based on associating with each vertex an element in the exterior (or, Grassmann) algebra, called an extensor, and then performing computations in this algebra. This connection to exterior algebra generalizes a number of previous approaches for the longest path problem and is of independent conceptual interest. Using this approach, we also obtain a deterministic 2k · poly(n) time algorithm to find a k-path in a given directed graph that is promised to have few of them. Our results and techniques generalize to the subgraph isomorphism problem when the subgraphs we are looking for have bounded pathwidth. Finally, we also obtain a randomized algorithm to detect k-multilinear terms in a multivariate polynomial given as a general algebraic circuit. To the best of our knowledge, this was previously only known for algebraic circuits not involving negative constants.
|
|
| 4. |
- Bringmann, Karl, et al.
(författare)
-
Multivariate Analysis of Orthogonal Range Searching and Graph Distances
- 2020
-
Ingår i: Algorithmica. - : Springer Science and Business Media LLC. - 0178-4617 .- 1432-0541. ; 82:8, s. 2292-2315
-
Tidskriftsartikel (refereegranskat)abstract
- We show that the eccentricities, diameter, radius, and Wiener index of an undirected n-vertex graph with nonnegative edge lengths can be computed in time O(n·(k+⌈logn⌉k)·2klogn), where k is linear in the treewidth of the graph. For every ϵ> 0 , this bound is n1 + ϵexp O(k) , which matches a hardness result of Abboud et al. (in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016. https://doi.org/10.1137/1.9781611974331.ch28) and closes an open problem in the multivariate analysis of polynomial-time computation. To this end, we show that the analysis of an algorithm of Cabello and Knauer (Comput Geom 42:815–824, 2009. https://doi.org/10.1016/j.comgeo.2009.02.001) in the regime of non-constant treewidth can be improved by revisiting the analysis of orthogonal range searching, improving bounds of the form log dn to (d+⌈logn⌉d), as originally observed by Monier (J Algorithms 1:60–74, 1980. https://doi.org/10.1016/0196-6774(80)90005-X). We also investigate the parameterization by vertex cover number.
|
|
