TNK104 Applied Optimization

Problem Complexity: Detailed

​

Lecture 9

based on the slides provided by Nikolaos Pappas

Tatiana Polishchuk,

Associate Professor,

Linköping University, KTS

https://www.itn.liu.se/~tatpo46/

​

Problem Complexity: Preliminaries

2

TNK104 Applied Optimization I

• There are fast algorithms for solving some combinatorial optimization problems (e.g., shortest path and MST) to global optimum
• For other problems, currently available exact algorithms are “not fast”, although they scale much better than brute force
• Fast (efficient) and exact (correct) algorithms for all combinatorial optimization problems?

​

Maybe these algorithms are there, just waiting to be discovered, or, maybe they don’t exist at all???

Problem Complexity: Preliminaries (cont’d)

3

TNK104 Applied Optimization I

• Are all combinatorial optimization problems equally easy/difficult? A: Not likely. Some appear to be easier than others.

​

• What is “easy”?

A: There is an efficient/fast algorithm that always returns the exact optimum

​

• What is “efficient/fast”?

A: The algorithm’s running time (in the number of elementary calculations) is bounded by a polynomial in the size of problem representation.

​

Consider a complete graph of n nodes:

• Shortest path: The classical Dijkstra’s algorithm runs in kn² time, where

k is some constant ! O(n²)

• MST: The Prim’s algorithm runs in O(n³) under a straightforward implementation
• Traveling salesman: ???

​

Big-O notation

Problem Class NP

4

TNK104 Applied Optimization I

• Decision problem: A problem/question with a yes/no answer

Consider a graph:

• Is there a path connecting nodes s and t?
• Is there a TSP tour with total cost less than a given value k?
• Is there a feasible vertex coloring using at most k colors?
• NP*: The class of decision problems with the property that, for every yes-instance, there is a “short” proof, that is, a certificate of the yes- answer can be checked/verified in polynomial time

All the combinatorial optimization problems we have discussed

have their decision problems in NP*.

Note: NP stands for nondeterministic polynomial time

NP

Class P

5

TNK104 Applied Optimization I

• P is the class of decision problems for which there exist exact and polynomial time algorithms

NP

​

P

• Examples of problems (or, their decision problems) in P:
• Determining if a number is prime
• Determining if a graph is connected
• Shortest path
• Maximum flow / minimum cut
• Minimum spanning tree
• Linear programming (note: the proof was not built on the simplex algorithm)

Class NP-Complete (NP-C)

6

TNK104 Applied Optimization I

• NP-C: The class of most difficult NP-problems
• A more precise definition: A problem is in NP-C if every problem in NP can be reduced to it in polynomial time

​

NP

NP-C

P

→ If we can solve one single NP-C problem in polynomial time, we can solve all problems in NP in polynomial time!

• If this would be the case, then P = NP

Class NP-Complete (NP-C) (cont’d)

7

TNK104 Applied Optimization I

• Many comb. opt. problems have their decision versions in NP-C
• Knapsack problem
• Vertex coloring

• Clique
• Set covering
• Set partitioning
• Steiner tree
• Dominating set
• Integer programming

and many more!

M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, 1979.

​

​

• Are there NP-problems that are neither in P nor NP-C? Yes, unless P = NP (Ladner’s theorem)

NP

NP-C

P

Karp’s 21 NP-Complete Problems

8

TNK104 Applied Optimization I

In 1972, R. Karp discussed the NP-completeness of 21 problems, starting from SAT

Satisfiability Problem (SAT)

9

TNK104 Applied Optimization I

Satisfiability Problem (SAT) (cont’d)

10

TNK104 Applied Optimization I

• If we can show that SAT is reducible to problem A, then A is NP-C
• If A is NP-C and we can reduce A to problem B, then B is NP-C
• and so on …

• Cook’s theorem (1971): SAT is NP-complete

This is the first problem proved to be NP-C (the concept didn’t exist before the theorem)

​

→ All problems in NP can be reduced (polynomially) to SAT

​

NP

SAT

A

11

TNK104 Applied Optimization I

P = NP?

NP

P

NP-C

We still don’t know.

Lance Fortnow, "The Status of the P Versus NP Problem", Communications of the ACM, Vol. 52 No. 9, Pages 78-86

Class NP-Hard

12

TNK104 Applied Optimization I

• NP-hard: at least as difficult as NP-C

​

​

NP

NP-C

P

NP-hard

• NP-hard problems are not necessarily in NP
• Similar to NP-C, if we can solve an NP-hard problem in polynomial time, then P = NP
• If an optimization problem has its decision problem in NP-C, then the optimization problem itself is NP-hard

→ Finding the optimum to, for example, integer programming, traveling salesman, graph coloring, set covering, and Steiner tree, is NP-hard

How Should We Interpret the Complexity Results?

13

TNK104 Applied Optimization I

L. Wolsey, Integer Programming, John Wiley & Sons, 1998, pp. 87-88:

​

“A pessimist might say that as most problems appear to be hard,… we have no hope of solving instances of large size …, and so we should give up.

​

A mathematician (optimist) might set out to become famous by proving that P=NP

​

A mathematician (pessimist) might set out to become famous by proving that P ≠ NP

​

A mathematician (thoughtful) might decide to ask a different question: Can I find an algorithm that is guaranteed to find a solution “close to optimal” in polynomial time in all cases?

​

A probabilist (thoughtful) might also ask a different question: Can I find an algorithm that runs in polynomial time and that is guaranteed to find an optimal or “close to optimal” solution with high probability?

How Should We Interpret the Complexity Results? (cont’d)

14

TNK104 Applied Optimization I

An engineer would start looking for a heuristic algorithm that produces practically usable solution

​

Your boss may say: I don’t care a damn about integer programming theory. You just worry about our scheduling problem. Give me a feasible production schedule for tomorrow…

​

A struggling professor might say: Great, previously I was trying to develop one algorithm to solve all integer programs, and publishing one paper every two years explaining why I was not succeeding. Now I know that I might as well study each NP problem individually. As there are thousands of them, I should be able to write twenty papers a year.

​

Needless to say they are nearly all right.”

How to Relate Problems to Each Other in Complexity?

15

TNK104 Applied Optimization I

→ An algorithm for B works also for A

→ B is at least as difficult as A, or, equivalently, A is at least as easy as B

​

​

Thus

​

• If A is NP-hard, then B is NP-hard
• If B is P, then A is P

A

B

Consider two problems A and B, if A can be (polynomial-time) reduced to B

Examples of Problem Reduction: Bipartite Matching

16

TNK104 Applied Optimization I

Bipartite matching

Instance: A bipartite graph G = (V₁, V₂, E)

Find a matching with maximum number of edges

(A matching is a set of edges without any node in common)

Example of Problem Reduction: Bipartite Matching (cont’d)

17

TNK104 Applied Optimization I

Relation to maximum flow:

Introduce two nodes s and t, and connect them to V₁ and V₂, respectively, with edge capacity one

Set also the capacity of the original edges (arcs) to one

The maximum flow from s to t provides the optimal matching

s

t

Examples of Problem Reduction: Degree-Constrained MST

18

TNK104 Applied Optimization I

Degree-constrained MST (DMST)

Examples of Problem Reduction: Degree-Constrained MST (cont’d)

19

TNK104 Applied Optimization I

Hamiltonian path

Equivalent to Hamiltonian cycle that is among Karp’s 21 NP-complete problems

Instance: A graph G = (V, E)

Is there a path visiting each node exactly once?

A graph without any Hamiltonian path A graph with a Hamiltonian path

Examples of Problem Reduction: Degree-Constrained MST (cont’d)

20

TNK104 Applied Optimization I

Hamiltonian path

DMST

DMST is NP-C (at least as difficult as Hamiltonian path)

For d = 2, DMST is . . . . . . a path.

Existence of Hamiltonian path ↔ Existence of a DMST with d = 2

Special Cases of NP-C Problems: Examples

21

TNK104 Applied Optimization I

Hamiltonian path is among Karp’s 21 NP-complete problems

• Suppose the graph is a cycle. Does the problem remain NP-C?

Knapsack is also among Karp’s 21 NP-complete problems

• Consider binary knapsack where all items have equal value but different weights. Does the problem remain NP-C?

​

​

What is the lesson learned?

Self-Study Material

Textbook:

Chapter 34, NP-completeness

​

​

MIT OCW video lectures:

​

#16 https://youtu.be/eHZifpgyH_4

​

​

Youtube videos:

​

Big O notation: https://youtu.be/zUUkiEllHG0

Complexity theory: https://youtu.be/u2DLlNQiPB4

Bipartite matchings https://youtu.be/GhjwOiJ4SqU

Satisfiability Problem https://youtu.be/SAXGKCnOuP8

​

​

​

​