Algorithm Analysis Problem Set 4
CSI 3108-01, Fall 2020 Due at 5:00pm, Tuesday, December 8
This problem set consists of one written assignment that has two parts.
When a problem asks you to design an algorithm, you must also prove the
algorithm’s correctness and analyze its running time. Your algorithm must
be efficient unless the problem specifies otherwise.
If you solve a problem by reducing to an algorithm from the textbook (ex-
cluding exercises) or lectures, then you do not need to re-derive the running
time or proof of correctness for the algorithm you are reducing to. However,
you must say which algorithm you are reducing to, and you must correctly
account for that algorithm’s running time when determining the overall run-
ning time of your own algorithm. You must also prove that your reduction
is correct, under the assumption that the algorithm you are reducing to is
correct.
You are also allowed to quote any theorem from the textbook (again, exclud-
ing exercises) or lectures, without re-deriving the proof of that theorem.
(1)
(a) (25 points)
In this problem, we are given some number k > 0 and a directed graph G = (V,E) with
two disjoint subsets of vertices A,B ⊊ V (A ∩ B = ∅) whose cardinalities are equal:
|A| = |B|. Let m := |A| = |B|. Our goal is to find m simple directed paths P1, . . . , Pm
that satisfy the following properties:
• every edge in E appears in at most k of these paths;
• every vertex in A is the first vertex of exactly one path among P1, . . . , Pm;
• every vertex in B is the last vertex of exactly one path among P1, . . . , Pm.
Design an algorithm that, given G, A, B, and k, finds such paths. If there does not exist
m paths that satisfy the given properties, your algorithm must output “infeasible”.
Example 1.
Suppose that the input graph G = (V,E) is defined by V := {a, b, c, d, e, f, g, h, i, j, k, l}
and E := {〈a, d〉, 〈d, g〉, 〈g, j〉, 〈j, a〉, 〈b, a〉, 〈a, c〉, 〈e, d〉, 〈d, f〉, 〈h, g〉, 〈g, i〉, 〈k, j〉, 〈j, l〉}.
The rest of the input is k = 2, A = {b, e, h, k}, and B = {c, f, i, l}.
• Paths P1 = (b, a, d, f), P2 = (e, d, f), P3 = (h, g, i), and P4 = (k, j, l) constitute an
incorrect answer because f ∈ B is the last vertex of two paths.
• Paths P1 = (b, a, d, g, j, l), P2 = (e, d, g, j, a, c), P3 = (h, g, j, a, d, f), and P4 =
(k, j, a, d, g, i) constitute an incorrect answer because edge 〈a, d〉 for example
appears on three paths.
• Paths P1 = (b, a, c), P2 = (e, d, f), P3 = (h, g, i), and P4 = (k, j, l) constitute
a correct answer. There are other correct answers, too, but your algorithm may
output any one of the correct answers.
Example 2.
Suppose that the input graph G = (V,E) is defined by V := {a, b, c, p, q,
x, y, z} and E := {〈a, p〉, 〈b, p〉, 〈c, p〉, 〈p, q〉, 〈q, x〉, 〈q, y〉, 〈q, z〉}. The rest of the input
is k = 2, A = {a, b, c}, and B = {x, y, z}. The correct answer is infeasible.
Example 3.
Suppose that the input graph G = (V,E) is defined by V := {a, b, c, p, q,
x, y, z} and E := {〈a, b〉, 〈c, b〉, 〈b, p〉, 〈b, q〉, 〈p, y〉, 〈q, y〉, 〈y, x〉〈y, z〉}. The rest of the
input is k = 2, A = {a, b, c}, and B = {x, y, z}. A correct answer is P1 = (a, b, p, y),
P2 = (b, p, y, x), and P3 = (c, b, q, y, z). Again, there are other correct answers; your
algorithm may output any one of them.
(b) (25 points)
Prove the following statement: in the above problem, there does not exist m paths that
satisfy the given properties if and only if there is some U ⊆ V such that |U ∩A| > |U ∩B|
and G has fewer than |U∩A|−|U∩B|
k
edges from U to V \ U .

欢迎咨询51作业君