08/09/2024

Industrial problems and polynomial reduction 101

• 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

Toggle

Polynomial reduction

The problems of operations research, and more generally of decision support are often Np-complete, that is to say that we do not know 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

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 entry u of P into an entry 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.