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

Jerzy Filar, Michael Haythorpe, Richard Taylor

    Research output: Contribution to journalArticlepeer-review


    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.

    Original languageEnglish
    Pages (from-to)1-16
    Number of pages16
    JournalNumerical Algebra, Control and Optimization
    Issue number1
    Publication statusPublished - Mar 2018


    • Complexity
    • Integer programming
    • Karp
    • Linear
    • NP-complete
    • Reduction


    Dive into the research topics of 'Linearly-growing reductions of Karp's 21 NP-complete problems'. Together they form a unique fingerprint.

    Cite this