Lecture 13: Summary
The University of Sydney
Page 1
How to design algorithms
Step 1: Understand problem
Step 4: Better understanding of problem
Step 2: Start with simple alg. Step 5: Improved alg.
Step 3: Does it work? Is it fast?
No Yes
The University of Sydney
Page 2
Problem
Algorithm
Analysis
DONE!
comp3027 Overview I
Graphs
Definitions and properties
Graph traversal: BFS and DFS
Applications: min-link path, bipartitness
Greedy algorithms
The University of Sydney
Page 3
Greedy technique
Standard correctness proof: exchange argument Applications: Scheduling, MST, Dijkstra (incl. properties)
comp3027 Overview II
Divide-and-Conquer algorithms
General technique: break, solve and combine
Recursion: How to state and solve a recursion Standard correctness proof: Induction
Applications: Mergesort, Inversions,
The University of Sydney
Page 4
comp3027 Overview III
Dynamic programming
General technique: break, solve, combine
Define states
State recursion
Correctness proof: Induction
Applications: Knapsack, weighted scheduling, RNA, Bellman-Ford,
Flow networks
The University of Sydney
Page 5
Properties of flow network: max flow, min cut, integer lemma, General technique: reduce to a flow network
Correctness proof: Solution for X U Solution for FN Applications: matching, edge-disjoint paths, circulation,
comp3027 Overview IV
Complexity
Polynomial-time reductions!
Classes: P, NP, NP-complete, NP-hard
How to prove that a problem belongs to P/NP/NP-complete Understand the NP-complete problems in lecture 10.
Coping with hardness
Understand the basic concepts:
Exponential time algorithms Restricted instances
Approximation algorithms
The University of Sydney
Page 6
Main Themes
Induction:
Proof technique
Algorithm design method: Divide-and-conquer and DP
Reduction:
Algorithm design: Reduction to flows
Hardness: Reduction from NP-complete problems
The University of Sydney
Page 7
Lecture 2: Graphs
Joachim Gudmundsson
The University of Sydney Page 8
Lecture 2: Graphs
Definitions
Representations
The University of Sydney
Page 9
Graph traversal:
Breadth First Search (incl. layers)
Depth First Search
Applications: bipartiteness, min-link paths,
Basic Definitions
Graphs (directed/undirected)
Tree (rooted/unrooted)
Path (simple), connectivity, cycle
The University of Sydney
Page 10
Trees
Definition: An undirected graph is a tree if it is connected and
does not contain a cycle.
Number of edges in a tree?
Theorem: Let G be an undirected graph on n nodes. Any two of the following statements imply the third.
G is connected.
G does not contain a cycle. G has n-1 edges.
The University of Sydney Page 11
Graph traversal: Breadth First Search
BFS intuition. Explore outward from s in all possible directions, adding nodes one layer at a time.
s
L n-1
BFS algorithm.
L0={s}.
L1 = all neighbors of L0.
L2 =allnodesthatdonotbelongtoL0 orL1,andthathaveanedgetoa node in L1.
Li+1 = all nodes that do not belong to an earlier layer, and that have an edge to a node in Li.
Theorem: For each i, Li consists of all nodes at distance exactly i from s. There is a path from s to t iff t appears in some layer.
The University of Sydney
Page 12
L1
L2
Application: BFS applied to Shortest paths
The shortest path between two nodes u,v in an unweighted graph G, is the path with the minimum number of edges that connects u and v (if it exists).
Compute the shortest paths from a given node s to all other nodes using BFS.
The University of Sydney
Page 13
Application: BFS applied to bipartiteness
Lemma: If a graph G is bipartite, it cannot contain an odd length
cycle.
Lemma: Let G be a connected graph, and let L0, , Lk be the layers produced by BFS starting at node s. Exactly one of the following holds.
(i) No edge of G joins two nodes of the same layer, and G is bipartite.
(ii) An edge of G joins two nodes of the same layer, and G contains an odd-length cycle (and hence is not bipartite).
L1 L2 L3 L1 L2 L3
The University of Sydney Case (i) Case (ii) Page 14
Lecture 3:
Greedy algorithms
The University of Sydney
Page 15
Greedy algorithms
The University of Sydney
Page 16
A greedy algorithm is an algorithm that follows the problem solving heuristic of making the locally optimal choice at each stage with the hope of finding a global optimum.
Greedy
Examples of problems that can be solved using a greedy approach:
Interval scheduling/partitioning
Scheduling to minimize lateness
Shortest path
Minimum spanning trees
The University of Sydney
Page 17
Interval Scheduling
Interval scheduling.
Input: Set of n jobs. Each job i starts at time sj and finishes at time fj.
Two jobs are compatible if they dont overlap in time.
Goal: find maximum subset of mutually compatible jobs.
b
a
c
d
e
f
g
h
0 1 2 3 4 5 6 7 8 9 10 11 The University of Sydney
Time
Page 18
Interval Scheduling: Greedy Algorithm
Greedy algorithm. Consider jobs in increasing order of finish time. Take each job provided it is compatible with the ones already taken.
Sort jobs by finish times so that f1 f2 fn. jobs selected
A
for j = 1 to n {
if (job j compatible with A) A A E {j}
}
return A
Implementation. O(n log n).
Rememberjobj*thatwasaddedlasttoA. Job j is compatible with A if sj 3 fj*.
The University of Sydney Page 19
Greedy algorithms: Analysis
1. DefineyoursolutionXandanoptimalsolutionOPT.
2. Compare solutions. If X1OPT then they must differ in a
specific way.
3. Exchange pieces. Transform OPT by exchanging some piece of OPT for some piece of X.
4. Iterate. Argue optimality.
The University of Sydney
Page 20
Interval Scheduling: Recap of Exchange Argument
Greedy: OPT:
We have an optimal solution that is closer to the greedy solution.
Start the argument over again, but now the first (r+1) elements of the greedy solution and the optimal solution are identical.
Continue iteratively until the optimal solution is transformed into the greedy solution without increasing the cost.
i1
i1
ir
ir+1
J1
J2
Jr
Jr+1
The University of Sydney Page 21
Minimum Spanning Tree*
Minimum spanning tree (MST). Given a connected graph G = (V, E) with real-valued edge weights ce, an MST is a subset of the edges
T I E such that T is a spanning tree whose sum of edge weights is minimized.
4 24 4 62396 9
16
18
511 511
The University of Sydney
Page 22
8 14 7 8 7 10
21
G = (V, E)
T, SeIT ce = 50
MST properties*
Simplifying assumption. All edge costs ce are distinct.
Cut property. Let S be any subset of nodes, and let e be the min cost edge with exactly one endpoint in S. Then the MST contains e.
Cycle property. Let C be any cycle, and let f be the max cost edge belonging to C. Then the MST does not contain f.
S
e
e is in the MST
f
C
The University of Sydney
Page 23
f is not in the MST
Prims Algorithm*
Prims algorithm. [Jarnik 1930, Dijkstra 1957, Prim 1959] Initialize S = any node.
Apply cut property to S.
Add min cost edge in cutset corresponding to S to T, and add one new
explored node u to S.
S
The University of Sydney
Page 24
Naive implementation: O(nm) time Need a Union-Find data structure to efficiently keep track of connected components
Kruskals Algorithm*
Kruskals algorithm. [Kruskal, 1956] Consider edges in ascending order of weight.
Case 1: If adding e to T creates a cycle, discard e according to cycle property.
Case 2: Otherwise, insert e = (u, v) into T according to cut property where S = set of nodes in us connected component.
v
u
S
e
e
The University of Sydney
Case 1
Case 2
Page 25
Shortest Path Problem*
Shortest path network.
Directed graph G = (V, E).
Source s, destination t.
Length !e = length of edge e.
Shortest path problem: find shortest directed path from s to t. cost of path = sum of edge costs in path
9 s
15
2 23 3 18
The University of Sydney
5
7 44 t
Page 26
14
6
6
11 4 19
5
20 16 6
2
Cost of path s-2-3-5-t = 9+23+2+16
= 50
30
Dijkstras Algorithm*
Compute shortest path distances to every vertex. Dijkstras algorithm.
Maintain a set of explored nodes S for which we have determined the shortest path distance d(u) from s to u.
Initialize S = {s}, d(s) = 0.
Repeatedly choose unexplored node v which minimizes
p(v) = min
e = (u,v) : uIS
add v to S, and set d(v) = p(v).
d(u) + !e ,
!e u
shortest path to some u in explored part, followed by a single edge (u, v)
v
d(u)
S
s
The University of Sydney
Page 27
Summary: Greedy algorithms
A greedy algorithm is an algorithm that follows the problem solving heuristic of making the locally optimal choice at each stage with the hope of finding a global optimum.
Problems
Interval scheduling/partitioning
Scheduling: minimize lateness
Minimum spanning tree (Prims algorithm)
Shortest path in graphs (Dijkstras algorithms)
The University of Sydney
Page 28
Lecture 4:
Divide & Conquer
The University of Sydney
Page 29
Fast Fourier Transform
Divide-and-Conquer
The divide-and-conquer strategy solves a problem by:
1. Breaking it into subproblems that are themselves smaller
instances of the same type of the original problem. 2. Recursively solving these subproblems.
3. Appropriately combining (merging) their answers.
Most common usage.
Break up problem of size n into two equal parts of size 12n. Solve two parts recursively.
Combine two solutions into overall solution in linear time.
The University of Sydney
Page 30
Mergesort
Mergesort.
Divide array into two halves.
Recursively sort each half.
Merge two halves to make sorted whole.
Jon von Neumann (1945)
A
L
G
O
R
I
T
H
M
S
divide
O(1)
A
L
G
O
R
I
T
H
M
S
sort
2T(n/2)
A
G
L
O
R
H
I
M
S
T
merge
O(n)
A
G
H
I
L
M
O
R
S
T
The University of Sydney
Page 31
Merging
Merging. Combine two pre-sorted lists into a sorted whole.
How to merge efficiently?
Linear number of comparisons. Use temporary array.
A
G
L
O
R
H
I
M
S
T
A
G
H
I
The University of Sydney
Page 32
Mergesort
Mergesort.
Divide array into two halves.
Recursively sort each half.
Merge two halves to make sorted whole.
Jon von Neumann (1945)
A
L
G
O
R
I
T
H
M
S
divide
O(1)
A
L
G
O
R
I
T
H
M
S
sort
2T(n/2)
A
G
L
O
R
H
I
M
S
T
merge
O(n)
A
G
H
I
L
M
O
R
S
T
The University of Sydney T(n) = O(n) + 2T(n/2) Page 33
Counting Inversions: Divide-and-Conquer
Divide-and-conquer.
Divide: separate list into two pieces.
Conquer: recursively count inversions in each half.
Combine: count inversions where ai and aj are in different halves, and
return sum of three quantities.
1
5
4
8
10
2
6
9
12
11
3
7
1
5
4
8
10
2
6
9
12
11
3
7
5 blue-blue inversions 8 green-green inversions
9 blue-green inversions
5-3, 4-3, 8-6, 8-3, 8-7, 10-6, 10-9, 10-3, 10-7
Total = 5 + 8 + 9 = 22.
Divide: O(1). Conquer: 2T(n/2)
Combine: ???
The University of Sydney
Page 34
Counting Inversions: Combine
Combine: count blue-green inversions
Assume each half is sorted.
Count inversions where ai and aj are in different halves. Merge two sorted halves into sorted whole.
3
7
10
14
18
19
2
11
16
17
23
25
The University of Sydney
Page 35
632200
5 blue-blue inversions 8 green-green inversions
How many blue-green inversions?
Counting Inversions: Combine
Combine: count blue-green inversions
Assume each half is sorted.
Count inversions where ai and aj are in different halves. Merge two sorted halves into sorted whole.
632200
13blue-greeninversions: 6+3+2+2+0+0
Count: O(n) Merge: O(n)
3
7
10
14
18
19
2
11
16
17
23
25
2
3
7
10
11
14
16
17
18
19
23
25
Time: T(n) = 2T(n/2) + O(n) = O(n log n) The University of Sydney
Page 36
Proof by unrolling*
ic
T(n)=ii 2T (n / 2) + cn
if n=1 otherwise
ii%$# ! sorting both halves merging
T(n)
T(n/2)
T(n/4) T(n/4)
T(n/2k)
T(1) T(1) T(1) T(1)
1 (of size n) cn
2 (of size n/2) cn
4 (of size n/4) cn
log2n
2k (of size n/2k) cn
n(of size 1) cn cn log2n Page 37
T(n/4)
T(n/2) T(n/4)
T(1) T(1)
The University of Sydney
T(1) T(1)
The master method*
The master method applies to recurrences of the form
T(n) = aT(n/b) + f(n) ,
where a 3 1, b > 1, and f is asymptotically positive.
The University of Sydney Page 38
T(n) = aT(n/b) + f(n)
size n cost f(n)
size n/b cost af(n/b)
size (n/b2) cost a2f(n/b2)
size 1
cost wT(1)
Branching factor a
height logb n
The University of Sydney
width w = alogb n = nlogb a
Page 39
Summary: Divide-and-Conquer
Algorithm:
Break up problem into several parts.
Solve each part recursively.
Combine solutions to sub-problems into overall solution.
Complexity analysis: Solve recurrence Unrolling
Master Method
Correctness: Induction
Problems
The University of Sydney
Merge Sort Closest pair Multiplication
Page 40
Lectures 6-7:
Dynamic Programming
The University of Sydney
Page 41
Fast Fourier Transform
Dynamic programming
1. Definesubproblems.
2. Write a recurrence (include base cases).
3. Prove that the recurrence is correct. Usually case-by-case. May
require an induction proof, but usually easy to prove.
4. Prove the algorithm evaluates the recurrence. Values computed in correct order.
5. Prove the algorithm is correct. The University of Sydney
Page 42
42
Weighted Interval Scheduling
Weighted interval scheduling problem.
Job j starts at sj, finishes at fj, and has weight or value vj .
Two jobs compatible if they dont overlap.
Goal: find maximum weight subset of mutually compatible jobs.
b
a
c
d
e
f
g
h
0 1 2 3 4 5 6 7 8 9 10 11 The University of Sydney
Time
Page 43
Weighted Interval Scheduling
Notation. Label jobs by finishing time: f1 f2 . . . fn .
Def. p(j) = largest index i < j such that job i is compatible with j. Ex: p(8)=5,p(7)=3,p(2)=0. 1 2 3 4 5 6 7 80 1 2 3 4 5 6 7 8 9 10 11 The University of SydneyTimePage 44 Dynamic Programming Step 1 Step 1: Define subproblemsOPT(j) = value of optimal solution to the problem consisting of job requests 1, 2, …, j.The University of SydneyPage 45 Dynamic Programming Step 2 Step 2: Find recurrences Case 1: OPT selects job j. can’tuseincompatiblejobs{p(j)+1,p(j)+2,…,j-1} must include optimal solution to problem consisting of remaining compatible jobs 1, 2, …, p(j) Case 2: OPT does not select job j. must include optimal solution to problem consisting ofremaining compatible jobs 1, 2, …, j-1OPT(j) = max {vj + OPT (p(j)), OPT(j-1)} Case 1 Case 2The University of SydneyPage 46 Dynamic Programming Step 3 Step 3: Solve the base casesOPT(0) = 0 OPT(j)=ii 0 if j=0 imax{vj +OPT(p(j)), OPT(j-1)} otherwiseThe University of SydneyPage 47Done…more or less Knapsack Problem Knapsackproblem. Givennobjectsanda”knapsack.” Item i weighs wi > 0 kilograms and has value vi > 0. KnapsackhascapacityofWkilograms.
Goal: fill knapsack so as to maximize total value.
W = 11
Item
Value
Weight
1
1
1
2
6
2
3
18
5
4
22
6
5
28
7
The University of Sydney
Page 48
Dynamic Programming Step 1 Step 1: Define subproblems
OPT(i, w) = max profit with subset of items 1, , i with weight limit w.
The University of Sydney
Page 49
Dynamic Programming Step 2 Step 2: Find recurrences
Case 1: OPT does not select item i.
OPT selects best of { 1, 2, , i-1 } using weight limit w
Case 2: OPT selects item i.
newweightlimit=wwi
OPT selects best of { 1, 2, , i1 } using this new weight limit
If wi>w
OPT(i,w) = OPT (i-1,w)
otherwise
OPT(i,w) = max { vi + OPT (i-1,w-wi), OPT(i-1,w) }
The University of Sydney
Page 50
Recap: Dynamic Programming Step 3 Step 3: Solve the base cases
OPT(0,w) = 0
i0 if i=0 OPT(i,w)=iOPT(i-1,w) if i>0andw >w
i
i
imax{OPT(i-1,w),v+OPT(i-1,w-w)} otherwise iii
The University of Sydney
Page 51
Donemore or less
Knapsack Problem: Running Time
Running time: Q(nW).
Not polynomial in input size!
Pseudo-polynomial.
Decision version of Knapsack is NP-complete.
Observe that in the reduction of vertex cover to subset sum, the numbers are exponential in the size of the graph!
The University of Sydney Page 52
Vertex Cover Reduces to Subset Sum
Proof: Given an instance (G, k) of VERTEX-COVER, construct an instance (S, t) of SUBSET-SUM that has a subset of S summing to t iff G has a vertex cover of
size at least k.
Number edges from 0 to |E|-1. Set S of integers:
For the i-th edge, add an integer bi
For each vertex v, add an integer av
bi = 4i
av = 4|E| + X 4i
0
xyz
1
t = k 4|E| +
The University of Sydney i=0
2 4i
Page 53
i:i-th edge is incident to v
az = 1104 ay = 1114
ax = 1014
|EX| 1
t = 1224
k=1
b0 = 0014
b1 = 0104
Shortest Paths
Shortest path problem. Given a directed graph G = (V, E), with edge weights cvw, find shortest path from node s to node t.
allow negative weights
2 10 3
9
s
18
30
5
-8
20
7
6
6
15
-16 6
4 19
6 16
t
11
44
The University of Sydney
Page 54
Shortest Paths: Dynamic Programming
Step 1: OPT(i, v) = length of shortest v-t path P using at most i edges.
Step 2:
Case 1: P uses at most i-1 edges. OPT(i, v) = OPT(i-1, v)
Case 2: P uses exactly i edges.
if (v, w) is first edge, then OPT uses (v, w), and then selects
best w-t path using at most i-1 edges
Step 3: OPT(0,t) = 0 and OPT(0,v=t) =
0 if i=0 and v=t OPT(i,v) = if i=0 and v=t
min{OPT(i-1,v), min [OPT(i-1,w)+cvw] } otherwise
The University of Sydney
(v,w)IE
Page 55
Dynamic Programming Summary I
Algorithm 3 steps:
1. Definingsubproblems
The University of Sydney
Page 56
2. 3.
Finding recurrences Solving the base cases
56
Dynamic Programming Summary II
1D dynamic programming
Weighted interval scheduling
Segmented Least Squares
Maximum-sum contiguous subarray Longest increasing subsequence
2D dynamic programming Knapsack
Shortest path
Dynamic programming over intervals
RNA Secondary Structure The University of Sydney
Page 57
Lectures 8-9: Flow networks
The University of Sydney
Page 58
Flow network*
Abstraction for material flowing through the edges. G = (V, E) = directed graph, no parallel edges.
Two distinguished nodes: s = source, t = sink.
c(e) = capacity of edge e.
295
10
15 15
sources 5 3 8 6 10 tsink
4
10
capacity
The University of Sydney
Page 59
15
46
10
15 4 30 7
Flows*
Definition: An s-t flow is a function that satisfies: For each e I E: 0 f(e) c(e)
(capacity) (conservation)
a f (e) . e out of s
6
10
For each v I V {s, t}: a f(e) = e in to v
Definition: The value of a flow f is: 6
a f(e) e out of v
2 9 5
v( f ) =
10
10
0
15 15 0
44 388
s 5 3 8 6 10 t
capacity
flow
15
11
1
40 6 150
11
10
10
The University of Sydney
4 30 7
Value =P2ag4e 60
Maximum Flow Problem*
Max flow problem. Find s-t flow of maximum value.
9
2 9 5
10
10
1
15 15 0
9
10
40 489
s 5 3 8 6 10 t
capacity
flow
15
14
4
40 6 150
14
10
10
The University of Sydney
4 30 7
Value =P2ag8e 61
Cuts*
Definitions:
Ans-tcutisapartition(A,B)ofVwithsIAandtIB.
The capacity of a cut (A, B) is: cap(A, B) = 295
a c(e) e out of A
10
4
15 15
10
s 5 3 8 6 10 t A
15
46
10
15 4 30 7
Capacity = 10 + 5 + 15
The University of Sydney
= 30
Page 62
Cuts
Definitions:
Ans-tcutisapartition(A,B)ofVwithsIAandtIB.
The capacity of a cut (A, B) is: cap(A, B) = 2 9 5
10
a c(e) e out of A
15 15
s 5 3 8 6 10 t
4
10
A
The University of Sydney
15 4 30 7
15
46
10
Capacity = 9 + 15 + 8 + 30
= 62
Page 63
Flows and Cuts*
Flow value lemma. Let f be any flow, and let (A, B) be any s-t cut. Then, the net flow sent across the cut is equal to the amount
leaving s.
af(e) af(e) = v(f) e out of A e in to A
6
2 9 5
10
10
44
0
15 15 0
6
10
388
s 5 3 8 6 10 t
A
1
40 6 150
11
10
10
15
11
Value = 6 + 0 + 8 1 + 11 = 24 Page 64
The University of Sydney
4 30 7
Ford-Fulkerson
Ford-Fulkerson(G,s,t) { foreach e I E
f(e) 0
Gf residual graph
while (there exists augmenting path P in Gf){ f Augment(f,P)
update Gf }
return f }
Augment(f,P) {
b bottleneck(P,f) foreach e =(u,v) I P {
if e is a forward edge then
increase f(e) in G by b
else (e is a backward edge)
decrease f(e) in G by b
}
return f }
Page 65
The University of Sydney
Residual Graph*
Originaledge: e=(u,v) IE. Flowf(e),capacityc(e).
Residualedge.
Undoflowsent.
e=(u,v)andeR =(v,u). Residualcapacity:
c(e)=iic(e)-f(e) ifeIE
f i f (e) if eR I E
Residual graph: Gf = (V, Ef ).
Residualedgeswithpositiveresidualcapacity. Ef ={e:f(e)
capacity
u 17 v
6
flow
residualcapacity
u 11 v
6
residual capacity
The University of Sydney
Page 66
Ford-Fulkerson Algorithm
0
2 4 4
flow
capacity
G:
s 10 3 9 5 10 t
0 10208 6010
8X0 0 X8
0 0 8X0
Flow value = 0
244
residual capacity 10
Gf:
10
2
86
s 10 3 9 5 10 t
The University of Sydney
Page 67
Ford-Fulkerson Algorithm
G:
0
2 4 4
1 0 X8 8
10208 6010
s 10 3 X 5 t 9 10
X
0 2 02 10X8
0
2 4 4
Flow value = 8
Gf:
8
2
86
10
2 s 10 3
9 5 2 t 8
The University of Sydney
Page 68
Max-Flow Min-Cut Theorem*
Augmenting path theorem: Flow f is a max flow if and only if there are no augmenting paths in the residual graph.
Max-flow min-cut theorem: The value of the max flow is equal to the value of the min cut. [Ford-Fulkerson 1956]
Integrality. If all capacities are integers then every flow value f(e) and every residual capacities cf (e) remains an integer throughout the algorithm.
The University of Sydney Page 69
Running Times*
Theorem. Ford-Fulkerson runs in O(mF) time.
Theorem. FordFulkerson with maximum bottleneck augmenting path finds a max flow in O(m2 log F) time. [Covered in last weeks slides]
Theorem. FordFulkerson with shortest augmenting path finds a max flow in O(nm2) time. [3927 Lecture]
Theorem. There is an algorithm that finds a max flow in O(nm) time. [Orlin 2012]
The University of Sydney Page 70
Bipartite Matching*
Input: undirected, bipartite graph G = (L E R, E).
M I E is a matching if each node appears in at most
one edge in M.
Max matching: find a max cardinality matching.
1 1 2 2
3 3 4 4
max matching 1-1, 2-2, 3-3, 5-5
5 5
The University of Sydney L
R Page 71
Bipartite Matching
Max flow formulation.
Create digraph G = (L E R E {s, t}, E ).
Direct all edges from L to R, and assign unit capacity.
Add source s, and unit capacity edges from s to each node in L. Add sink t, and unit capacity edges from each node in R to t.
G
1
1 1 1 2 2
3 3 4 4
1
s
t
The University of Sydney
L 5 5 R
Page 72
Bipartite Matching: Proof of Correctness
Theorem: Max cardinality matching in G U value of max flow in G. Proof:
Assume max matching M has cardinality k.
Consider a flow f that sends 1 unit along each of the k paths, defined by
the edges in M.
fisaflow,andithasvaluek.
1 1 1
2 2 12 21
G3 3s33tG 4 4 4 4
1 1
The Univers5ity of Sydney 5 5 5 Page 73
Bipartite Matching: Proof of Correctness
Theorem: Max cardinality matching in G U value of max flow in G. Proof: U
LetfbeamaxflowinGofvaluek.
Integrality theorem k is integral so f(e) is 0 or 1. ConsiderM=setofedgesfromLtoRwithf(e)=1.
each node in L and R participates in at most one edge in M |M|=k: considercut(LEs,REt)
1 1 1
12 21 2 2
s 3 3 t 3 3 4 4 4 4
G5 5 5 5G
1 1
The University of Sydney Page 74
Edge Disjoint Paths
Disjoint path problem:
Given a digraph G = (V, E) and two nodes s and t, find the max number of edge-disjoint s-t paths.
Definition: Two paths are edge-disjoint if they have no edge in common.
25
s36t
47
The University of Sydney
Page 75
Edge Disjoint Paths
Disjoint path problem:
Given a digraph G = (V, E) and two nodes s and t, find the max number of edge-disjoint s-t paths.
Definition: Two paths are edge-disjoint if they have no edge in common.
25
s36t
47
The University of Sydney
Page 76
Edge Disjoint Paths
Max flow formulation: assign unit capacity to every edge. 111
111
s1 1t
1
1
1 1
11
The University of Sydney
Page 77
Edge Disjoint Paths
Max flow formulation: assign unit capacity to every edge. 111
111
s1 1t
1
1
1 1
11
Theorem: Max number edge-disjoint s-t paths equals max flow value.
Proof:
Suppose there are k edge-disjoint paths P1, . . . , Pk.
Set f(e) = 1 if e participates in some path Pi ; else set f(e) = 0. Since paths are edge-disjoint, f is a flow of value k.
The University of Sydney Page 78
Edge Disjoint Paths
Max flow formulation: assign unit capacity to every edge. 111
111
s1 1t
1
1
1 1
11
Theorem: Max number edge-disjoint s-t paths equals max flow value. Proof: U
Suppose max flow value is k.
Integrality theorem there exists 0-1 flow f of value k. Consider edge (s, u) with f(s, u) = 1.
by conservation, there exists an edge (u, v) with f(u, v) = 1
continue until reach t, always choosing a new edge
Produces k (not necessarily simple) edge-disjoint paths. The University of Sydney
Page 79
Summary: Flow networks
Properties
Max-flow min-cut theorem
Integrality lemma
Ford-Fulkersons algorithm Problems
Max flow
Min cut
Matching
Disjoint edge paths
The University of Sydney
Page 80
Lecture 10:
NP and Computational Intractability
The University of Sydney
Page 81
Definition of the class NP
Class NP: Decision problems for which YES-instances have a poly-time certifier.
Certification algorithm intuition.
Certifier views things from managerial viewpoint.
Certifier does not solve the problem by its own;
rather, it checks if a proposed proof t is a valid solution.
Definition: Algorithm C(s,t) is a certifier for problem X if for every input instance s and proposed proof t, C(s, t) = `yes if and only if t is a valid solution to s.
certificate or witness
The University of Sydney
Page 82
Class NP-hard
Class NP-complete: A problem in NP such that every problem in NP polynomially reduces to it.
Class NP-hard:
A decision problem such that every problem in NP polynomially reduces to it.
not necessarily in NP
The University of Sydney Page 83
Establishing NP-Completeness
Remark: Once we establish first natural NP-complete problem, others fall like dominoes.
Recipe to establish NP-completeness of problem Y. Step1. ShowthatYisinNP.
Step 2. Choose an NP-complete problem X. Step 3. Prove that X p Y.
Justification: If X is an NP-complete problem, and Y is a problem in NP with the property that X P Y then Y is NP-complete.
Proof: LetWbeanyprobleminNP. ThenW P X P Y. Bytransitivity,WP Y.
Hence Y is NP-complete. The University of Sydney
by definition of NP-complete
by assumption
Page 84
Reduction Template for Decision Problems (aka Karp reduction)*
Algorithm for X
Instance of Y
f(I)
Yes for f(I) No for f(I)
Transforms instance of X to instance of Y
Algorithm for Y
Instance of X
I
Yes for I No for I
Step 2
Step 1
Step 1: Construct a polynomial-time algorithm that transforms instance I of X to an instance f(I) of Y
Step 2: Prove correctness, which boils down to showing
Answer for I is Yes iff answer for f(I) is Yes
Proof usually done by transforming certificate for I to certificate
for f(I) and vice versa
The University of Sydney Page 85
Summary
Polynomial time reductions
3-SAT P DIR HAMILTONIAN CYCLE P HAMILTONIAN CYCLE P TSP 3-SAT P INDEPENDENT-SET P VERTEX-COVER P SET-COVER
Complexity classes:
P: Decision problems for which there is a poly-time algorithm.
NP: Decision problems for which there is a poly-time certifier. NP-complete: A problem in NP such that every problem in NP polynomial
reduces to it.
NP-hard: A problem such that every problem in NP polynomial reduces to it.
Lots of problems are NP-complete
See https://www.nada.kth.se/~viggo/wwwcompendium/
The University of Sydney
Page 86
Lecture 11:
Coping with hardness
The University of Sydney
Page 87
Summary
NP-complete problems show up in many applications. There are different approaches to cope with it:
Approximation algorithms
Restricted cases (trees, bipartite graphs, small solution)
Randomized algorithms
Each approach has its pros and cons.
The University of Sydney
Page 88
Exam
Time: 10 minutes reading time 2.5 hours writing
Number of problems: 6 (ordered from easiest to hardestimo) For Question 6 there is one for comp3027
and one for comp3927. See Practice Final on Ed.
The University of Sydney
Page 89
More algorithms?
COMP3530:DiscreteOptimization(2019S2) Lecturer: Julian Mestre
COMP5045:ComputationalGeometry(2020S1) Lecturer: Joachim Gudmundsson
Otheropportunities:
SSP, summer projects, informal reading
Please get in touch with us for more information The University of Sydney
Page 90
Please remember to fill in the unit of study evaluation
https://student-surveys.sydney.edu.au/students/
What was good? What was bad?
Thanks for taking the class! Good luck on the exam!
The University of Sydney
Page 91
Reviews
There are no reviews yet.