2013/11/13 by Amir Abboud, Abboud, Amir, Kevin Lewi +3
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems #cs.CC #cs.DS
paper · pdf · doi:10.48550/arxiv.1311.3054
Title of an earlier version of this paper: On the Parameterized Complexity of k-SUM
openalex publication_date 2013/11/13 · arxiv created 2015/11/25 · arxiv updated 2015/11/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present a new way to encode weighted sums into unweighted pairwise constraints, obtaining the following results. - Define the k-SUM problem to be: given n integers in [-n2k, n2k] are there k which sum to zero? (It is well known that the same problem over arbitrary integers is equivalent to the above definition, by linear-time randomized reductions.) We prove that this definition of k-SUM remains W[1]-hard, and is in fact W[1]-complete: k-SUM can be reduced to f(k) * no(1) instances of k-Clique. - The maximum node-weighted k-Clique and node-weighted k-dominating set problems can be reduced to no(1) instances of the unweighted k-Clique and k-dominating set problems, respectively. This implies a strong equivalence between the time complexities of the node weighted problems and the unweighted problems: any polynomial improvement on one would imply an improvement for the other. - A triangle of weight 0 in a node weighted graph with m edges can be deterministically found in m1.41 time.