Shortest (A+B)-Path Packing Via Hafnian

Björklund 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...

Full description

Saved in:
Bibliographic Details
Published in:Algorithmica 2018-08, Vol.80 (8), p.2478-2491
Main Authors: Hirai, Hiroshi, Namba, Hiroyuki
Format: Article
Language:English
Subjects:
Algorithm Analysis and Problem Complexity
Algorithms
Computation
Computer Science
Computer Systems Organization and Communication Networks
Data Structures and Information Theory
Mathematics of Computing
Polynomials
Randomization
Set theory
Theory of Computation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Björklund 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 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örklund 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 limitation.
ISSN:0178-4617
1432-0541
DOI:10.1007/s00453-017-0334-0