Reducibility Among Combinatorial Problems

By Richard M. Karp. 1972

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Algorithms & Complexity

Citations in the corpus

Scalable agent alignment via reward modeling: a research direction (2018, background): “When using polynomially bounded quantiﬁers and a formula ϕ that can be evaluated in polynomial time, reward modeling is analogous to solving NP-complete problems: a nondeterministic execution (analogous to the agent) proposes a solution which can be ‘evaluated’ for correctness in deterministic polyn”
Learning Combinatorial Optimization Algorithms over Graphs (2017, background): “In fact, of Karp’s 21 problems in the seminal paper on reducibility [19], 10 are decision versions of graph optimization problems, while most of the other 11 problems, such as set covering, can be naturally formulated on graphs.”
Drift analysis and average time complexity of evolutionary algorithms (2001, background): “The partition probl em can be polynomially transformed to it [21].”
Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions (2002, methodology): “It remains to show that Rot(c) is a non-singular matrix, or equivalently, the n-dimensional volume of P(Rot(c)) is nonzero. Notice that P(Rot(c)) is an almost cubic parallelepiped obtained by perturbing the main vertexes of a hypercube of size l = nS by at most = ( √ n/2)S. In Micciancio (2002b) it ”
Proof verification and hardness of approximation problems (1992, background): “The theory of NP-completeness, developed by Cook [1971], Karp [1972], and Levin [1973], shows that many decision problems of interest, such as satisfiability, are NP-complete.”
Combinatorial optimization and reasoning with graph neural networks (2021, background): “In fact, from the 21 NP -complete problems identiﬁed by Karp [1972], ten are decision versions of graph optimization problems, e.g., the travelling saleperson problem (TSP).”
Algorithms for Computing Minimal Unsatisfiable Subsets of Constraints (2007, background): “The problem of deciding whether a given collection of sets has a hitting set of size k or smaller is NP-complete [23].”
A Combinatorial Approach to Nonlocality and Contextuality (2012, background): “1), To be decided: Is B satisfiable? This is well-known to be NP-complete [59].”
OptiType: precision HLA typing from next-generation sequencing data (2014, background): “Finally, based on this matrix, a special case of the set cover problem (Karp, 1972) is formulated as an integer linear program (ILP) that selects up to two alleles for each locus simultaneously, maximizing the number of mapped reads that can be explained by the predicted genotype (Fig.”
Spectrum Sharing in Dynamic Spectrum Access Networks: WPE-II Written Report (2009, background): “The goal of minimizing total number of colors can be written as: Additionally, we note that when the goal is to minimize the total number of colors and the candidate color set L n,m is same (homogeneous network) for each vertex, then the problem falls back to a normal graph coloring problem [17].”
Iterative methods for sparse linear systems (2003, background): “In fact, finding the independent set of maximum cardinal is NP -hard [132].”
A Geometric Theory for Hypergraph Matching (2011, background): “However, while Edmonds’ algorithm [10] provides an efficient means to determine whether a graph has a perfect matching, the decision problem is NP-complete in k-graphs for k ≥ 3 (it is one of Karp’s original 21 NP-complete problems [18]).”