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查看全文

Solidot 文章翻译

 你的名字 留空匿名提交 你的Email或网站 用户可以联系你 标题 简单描述 内容 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