Finding the Minimum-Weight k-Path

2013/07/09 by Avinatan Hassidim, Hassidim, Avinatan, Orgad Keller +5
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS

paper · pdf · doi:10.48550/arxiv.1307.2415

To appear at WADS 2013

arxiv created 2013/07/09 · arxiv updated 2013/07/10

Abstract

Given a weighted n-vertex graph G with integer edge-weights taken from a range [-M,M], we show that the minimum-weight simple path visiting k vertices can be found in time O(2^k \poly(k) M n^ω) = O^*(2^k M). If the weights are reals in [1,M], we provide a (1+ε)-approximation which has a running time of O(2^k \poly(k) n^ω(loglog M + 1/ε)). For the more general problem of k-tree, in which we wish to find a minimum-weight copy of a k-node tree T in a given weighted graph G, under the same restrictions on edge weights respectively, we give an exact solution of running time O(2^k \poly(k) M n³) and a (1+ε)-approximate solution of running time O(2^k \poly(k) n³(loglog M + 1/ε)). All of the above algorithms are randomized with a polynomially-small error probability.

Related

• Minimum Cut in O(mlog² n) Time
• Faster Exact and Approximate Algorithms for k-Cut
• New and Simplified Distributed Algorithms for Weighted All Pairs Shortest Paths
• On r-Simple k-Path
• Finding the KT partition of a weighted graph in near-linear time