Algorithms 3027/3927 Assignment 3 2021 Semester 1
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.
u
st
v
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: 2: 3: 4: 5: 6: 7: 8: 9:
procedureGreedy(G=(V,E))
Initialize H ← G, S ← ∅. ◃ S will be the set of edge-disjoint paths output by the algorithm. while there exists a path from s to t in H do
LetP beashortestpathfromstotinH AddP toS
Remove edges in P from H
end while
Return S 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
The University of Sydney School of Computer Science
uu
stst
vv
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
vx vx
uu
wy wy
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,thenthemaxflowinH isatleastL.
(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: 2:
3: 4: 5: 6:
7: 8: 9:
10: 11:
procedureRandomized-contraction(G=(V,E))
Initialize S(v) = {v} for each vertex v. ◃ S(v) keeps track of the vertices that have been
contracted into v.
Initialize G0 = G.
for i ← 1 to |V | − 2 do
v.
Choose an edge e = (u, v) of Gi−1 uniformly at random.
Let Gi be the graph resulting from the contraction of e, with a new vertex zuv replacing u and
Define S(zuv) to be the union of S(u) and S(v) end for
Let y and z be the two vertices of G|V |−2.
Return the cut (S(y), S(z)). 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