Figure 1.
A tree showing the 21 NP-complete problems identified by Karp, where the edges correspond to individual reductions
-
Previous Article
Fourier-splitting method for solving hyperbolic LQR problems
- NACO Home
- This Issue
- Next Article
March
2018, 8(1): 1-16.
doi: 10.3934/naco.2018001
Linearly-growing reductions of Karp's 21 NP-complete problems
| 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 |
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.
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 and 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. |
| [2] |
W. J. Cook, W. H. Cunningham, W. R. Pulleyblank and A. Schrijver,
Combinatorial Optimization, Wiley, New York, 1998. |
| [3] |
A. Johnson.
Quasi-Linear Reduction of Hamiltonian Cycle Problem (HCP) to Satisfiability Problem (SAT), IP. com, Disclosure Number: IPCOM000237123D, 2014. |
| [4] |
R. M. Karp,
Reducibility Among Combinatorial Problems, Springer, New York, 1972. |
| [5] |
C. H. Papadimitriou,
Computational Complexity, Addison-Wesley, 1994. |
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. |
| [2] |
W. J. Cook, W. H. Cunningham, W. R. Pulleyblank and A. Schrijver,
Combinatorial Optimization, Wiley, New York, 1998. |
| [3] |
A. Johnson.
Quasi-Linear Reduction of Hamiltonian Cycle Problem (HCP) to Satisfiability Problem (SAT), IP. com, Disclosure Number: IPCOM000237123D, 2014. |
| [4] |
R. M. Karp,
Reducibility Among Combinatorial Problems, Springer, New York, 1972. |
| [5] |
C. H. Papadimitriou,
Computational Complexity, Addison-Wesley, 1994. |
| [1] |
René Henrion, Christian Küchler, Werner Römisch. Discrepancy distances and scenario reduction in two-stage stochastic mixed-integer programming. Journal of Industrial and Management Optimization, 2008, 4 (2) : 363-384. doi: 10.3934/jimo.2008.4.363 |
| [2] |
Zhiguo Feng, Ka-Fai Cedric Yiu. Manifold relaxations for integer programming. Journal of Industrial and Management Optimization, 2014, 10 (2) : 557-566. doi: 10.3934/jimo.2014.10.557 |
| [3] |
Mahmoud Ameri, Armin Jarrahi. An executive model for network-level pavement maintenance and rehabilitation planning based on linear integer programming. Journal of Industrial and Management Optimization, 2020, 16 (2) : 795-811. doi: 10.3934/jimo.2018179 |
| [4] |
Elham Mardaneh, Ryan Loxton, Qun Lin, Phil Schmidli. A mixed-integer linear programming model for optimal vessel scheduling in offshore oil and gas operations. Journal of Industrial and Management Optimization, 2017, 13 (4) : 1601-1623. doi: 10.3934/jimo.2017009 |
| [5] |
Edward S. Canepa, Alexandre M. Bayen, Christian G. Claudel. Spoofing cyber attack detection in probe-based traffic monitoring systems using mixed integer linear programming. Networks and Heterogeneous Media, 2013, 8 (3) : 783-802. doi: 10.3934/nhm.2013.8.783 |
| [6] |
Mahdi Roozbeh, Saman Babaie–Kafaki, Zohre Aminifard. Two penalized mixed–integer nonlinear programming approaches to tackle multicollinearity and outliers effects in linear regression models. Journal of Industrial and Management Optimization, 2021, 17 (6) : 3475-3491. doi: 10.3934/jimo.2020128 |
| [7] |
Jianqin Zhou, Wanquan Liu, Xifeng Wang. Complete characterization of the first descent point distribution for the k-error linear complexity of 2n-periodic binary sequences. Advances in Mathematics of Communications, 2017, 11 (3) : 429-444. doi: 10.3934/amc.2017036 |
| [8] |
Yongjian Yang, Zhiyou Wu, Fusheng Bai. A filled function method for constrained nonlinear integer programming. Journal of Industrial and Management Optimization, 2008, 4 (2) : 353-362. doi: 10.3934/jimo.2008.4.353 |
| [9] |
Ye Tian, Cheng Lu. Nonconvex quadratic reformulations and solvable conditions for mixed integer quadratic programming problems. Journal of Industrial and Management Optimization, 2011, 7 (4) : 1027-1039. doi: 10.3934/jimo.2011.7.1027 |
| [10] |
Zhenbo Wang, Shu-Cherng Fang, David Y. Gao, Wenxun Xing. Global extremal conditions for multi-integer quadratic programming. Journal of Industrial and Management Optimization, 2008, 4 (2) : 213-225. doi: 10.3934/jimo.2008.4.213 |
| [11] |
Jing Quan, Zhiyou Wu, Guoquan Li. Global optimality conditions for some classes of polynomial integer programming problems. Journal of Industrial and Management Optimization, 2011, 7 (1) : 67-78. doi: 10.3934/jimo.2011.7.67 |
| [12] |
Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial and Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102 |
| [13] |
Mohamed A. Tawhid, Ahmed F. Ali. A simplex grey wolf optimizer for solving integer programming and minimax problems. Numerical Algebra, Control and Optimization, 2017, 7 (3) : 301-323. doi: 10.3934/naco.2017020 |
| [14] |
Charles Fefferman. Interpolation by linear programming I. Discrete and Continuous Dynamical Systems, 2011, 30 (2) : 477-492. doi: 10.3934/dcds.2011.30.477 |
| [15] |
Dandan Wang, Xiwang Cao, Gaojun Luo. A class of linear codes and their complete weight enumerators. Advances in Mathematics of Communications, 2021, 15 (1) : 73-97. doi: 10.3934/amc.2020044 |
| [16] |
Jean Creignou, Hervé Diet. Linear programming bounds for unitary codes. Advances in Mathematics of Communications, 2010, 4 (3) : 323-344. doi: 10.3934/amc.2010.4.323 |
| [17] |
Louis Caccetta, Syarifah Z. Nordin. Mixed integer programming model for scheduling in unrelated parallel processor system with priority consideration. Numerical Algebra, Control and Optimization, 2014, 4 (2) : 115-132. doi: 10.3934/naco.2014.4.115 |
| [18] |
Alina Ostafe, Igor E. Shparlinski, Arne Winterhof. On the generalized joint linear complexity profile of a class of nonlinear pseudorandom multisequences. Advances in Mathematics of Communications, 2010, 4 (3) : 369-379. doi: 10.3934/amc.2010.4.369 |
| [19] |
Yi Xu, Wenyu Sun. A filter successive linear programming method for nonlinear semidefinite programming problems. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 193-206. doi: 10.3934/naco.2012.2.193 |
| [20] |
Shudi Yang, Xiangli Kong, Xueying Shi. Complete weight enumerators of a class of linear codes over finite fields. Advances in Mathematics of Communications, 2021, 15 (1) : 99-112. doi: 10.3934/amc.2020045 |
Impact Factor:
Tools
Metrics
Other articles
by authors
[Back to Top]