Exact weight subgraphs and the k-sum conjecture

DOI10.1007/978-3-642-39206-1_1zbMATH Open1336.68111arXiv1304.7558OpenAlexW2119461694MaRDI QIDQ5326545FDOQ5326545

Authors: Amir Abboud, Kevin Lewi 

Publication date: 6 August 2013

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1304.7558

Recommendations

• Finding, minimizing, and counting weighted subgraphs
• Finding, minimizing, and counting weighted subgraphs
• Losing weight by gaining edges
• Finding the Smallest H-Subgraph in Real Weighted Graphs and Related Problems
• Finding heaviest \(H\)-subgraphs in real weighted graphs, with applications

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Cites Work

• On a class of \(O(n^ 2)\) problems in computational geometry
• 3SUM, 3XOR, triangles
• Towards polynomial lower bounds for dynamic problems
• Color-coding
• Universal hashing and \(k\)-wise independent random variables via integer arithmetic without primes
• Finding, minimizing, and counting weighted subgraphs
• On the possibility of faster \textsc{SAT} algorithms
• Lower bounds for linear degeneracy testing
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Finding and counting small induced subgraphs efficiently
• Title not available (Why is that?)
• Faster algorithms for finding and counting subgraphs
• Counting and detecting small subgraphs via equations and matrix multiplication
• Algorithms and Data Structures
• On the complexity of fixed parameter clique and dominating set
• Title not available (Why is that?)

Cited In (14)

• Finding, minimizing, and counting weighted subgraphs
• A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem
• Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle
• Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time
• Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
• Simple paths with exact and forbidden lengths
• Fine-Grained Reductions and Quantum Speedups for Dynamic Programming.
• Knapsack problem with objective value gaps
• On Multidimensional and Monotone k-SUM
• Dividing splittable goods evenly and with limited fragmentation
• Finding, minimizing, and counting weighted subgraphs
• Title not available (Why is that?)
• \(k\)-SUM in the sparse regime: complexity and applications
• Losing weight by gaining edges

This page was built for publication: Exact weight subgraphs and the \(k\)-sum conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5326545)