American Institute of Mathematical Sciences

Advanced
March  2018, 8(1): 1-16. doi: 10.3934/naco.2018001

Linearly-growing reductions of Karp's 21 NP-complete problems

Jerzy A. Filar 1, , Michael Haythorpe 1,, and  Richard Taylor 2,

1. 

School of Computer Science, Engineering and Mathematics, Flinders University, Bedford Park, SA 5042, Australia
2. 

Defence Science and Technology Group, Canberra, ACT 2600, Australia

* Corresponding author: Michael Haythorpe: michael.haythorpe@flinders.edu.au

The reviewing process was handled by A. Baghirov

Received  September 2015 Revised  January 2018 Published  March 2018

We address the question of whether it may be worthwhile to convert certain, now classical, NP-complete problems to one of a smaller number of kernel NP-complete problems. In particular, we show that Karp's classical set of 21 NP-complete problems contains a kernel subset of six problems with the property that each problem in the larger set can be converted to one of these six problems with only linear growth in problem size. This finding has potential applications in optimisation theory because the kernel subset includes 0-1 integer programming, job sequencing and undirected Hamiltonian cycle problems.

Keywords: NP-complete, reduction, linear, Karp, complexity, integer programming.
Mathematics Subject Classification: Primary: 68Q15; Secondary: 90C10.
Citation: Jerzy A. Filar, Michael Haythorpe, Richard Taylor. Linearly-growing reductions of Karp's 21 NP-complete problems. Numerical Algebra, Control & Optimization, 2018, 8 (1) : 1-16. doi: 10.3934/naco.2018001
References:
[1]

S. Cook, The complexity of theorem proving procedures, Proceedings of the Third Annual ACM Symposium on Theory of Computing, (1971), 151-158. Google Scholar

[2]

W. J. Cook, W. H. Cunningham, W. R. Pulleyblank and A. Schrijver, Combinatorial Optimization, Wiley, New York, 1998.  Google Scholar

[3]

A. Johnson. Quasi-Linear Reduction of Hamiltonian Cycle Problem (HCP) to Satisfiability Problem (SAT), IP. com, Disclosure Number: IPCOM000237123D, 2014. Google Scholar

[4]

R. M. Karp, Reducibility Among Combinatorial Problems, Springer, New York, 1972.  Google Scholar

[5]

C. H. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.  Google Scholar

show all references

The reviewing process was handled by A. Baghirov

References:
[1]

S. Cook, The complexity of theorem proving procedures, Proceedings of the Third Annual ACM Symposium on Theory of Computing, (1971), 151-158. Google Scholar

[2]

W. J. Cook, W. H. Cunningham, W. R. Pulleyblank and A. Schrijver, Combinatorial Optimization, Wiley, New York, 1998.  Google Scholar

[3]

A. Johnson. Quasi-Linear Reduction of Hamiltonian Cycle Problem (HCP) to Satisfiability Problem (SAT), IP. com, Disclosure Number: IPCOM000237123D, 2014. Google Scholar

[4]

R. M. Karp, Reducibility Among Combinatorial Problems, Springer, New York, 1972.  Google Scholar

[5]

C. H. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.  Google Scholar

Figure 1.  A tree showing the 21 NP-complete problems identified by Karp, where the edges correspond to individual reductions
Figure Options

Download full-size image

Download as PowerPoint slide

[1]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399
[2]

Vladimir Gaitsgory, Ilya Shvartsman. Linear programming estimates for Cesàro and Abel limits of optimal values in optimal control problems. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021102
[3]

Qing Liu, Bingo Wing-Kuen Ling, Qingyun Dai, Qing Miao, Caixia Liu. Optimal maximally decimated M-channel mirrored paraunitary linear phase FIR filter bank design via norm relaxed sequential quadratic programming. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1993-2011. doi: 10.3934/jimo.2020055
[4]

Xiaochen Mao, Weijie Ding, Xiangyu Zhou, Song Wang, Xingyong Li. Complexity in time-delay networks of multiple interacting neural groups. Electronic Research Archive, , () : -. doi: 10.3934/era.2021022
[5]

Hyunjin Ahn, Seung-Yeal Ha, Woojoo Shim. Emergent dynamics of a thermodynamic Cucker-Smale ensemble on complete Riemannian manifolds. Kinetic & Related Models, 2021, 14 (2) : 323-351. doi: 10.3934/krm.2021007
[6]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023
[7]

Mohammed Abdelghany, Amr B. Eltawil, Zakaria Yahia, Kazuhide Nakata. A hybrid variable neighbourhood search and dynamic programming approach for the nurse rostering problem. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2051-2072. doi: 10.3934/jimo.2020058
[8]

Huy Dinh, Harbir Antil, Yanlai Chen, Elena Cherkaev, Akil Narayan. Model reduction for fractional elliptic problems using Kato's formula. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021004
[9]

Xiaofei Liu, Yong Wang. Weakening convergence conditions of a potential reduction method for tensor complementarity problems. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021080
[10]

Palash Sarkar, Subhadip Singha. Classical reduction of gap SVP to LWE: A concrete security analysis. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021004
[11]

Peter Benner, Jens Saak, M. Monir Uddin. Balancing based model reduction for structured index-2 unstable descriptor systems with application to flow control. Numerical Algebra, Control & Optimization, 2016, 6 (1) : 1-20. doi: 10.3934/naco.2016.6.1
[12]

Guiyang Zhu. Optimal pricing and ordering policy for defective items under temporary price reduction with inspection errors and price sensitive demand. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021060
[13]

Sumon Sarkar, Bibhas C. Giri. Optimal lot-sizing policy for a failure prone production system with investment in process quality improvement and lead time variance reduction. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021048
[14]

Diana Keller. Optimal control of a linear stochastic Schrödinger equation. Conference Publications, 2013, 2013 (special) : 437-446. doi: 10.3934/proc.2013.2013.437
[15]

Guillaume Bal, Wenjia Jing. Homogenization and corrector theory for linear transport in random media. Discrete & Continuous Dynamical Systems, 2010, 28 (4) : 1311-1343. doi: 10.3934/dcds.2010.28.1311
[16]

Nizami A. Gasilov. Solving a system of linear differential equations with interval coefficients. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2739-2747. doi: 10.3934/dcdsb.2020203
[17]

Alexander A. Davydov, Massimo Giulietti, Stefano Marcugini, Fernanda Pambianco. Linear nonbinary covering codes and saturating sets in projective spaces. Advances in Mathematics of Communications, 2011, 5 (1) : 119-147. doi: 10.3934/amc.2011.5.119
[18]

W. Cary Huffman. On the theory of $\mathbb{F}_q$-linear $\mathbb{F}_{q^t}$-codes. Advances in Mathematics of Communications, 2013, 7 (3) : 349-378. doi: 10.3934/amc.2013.7.349
[19]

Arunima Bhattacharya, Micah Warren. $ C^{2, \alpha} $ estimates for solutions to almost Linear elliptic equations. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021024
[20]

Markus Harju, Jaakko Kultima, Valery Serov, Teemu Tyni. Two-dimensional inverse scattering for quasi-linear biharmonic operator. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2021026

 Impact Factor: 

Tools

Metrics

  • PDF downloads (347)
  • HTML views (788)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences