Exact Weight Subgraphs and the k-Sum Conjecture

1.1 Our Results

• If k-SUM requires O(n^⌈k/2⌉−ε) time, Theorem 2 rules out that running time for exact-weight H, k-matching, k-star, and (k−1)-path on the stated graph sizes.The graph sizes are n for H and (k−1)-path, √n for k-matching, and n^(1−1/k) for k-star.Source: §1.1 · p. 3
• For k=3, faster algorithms for 3-SUM also yield faster algorithms for 3-STAR and 3-MATCHING, whose exact-weight thresholds are O(n^3) and O(n^4), respectively.The results state that either all three problems admit the specified improvements or none do.Source: §1.1 · p. 3
• An O(n^(3−ε)) algorithm for EXACT-WEIGHT-4-PATH would imply an O(n^(3−ε′)) algorithm for 5-SUM, while EXACT-WEIGHT-5-PATH improvements extend to the other connected 3-edge subgraph problems considered.The unweighted and minimum-weight versions of 4-PATH are solvable in O(n^2), and 6-SUM reduces to 5-PATH.Source: §1.1 · pp. 3–4
• If H1 is a vertex-minor of H2, an O(n^α) algorithm for EXACT-WEIGHT-H2 gives a Õ(n^α) algorithm for EXACT-WEIGHT-H1.The paper uses this relation to connect 4-CYCLE, 4-PATH, and 3-CLIQUE.Source: §1.1 · p. 3
• A d-separator reduces EXACT-WEIGHT-H to Õ(n^|S|) instances of d-SUM, yielding an Õ(n^γ(H)) upper bound.For k-PATH, the middle vertex is an optimal separator and gives an O(n^⌈(k+1)/2⌉) running time; in many cases, improving the separator algorithm would refute the k-SUM Conjecture.Source: §1.1 · pp. 4–5
• For an H with k vertices and an independent set of size s, MIN-WEIGHT-H can be solved in Õ(n^(k−s+1)) time, improving on the cited O(n^(k−s+2)) algorithm.The paper also highlights bounded-treewidth and large-independent-set cases for its exact-weight algorithm.Source: §1.1 · p. 5

2 Preliminaries and Basic Constructions

• The framework represents graph vertices, edges, and neighborhoods by V(G), E(G), and N(v), and defines reductions by how faster algorithms transfer between problems.A polylogarithmic improvement to the target problem need not yield an improvement to the source problem.Source: §2 · p. 6, §2.1 · p. 6

2.2 The k-SUM Problem

• The paper uses a list-based k-SUM formulation, including CONVOLUTION-k-SUM, and establishes that k-SUM reduces to it with matching exponent parameters.The list formulation selects one number from each of k lists; the convolution version also constrains the selected indices.Source: §2.2 · p. 7

2.3 H-Partite Graphs

• An H-partite graph partitions its vertices into k sets, with edges allowed only between pairs corresponding to edges of H.An H-subgraph selects exactly one vertex from each partition.Source: §2.3 · p. 7
• The structured EXACT-H formulation asks whether a complete H-partite graph has an H-subgraph of total weight zero, and it is tightly reducible to EXACT-WEIGHT-H.The paper uses EXACT-H in its proofs, with the results applying to EXACT-WEIGHT-H through the stated equivalence.Source: §2.3 · p. 7

• k-SUM on n numbers reduces to one EXACT-H instance on kn vertices for any k-node subgraph H.The construction places each list in a vertex class and uses node weights so an H-subgraph’s weight equals the corresponding k-SUM solution’s sum.Source: §3 · p. 8
• For k-MATCHING, k-SUM reduces to one exact-weight instance on k√n vertices by encoding each list value as an edge weight.Each matching’s total weight equals the associated k-SUM solution’s sum.Source: §3 · p. 8
• If EXACT-k-STAR runs in O(n^α), then k-SUM runs in ˜O(n^((1−1/k)·α)).The reduction uses a sequence of k-SUM instances and a self-reduction from k-SUM to that sequence.Source: §3 · p. 9
• An O(n^⌈k/2⌉−ε) algorithm for EXACT-k-PATH would yield an O(n^⌈k/2⌉−ε′) algorithm for (k+1)-SUM.Source: §3 · p. 10
• The path reduction encodes a convolution-(k+1)-SUM instance in edge weights so that zero-weight k-paths correspond to zero-sum solutions.Source: §3 · p. 10

4 Relationships Between Subgraphs

• A vertex-minor is obtained through a sequence of edge deletions or vertex contractions, with contractions permitted between nonadjacent vertices.Source: §4 · pp. 10–11
• Deleting an edge from H′ reduces EXACT-H on kn nodes to one EXACT-H′ instance on kn nodes by assigning weight zero to the added super-edge.Source: §4 · p. 11
• Contracting two vertices reduces EXACT-H on (k+1)n nodes to one EXACT-H′ instance on kn nodes by copying each vertex and adding opposite weights to the copies.The weight offsets force both copies to be selected together in any zero-weight H′-subgraph.Source: §4 · p. 11
• The contraction reduction preserves zero-weight solutions in both directions, so EXACT-H′ has a zero-weight subgraph exactly when EXACT-H does.Source: §4 · pp. 11–12

4.1 Reverse Direction

• When H adds a universal node to H′, EXACT-H reduces to α+1 instances of EXACT-H′, each testing a fixed vertex in the new node’s class.Source: §4.1 · p. 12

• A separator algorithm enumerates S-subgraphs and uses 2-SUM to combine the two edge-disjoint sides of H.For a separator (S, H1, H2), the running time is O(3^k + n^|S|·(n^|H1| + n^|H2|)).Source: §5 · p. 13
• A faster d-SUM algorithm can improve EXACT-H through the generalized separator reduction, though current best-known k-SUM runtimes make it no better than the 2-SUM separator algorithm.Source: §5 · pp. 13–14
• For a d-separator, EXACT-WEIGHT-H reduces to ˜O(n^|S|) instances of d-SUM, each on at most max{n^|H1|, …, n^|Hd|} numbers.Source: §5 · pp. 13–14
• If H has an independent set of size s, EXACT-H reduces to O(n^(k−s)) instances of s-SUM on n integers.Source: §5 · p. 14
• For H on k nodes with treewidth bounded by tw, a d-separator of size tw yields parts of at most 2k/3 nodes, establishing γ(H) ≤ 2k/3 + tw.Source: §5 · p. 14
• For an H with an independent set of size s, minimum total weight can be found in ˜O(n^(k−s+1)) time.The procedure replaces d-SUM with finding the minimum value in each list for each separator subgraph.Source: §5 · p. 14

• 5-CYCLE is the simplest subgraph for which the paper cannot give tight upper and lower bounds; whether O(n^(4−ε)) is possible without refuting k-SUM remains open.Source: §6 · p. 15
• The authors ask whether EXACT-WEIGHT-4-PATH reduces to EXACT-WEIGHT-3-STAR, which would connect breaking the 3-SUM conjecture to an O(n^(3−ε)) All-Pairs Shortest Paths algorithm.Source: §6 · p. 15

A Reducibility

• For weighted graph problems and k-SUM with integers in [−M, M], n denotes the number of nodes or integers times log M, respectively.Source: A Reducibility · p. 16
• A is reducible to B when an oracle algorithm solves A with probability 1−o(1), subject to the definition’s additional conditions.The supplied passage gives only the success-probability condition; the remaining conditions are not fully shown.Source: A Reducibility · p. 16
• Reducibility is transitive: if A reduces to B and B reduces to C, then A reduces to C.Source: A Reducibility · p. 16
• An O(n^(b−ε)) algorithm for B yields an O(n^(a−δ)) algorithm for A for some δ>0, with success probability 1−o(1).Source: A Reducibility · p. 16

B Proof of Lemma 8

• EXACT-H reduces to EXACT-WEIGHT-H by encoding vertex weights and super-edge offsets into edge weights and choosing a target that preserves zero-weight H-subgraphs.The proof argues that each super-edge is used once and that a target-summing solution occupies distinct super-nodes, recovering total original weight zero.Source: B Proof of Lemma 8 · pp. 16–17
• Repeating the random partitioning O(k^k) times supports the reduction, and the proof says the procedure can be derandomized.Source: B Proof of Lemma 8 · p. 17
• EXACT-WEIGHT-H reduces to EXACT-H by randomly assigning vertices to k parts, with a fixed H-copy landing in the required parts with probability 1/k^k.Source: B Proof of Lemma 8 · p. 17

C Proof of Lemma 7

• Dietzfelbinger hashing provides load balancing and almost linearity: few numbers enter overloaded buckets, and sums constrain the final number to one of k buckets.Source: C Proof of Lemma 7 · p. 17
• The reduction repeats hashing O(k^k log n) times and ignores numbers in overloaded buckets.Source: C Proof of Lemma 7 · p. 18
• It enumerates kR^k convolution-k-SUM instances over bucket positions and offsets, with each instance containing lists of t numbers.Source: C Proof of Lemma 7 · p. 18
• A k-SUM solution avoids overloaded buckets in a good iteration with probability 1−O(n^−c), and almost linearity places its final number in the enumerated offset bucket.Source: C Proof of Lemma 7 · p. 18
• Every solution found in a convolution instance is also a valid k-SUM solution with the same sum, establishing the reduction’s reverse direction.Source: C Proof of Lemma 7 · p. 18
• For odd k, setting t=n^ε makes the first term insignificant and yields a k-SUM algorithm in O~(n^(⌈k/2⌉−ε′)) time for some ε′>0.Source: C Proof of Lemma 7 · pp. 17–18