Industrial problems and polynomial reduction 101

I. Reduction and presentation of Karp's 21 problems

Satisfiability
- Click
  - Set packing
  - Vertex cover
    - Set covering
    - Feedback arc set
    - Feedback node set
    - Directed hamiltonian circuit
      - Undirected Hamiltonian circuit
0-1 interger programming
3-SAT
- Chromatic number
  - Click cover
  - Exact cover
    - 3D Matching
    - Steiner tree
    - Hitting set
    - Knapsack
      - Job sequencing
      - Partition
        Max-cut

Contents

Polynomial reduction

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

Polynomial complexity

The problems are decidable, that is, 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.

a algorithm is of polynomial complexity if there exists a polynomial 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 is of 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 influence the complexity.

Polynomial reduction

A decision problem P reduces to a decision problem P 'if there exists a polynomial algorithm R which 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.