  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.
