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

Jerzy A. Filar; Michael Haythorpe; Richard Taylor

doi:10.3934/naco.2018001

Article Contents

2018, Volume 8, Issue 1: 1-16. Doi: 10.3934/naco.2018001

This issue Previous Article Next Article Fourier-splitting method for solving hyperbolic LQR problems

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

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

Received: September 2015

Revised: January 2018

Published: March 2018

Abstract Full Text(HTML) Figure(1) Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 68Q15; Secondary: 90C10.

Citation:

Full Text(HTML)

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

Download: Full-size image PowerPoint slide

Related Papers

Cited by

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.