  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.
