We consider the Exact-Weight- H problem of finding a (not necessarily induced) subgraph H of weight 0 in an edge-weighted graph G. We show that for every H, the complexity of this problem is strongly related to that of the infamous k-sum problem. In particular, we show that under the k-sum Conjecture, we can achieve tight upper and lower bounds for the Exact-Weight-H problem for various subgraphs H such as matching, star, path, and cycle. One interesting consequence is that improving on the O(n~3) upper bound for Exact-Weight-4-path or Exact-Weight-5-path will imply improved algorithms for 3-sum, 5-sum, All-Pairs Shortest Paths and other fundamental problems. This is in sharp contrast to the minimum-weight and (unweighted) detection versions, which can be solved easily in time O(n~2). We also show that a faster algorithm for any of the following three problems would yield faster algorithms for the others: 3-sum, Exact-Weight-3-matching, and Exact-Weight-3-star.
展开▼
