Graph Theory and
Applications
Lecture 7: TSP and related problems
Ta Viet Cuong, Ph.D
HMI laboratory, FIT-UET
Today
I. Review
II. Cover set and Maximum Independent Set
III. TSP
Homework
2
(s-t) Cuts
Definition: An (s-t) cut of graph G = <V, E> in a way to partition V into
two disjoint set A, B with s in A and t in B
3
Flow value lemma
Let f be any flow, and let (A, B) be any s-t cut, then the value of f equal the flow leaving A
Proof: (by induction)
- Base case A = {s}
- Assume |A| < k
4
Optimality Conditions for Max Flow
Let f be a flow in a graph G, the following are equivalent:
a) f is maximum flow
b) there is an (s, t)-cut (A, B) such that the value of f equals the capacity
of (A, B)
c) there is no s-t path in the residual network of G(f)
Proof sketch: (2) -> (1) -> (3) -> (2)
5
Algorithms
6
Application 1: Bipartite Matching
Students and jobs:
- Company only has one job
- Student can join one company
Can you find a match:
- Between student and company
7
Application 1: Bipartite Matching
Matching: Given a Bipartite Graph, we want to associate vertex from L to R as many as
possible with a constraint:
- Each vertex is matched to one and only one vertex of the other side
8
Variants of Flow problems
There are several variants of the flow problems:
- Multi sources/sinks flow
- Flow with vertex capacity
- Flow with max/min constraint
- Max flow min-cost problems
- Max-flow problem can be augmented by disjunctive constraints
9
Excercise
Given a chess board of size NxN, there is K-Pawn place on the tables. Find the maximum
number of Rook that can place in the board with the constraint that: no Rook can attack
each others.
10
Today
I. Review
II. Cover set and Maximum Independent Set
III. TSP
Homework
11
Minimum Cover set
Give a undirected graph G = <V, E>, a vertex cover is a set of vertices V’ where every
edges of E has at least one endpoint in V’
12
Minimum Cover set
Trivial Cover: we can use V as a cover set
We want to find the cover set with smallest possible size
13
Maximum Independent Set
Give a undirected graph G = <V, E>, a vertex cover is a set of vertices V’ where there is no
edge in E connect two vertices in V’
14
Maximum Independent Set
We want to maximize the set of independent set
15
Properties
- The complement of a vertex cover is an independent set
- The minimum number of vertex cover plus the maximum number of independent set
is the number of vertices |V|
Exact solutions:
- For bipartite graph, the vertex cover is equal the maximum matching number
- For tree graph, we can go from leaf to find the minimum number of vertex cover
16
Solution
The minimum vertex cover set is a NP-complete in general.
Exhaustive search approach: can try 2kNO(1) approach: test all the cover set of k vertex
Improve exhaustive search approach:
- With each vertex v, choose v or choose all of the neighbors of v
17
Approximate solution
We can based on the matching properties:
- Find a maximal matching M, then using all the vertices of edge in M
18
Homework
Find the maximum matching M and its related cover set. Which is the optimal cover set?
19
Today
I. Review
II. Cover set and Maximum Independent Set
III. TSP
Homework
20
Travelling Salesman Problem (TSP)
One of the most famous problem in graph domain:
21
Travelling Salesman Problem
Formal definition:
- Give a undirected graph G = <V, E>, for e in E, the cost
- A TSP tour is a simple cycle that visited each vertex once
The goal is: find the cycle that have the minimum cost
22
Example 1:
The tour through the number of positions: it started as far as 1832 as a tour through some
cities in Germany and Switzerland
23
Example 2:
Task scheduler:
- There is a number of tasks
- The tasks can be set up with a cost: locating
resources, workers
- The cost is depending on the previous tasks
Find the optimal order of tasks:
- A hard disk with a number of read requests
24
Theorem
Theorem: If P != NP, then there is no 𝜶-approximation algorithm for the for the TSP, for
any 𝜶
𝜶-approximation: for a minimization problem runs in polynomial time and always returns
a feasible solution with cost at most α times the minimum possible
Proof: Using reduction n from the Hamiltonian cycle problem
Short: The TSP is hard, even to approximate
25
Theorem
Theorem: If P != NP, then there is no 𝜶-approximation algorithm for the for the TSP, for
any 𝜶
Proof: Using reduction n from the Hamiltonian cycle problem
26
Theorem
Theorem: If P != NP, then there is no 𝜶-approximation algorithm for the for the TSP, for
any 𝜶
𝜶-approximation: for a minimization problem runs in polynomial time and always returns
a feasible solution with cost at most α times the minimum possible
Short: The TSP is hard, even to approximate
27
Version of TSP
+ Metric TSP: The edge costs satisfy the triangle inequality
+ Point TSP: the set of v is set on the plane, with the cost is the distance
28
The Minimum Spanning Tree heuristics
Lenma: For every instance G = (V, E, c), the minimum-possible cost of a TSP tour is at
least the cost of a minimum spanning tree (MST).
Proof: you can try to reduce an edge from the TSP
29
The Minimum Spanning Tree heuristics
30
The Minimum Spanning Tree heuristics
d - output of the algorithms
e - optimal solution
31
The Minimum Spanning Tree heuristics
Theorem: The MST heuristic is a 2-approximation algorithm for the metric TSP.
Or:
We can find a TSP tour that is less than 2*OPTIMAL TSP
Proof: (we need double the tree)
32
The Minimum Spanning Tree heuristics
We do not need to double the edges:
33
The Minimum Spanning Tree heuristics
Theorem: the above algorithms is an 3/2-approximation algorithm for the metric TSP
Some notes:
- It is the best approximation algorithm to this day for metric TSP
- If possible, there is some conjecture that can results in a 4/3-approximation
- In July 2020 however, Karlin, Klein, and Gharan released a preprint in which they
introduced a novel approximation algorithm and claimed that its approximation ratio
is 1.5 − 10−36
34
Homework
Improve the TSP tour of the following graph, using block distance
35
