### Assignment 2

```Assignment 2
COMP 5703 - Fall 2014
October 20, 2014
1
Instructions
This is due at the start of the class on November 17, 2014. Please write clearly and answer questions
precisely. As a thumb rule, the answer should be limited to ≤ 2 written pages, with ample spacing
between lines and in margins, per question. Always start a new question on a new page, starting
with Question 1, followed by Question 2, ..., Question n. Please cite all the references (including
web-sites, names of friends, etc.) which you have used/consulted as the source of information for
each of the questions. BTW, when a question asks you to design an algorithm - it requires you
to (1) Clearly spell out the steps of your algorithm in pseudocode (2) Prove that your algorithm
is correct and (3) Analyze the running time. By default a graph G = (V, E) is simple, undirected
and connected.
2
Problems
1. Consider the following version of the (weighted) planar-separator theorem. Let G = (V, E)
be an embedded undirected triangulated planar graph, where n = |V |. Each vertex v ∈ V
P
has a positive weight w(v) ≥ 0 and v∈V w(v) = 1. There exists a partition of V into disjoint
sets A, B, and S, such that
(a) w(A), w(B) ≤ 32 , where w(A) is the sum total of weights of all the vertices in set A
√
(b) |S| ≤ 4 n
(c) There is no edge in E that joins a vertex in A with a vertex in B.
(d) Such a set S can be found in linear time.
Show what changes you need to make in the proof of (unweighted) Planar Separator Theorem
to prove the above theorem.
2. Prove the following: Let G = (V, E) be a connected planar graph and G∗ be its dual. For
any E 0 ⊆ E, the subgraph (V, E 0 ) has a cycle if and only if the subgraph (V ∗ , E − E 0 ) of G∗
is disconnected.
3. Prove the following theorem on Geometric Separators. In 2-dimensions assume that you have
n squares of arbitrary sizes. Squares are axis aligned. Moreover none of the points in the
plane is inside more than k-squares. Prove that there exists either a vertical or a horizontal
line which partitions the set of squares in such a way that at least b n+1−k
c of squares interiors
4
lie to each side of the line. How fast you can find such a line?
1
4. Prove that in the LCA algorithm of Bender and Farach-Colton, why does the reduction from
the LCA problem to the range-minima query works, i.e., show that in place of finding the
LCA of nodes u and v in the binary tree, why does it suffice to compute the smallest level
number in the level array in an interval defined by the first occurrence of the node u an v in
the level array.
5. This problem is to show that an arbitrary range minima query (RMQ) problem can be solved
within the same complexity as the one with the ±1 RMQ problem. Recall that the ±1
RMQ problem for an array of size n required O(n) time to preprocess and then the queries
were answered in O(1) time. The idea is to reduce an arbitrary RMQ problem to the LCA
problem. This reduction uses Cartesian Tree. Let A be an array consiting of n numbers (need
not satisfy the ±1 property). The Cartesian Tree C for A is defined as follows: The root
of C is the minimum element of A, and it stores the position of this element in the array.
Removing the root element splits the array into left and right subarrays. The left and right
children of the root are recursively constructed Cartesian trees of the left and right subarrays,
respectively. Prove the following:
(a) Cartesian tree C of an array A of size n can be computed in O(n) time (use incremental
construction).
(b) Show that RM QA (i, j) = LCAC (i, j) (Recall that in C we store the indices i and j.)
6. Let G = (V, E) be a connected undirected graph, where each edge has a positive weight, and
n = |V |. Let us compute a subgraph H of G, by choosing each edge of G, independently with
probability 0 < p < 1. Let T be a minimum spanning forest of H. Show that for any integer
k > 0, the
number of light edges in G with respect to T exceeds k with probability at most
Pn−1 k i
p
(1
− p)k−i .
i=0 i
(Hint: Look at the paper by Klein and Tarjan on MST)
7. Suppose we are given a flow network G, where edges have positive integer capacities, and
P
C = u,v∈V c(u, v), where c(u, v) is the capacity of the edge e = (u, v) ∈ E. Show the
following
(a) The value of the max flow is an integer.
(b) There is an assignment of non-negative integer flow values on each edge of G, satisfying
all the flow conservation conditions, so that G achieves max flow.
(c) Show that the number of iterations required in the Ford-Fulkerson’s algorithm (Residual
network, find an augmenting path, augment the flow, repeat) is O(C).
(d) Show that in the worst case, Ford-Fulkerson’s algorithm, as stated in the Question 5c
runs in exponential time.
(e) Construct an example, where one can realize the worst case as stated in the Question
5d.
8. Let G = (V, E) be the flow network. Let C = max(u,v)∈E c(u, v) be the maximum capacity.
Show the following:
(a) Minimum cut of G has a capacity of at most C|E|.
2
(b) For a given number K > 0, show how to find an augmenting path of capacity at least
K in O(|E|) time, provided that such a path exists.
(c) Execute the following algorithm:
i. Initialize the flow f = 0;
ii. K = 2blog Cc ;
iii. While K ≥ 1 do
A. While there exists an augmenting path p of capacity at least K then augment
flow f along p.
B. K := K/2;
iv. Return f .
Show that the above algorithm computes Max-Flow.
(d) Show that the loop in Step iii.A is executed at most O(|E|) times for each value of K.
(e) Show that the algorithm runs in O(|E|2 log C) time.
9. Let G = (V, E) be a flow network. Recall that G is a complete graph, where some of the
edges may have a capacity of zero. Suppose your task in the max flow problem is to increase
the flow of a network as much as possible, but you are only allowed to increase the capacity of
only one edge, whose capacity is strictly larger than zero. First show that there are networks
where such an edge may not exist, i.e. increasing the capacity of a single edge (> 0 capacity)
will not alter the value of the max-flow. Show that there are networks, where such an edge
may exist. Try to design an algorithm which can detect whether flow can be increased.
10. A simple undirected graph G = (V, E) is called k-edge connected if removal of any set of
k-edges keeps G still connected. (e.g. cycles are 1-edge connected.) Show how to compute
edge connectivity of G by invoking at most |V | network flow computations.
3
```