Parallel Polynomial Permanent Mod Powers of 2 and Shortest Disjoint Cycles

2021/06/01 by Datta, Samir, Jaiswal, Kishlaya
#Computational Complexity (cs.CC) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2106.00714

Abstract

We present a parallel algorithm for permanent mod 2^k of a matrix of univariate integer polynomials. It places the problem in ParityL subset of NC². This extends the techniques of [Valiant], [Braverman, Kulkarni, Roy] and [Björklund, Husfeldt], and yields a (randomized) parallel algorithm for shortest 2-disjoint paths improving upon the recent result from (randomized) polynomial time. We also recognize the disjoint paths problem as a special case of finding disjoint cycles, and present (randomized) parallel algorithms for finding a shortest cycle and shortest 2-disjoint cycles passing through any given fixed number of vertices or edges.

Related

• The Shortest Even Cycle Problem is Tractable
• A parallel algorithm for the odd two-face shortest k-disjoint path problem
• A new algebraic technique for polynomial-time computing the number modulo 2 of Hamiltonian decompositions and similar partitions of a graph's edge set
• Computing Permanents and Counting Hamiltonian Cycles Faster
• On the expressive power of planar perfect matching and permanents of bounded treewidth matrices