Polynomial reduction

21 problems of Karp :

  • Satisfiability
    • Clique
      • Set packing
      • Vertex cover
        • Set covering
        • Feedback arc set
        • Feedback node set
        • Directed hamiltonian circuit
          • Undirected hamiltonien circuit
  • 0-1 integer programming
  • 3-SAT
    • Chromatic number
      • Clique cover
      • Exact cover
        • Matching 3D
        • Steiner tree
        • Hitting set
        • Knapsack or in PDF
          • Job sequencing
          • Partition
            • Max-cut

The problems of operational research, and more generally of the decision making, are often Np-complete, that is to say that we do not know any algorithms allowing to find an optimal solution in polynomial time, but we know how to obtain a feasible solution in polynomial time.

Polynomial complexity

The problems are decidable, the problem can be formulated in such a way that the answer is Yes or No. The complexity of its problems will be considered in the worst case.

An algorithmhave a polynomial complexity if there exists a polynom P such that the number of elementary instructions carried out during its execution on an instance of size n is at most P(n). A problem have a polynomial complexity if there is an algorithm of polynomial complexity solving it. It is important to emphasize that the representation of the data structures used does not affect complexity.

Polynomial reduction

A decision problem P is reduced to a decision problem P’ if there exists a polynomial algorithm R that transforms any input u of P into an input u’ = R(u) of P’ such that u∈YES(P) ⇔ u’∈YES(P’).


This suggests the following implication: if there is a polynomial algorithm for P’, then there is also one for P.