Exact Weight Subgraphs and the k-Sum Conjecture

DOI10.1007/978-3-642-39206-1_1zbMath1336.68111arXiv1304.7558OpenAlexW2119461694MaRDI QIDQ5326545

Kevin Lewi, Amir Abboud

Publication date: 6 August 2013

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

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

Mathematics Subject Classification ID

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

Related Items (10)

Matching Triangles and Basing Hardness on an Extremely Popular Conjecture ⋮ Knapsack problem with objective value gaps ⋮ Simple paths with exact and forbidden lengths ⋮ Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle ⋮ Unnamed Item ⋮ Dividing splittable goods evenly and with limited fragmentation ⋮ Fine-Grained Reductions and Quantum Speedups for Dynamic Programming. ⋮ A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem ⋮ On Multidimensional and Monotone k-SUM ⋮ Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic $\tilde{O}(n^{5/3})$ Time

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 3SUM, 3XOR, triangles
• Finding and counting small induced subgraphs efficiently
• Faster algorithms for finding and counting subgraphs
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• On the complexity of fixed parameter clique and dominating set
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time
• On a class of \(O(n^ 2)\) problems in computational geometry
• 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
• Algorithms and Data Structures
• Lower bounds for linear degeneracy testing

This page was built for publication: Exact Weight Subgraphs and the k-Sum Conjecture