## Shortest (A+B)-path packing via hafnian. (arXiv:1603.08073v2 [math.CO] UPDATED)

Bj\"orklund and Husfeldt developed a randomized polynomial time algorithm to
solve the shortest two disjoint paths problem. Their algorithm is based on
computation of permanents modulo 4 and the isolation lemma. In this paper, we
consider the following generalization of the shortest two disjoint paths
problem, and develop a similar algebraic algorithm. The shortest perfect
$(A+B)$-path packing problem is: given an undirected graph $G$ and two disjoint
node subsets $A,B$ with even cardinalities, find a shortest $|A|/2+|B|/2$
disjoint paths whose ends are both in $A$ or both in $B$. Besides its
NP-hardness, we prove that this problem can be solved in randomized polynomial
time if $|A|+|B|$ is fixed. Our algorithm basically follows the framework of
Bj\"orklund and Husfeldt but uses a new technique: computation of hafnian
modulo $2^k$ combined with Gallai's reduction from $T$-paths to matchings. We
also generalize our technique for solving other path packing problems, and
discuss its limit查看全文