Algorithms 3027/3927 Assignment 3 The University of Sydney
2021 Semester 1 School of Computer Science
3027 students: Do Tasks 1 and 2. 3927 students: Do Tasks 2 and 3.
Task 1 (3027 only): Greed is not good for edge-disjoint paths [20
marks]
In the Edge-Disjoint Paths Problem, we are given a directed graph G = (V,E) and vertices s, t ∈ V .
Two paths P1 and P2 are edge-disjoint if they do not share any edges. The goal is to find the maximum
number of edge-disjoint paths from s to t, i.e. we want to find the maximum number of s − t paths
P1, P2, . . . , Pk such that for every 1 ≤ i < j ≤ k, Pi and Pj are edge-disjoint.
In class, we showed how to solve this problem by reducing to the Maximum Flow Problem. Your
friend says “We don’t need this network flow thingamajig. Just use greedy: while there exist an s − t
path P in G, take it and remove its edges from G and rinse and repeat.” However, you point out that
on the graph in Figure 1, if greedy takes the path s− v− u− t, then it gets stuck, while clearly there are
two edge-disjoint paths s− u− t and s− v − t.
s
u
v
t
Figure 1: Example input graph
Your friend replies with “That’s true, but mate, what if, instead of taking any s− t path, we take the
shortest s− t path instead?”
Here’s a more formal description of their shortest path greedy algorithm.
Algorithm 1 Greedy algorithm for Edge-Disjoint Paths
1: procedure Greedy(G = (V,E))
2: Initialize H ← G, S ← ∅. . S will be the set of edge-disjoint paths output by the algorithm.
3: while there exists a path from s to t in H do
4: Let P be a shortest path from s to t in H
5: Add P to S
6: Remove edges in P from H
7: end while
8: Return S
9: end procedure
When G is the graph in Figure 1, then Greedy produces the paths s − u − t and s − v − t which is
indeed optimal. In the first iteration, it chooses s− u− t as the shortest path, removing the edges (s, u)
and (u, t) from H; then it chooses s− v − t, removing (s, v) and (v, t) from H. Since H now consists of
only the edge (v, u), there is no path from s to t, so the algorithm terminates. (See Figure 2 for what H
looks like after each iteration.)
Your task is to provide an example input graph on which the above greedy algorithm does not produce
the maximum number of edge-disjoint paths.
(a) Draw the graph.
1
s
u
v
t s
u
v
t
Figure 2: Left: H after the first iteration. Right: H after the second iteration.
(b) Execute the greedy algorithm on the graph, describing what the set S and the graph H is in each
iteration of the greedy algorithm. You should draw the graph H in each iteration. If in some
iteration, there are multiple shortest paths in H, you can make greedy choose any one of them.
(c) Describe/draw a set of edge-disjoint paths that is larger than S.
If you are using LaTeX for your assignments, you can use the TikZ package to draw the graph using
LaTeX. Here’s the code for the example input graph above.
\usepackage{tikz}
\begin{figure}[htbp]
\begin{center}
\vspace{1ex}
\tikzstyle{arc}=[-latex,line width=1pt]
\tikzstyle{vertex}=[draw,circle,very thick,inner sep=2pt]
\begin{tikzpicture}[xscale=1,yscale=1]
\node[vertex,label=left:$s$] (s) at (0,0) { };
\node[vertex,label=above:$u$] (u) at (1,1) { };
\node[vertex,label=below:$v$] (v) at (1,-1) { };
\node[vertex,label=right:$t$] (t) at (2,0) { };
\path[arc] (s) edge (u);
\path[arc] (s) edge (v);
\path[arc] (v) edge (u);
\path[arc] (u) edge (t);
\path[arc] (v) edge (t);
\end{tikzpicture}
\end{center}
\caption{Example input graph}
\end{figure}
Task 2: Edge Direction [80 marks]
In the Edge Direction Problem, we are given an undirected G = (V,E) with n vertices and m edges, and
a positive integer B, we want to decide if it is possible to direct the edges so that the resulting directed
graph has in-degree at most B, i.e. the in-degree of every vertex is at most B. Note that we simply need
to output a Boolean answer YES or NO. See Figure 3 for an example.
Your task is to design an efficient reduction from the Edge Direction Problem to a max flow decision
problem. In the Max Flow Decision Problem, we are given a flow network H and a target value L and
the goal is to decide if the max flow in H has value at least L; the output is either YES or NO.
(a) Describe how you transform the Edge Direction Problem into a Max Flow Decision Problem. In
particular, you need to describe the flow network H and the target value L of your max flow decision
problem.
(b) Prove the correctness of your reduction. In particular, you need to prove the following two state-
ments:
2
u
v
w
x
y
u
v
w
x
y
Figure 3: The edges in the graph on the left can be directed so that the in-degree is at most 2 (see
directed graph on the right), but cannot be directed so that the in-degree is at most 1.
(a) If the max flow in H is at least L, then it is possible to direct the edges so that the resulting
directed graph has in-degree at most B.
(b) If it is possible to direct the edges so that the resulting directed graph has in-degree at most
B, then the max flow in H is at least L.
(c) Prove the time complexity of your entire algorithm, taking into account the time taken to compute
H and L, and to solve the max flow decision problem. Make sure you state which max flow algorithm
you use to solve the max flow decision problem, and that your time complexity is stated in terms
of G and B.
Task 3 (3927 only): Randomized Contraction Fails on Weighted
Graphs [20 marks]
Your task is to give an example of an n-vertex graph G = (V,E) with edge weights w(u, v) such that
the probability that the randomized contraction algorithm finds a min-weight cut is at most c/2n, for
some constant c.
Algorithm 2 Randomized contraction algorithm
1: procedure Randomized-contraction(G = (V,E))
2: Initialize S(v) = {v} for each vertex v. . S(v) keeps track of the vertices that have been
contracted into v.
3: Initialize G0 = G.
4: for i← 1 to |V | − 2 do
5: Choose an edge e = (u, v) of Gi−1 uniformly at random.
6: Let Gi be the graph resulting from the contraction of e, with a new vertex zuv replacing u and
v.
7: Define S(zuv) to be the union of S(u) and S(v)
8: end for
9: Let y and z be the two vertices of G|V |−2.
10: Return the cut (S(y), S(z)).
11: end procedure
(a) Describe your n-vertex directed graph G. Make sure that your description is in terms of n, similar
to the solution of Tutorial 6, Problem 9, and that you include an illustration of G for ease of
readability.
(b) Show that the probability that the randomized contraction algorithm finds a min-weight cut in G
is at most c/2n.
Submission details
• Submission deadline is Wednesday 5 May, at 23:59. Late submissions without special con-
sideration will be subject to the penalties specified in the first lecture (20% per day). Submissions
3
later than Friday 7 May, 23:59 will not be accepted.
• Submit your answers as a single document to Gradescope. Your work must be typed (no images of
text, although you can use diagrams if you think it helps.) Please try to be reasonably concise.
• Your report will be subject to automatic and manual plagiarism detection systems. Remember, it’s
acceptable to discuss high level ideas with your peers, but you should not share the detail of your
work, such as parts as the precise algorithms, examples, proofs, writing, or code.
• To facilitate anonymous grading, please do not write your name on your submission.
4