Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
Exact Weight Subgraphs and the k-Sum Conjecture
verfasst von : Amir Abboud, Kevin Lewi
Erschienen in: Automata, Languages, and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
.