COL702: Advanced Data Structures and Algorithms (CSE, IITD, Semester-I-2022-23) Homework-6

There are 3 questions for a total of 75 points.

1. Solve the following two problems:

(a) (10 points) An edge in a network flow graph is called downwards critical if decreasing the capacity
of this edge decreases the maximum flow in the network. Design an algorithm to find a downwards
critical edge in a network. Give pseudocode, discuss running time and give proof of correctness.

Solution: Run a max-flow algorithm on the graph and obtain a s-t flow f . Let A be all vertices
reachable from s in the residual graph Gf . Note that (A, B) is an s-t cut. Any edge that goes
across this cut (A, B) is a downwards critical edge since decreasing the capacity of this edge
decreases the capacity of the cut. The running time of the algorithm will be the same as the
running time of the max-flow algorithm that you use.

(b) (15 points) An edge in a network flow graph is called upwards critical if increasing the capacity
of this edge increases the maximum flow in the network. Design an algorithm to find an upwards
critical edge in a network in case there exists one. Give pseudocode, discuss running time and give
proof of correctness.

Solution: Let us start by proving the following claim.

Claim 1: An edge is upwards critical if and only if it is present in all s-t min-cuts of the given
graph.
Proof. If all s-t min-cuts include an edge e, then increasing the capacity of this edge will
definitely increase the capacity of the min-cut in the graph and hence the max-flow will increase
(using max-flow-min-cut theorem).
On the other hand, if increasing the capacity of an edge e increases the max-flow. Then we will
argue that e is present in all s-t min-cuts. Suppose for the sake of contradiction, assume that
there is a min-cut in the graph that does not include e, then the capacity of the min-cut will
not change by increasing the capacity of e and hence the max-flow will not increase.
Suppose we run a max-flow algorithm to find a max flow f in the network. Let A be the set of
vertices reachable from the source vertex s in Gf and B be the remaining vertices. We know
that (A, B) is a cut with minimum capacity. What the above claim tells us is that the only
edges that are candidates for being upwards critical are edges that go from A to B. Let (u, v)
be any such edge. How do we determine if increasing the capacity of (u, v) increases the flow?
The simplest way to do this is to consider graph G0f which is the same as Gf except that the
weight of edge (u, v) is non-zero. Now, if there is an s-t path in G0f , then this means that more
flow may be pushed in G0f . This means that if the edge capacity of (u, v) were larger, then the
max-flow is larger. This means that (u, v) is upwards critical.
Let T denote all vertices in B such that there is a path from the vertex to t in Gf . Note that
we can find this set T by doing a DFS (on an appropriate graph) in time O(n + m) time. We
simply output any edge from the set A to T . So, the total running time will be equal to the
running time of the max-flow algorithm plus O(n + m).

1 of 4
COL702: Advanced Data Structures and Algorithms (CSE, IITD, Semester-I-2022-23) Homework-6

2. (25 points) Design an algorithm that outputs a minimum vertex cover of a given bipartite graph G =
(L, R, E). Give pseudocode, discuss running time and give proof of correctness.

Solution: Given a bipartite graph G = (L, R, E), we construct a flow network F as follows:

F has a source vertex s and a sink vertex t. F also has a vertex corresponding to each
vertex in L and R. For every u ∈ L, there is an edge (s, u) in F with weight 1 and for
every v ∈ R, there is an edge (v, t) in F with weight 1. For every edge (u, v) ∈ E, there
is an edge (u, v) in F with weight ∞.

The following claims with respect to the above construction will help us design an algorithm.
Claim 1: If there is an s-t cut in F with finite capacity k, then there is a vertex cover of G with
cardinality k.

Proof. Let (A, B) denote the cut with finite capacity k. Let S = A ∩ L and T = A ∩ R. Note that
k = c(A, B) = |L − S| + T . This is because there is no edge that goes from a vertex in A to a vertex
in R − T , since otherwise the capacity of the cut will not be finite. Given this, note that the set
(L − S) ∪ T is a vertex cover of G. This proves the claim.

Claim 2: If there is a vertex cover of G with cardinality k, then there is an s-t cut in F with capacity
k.

Proof. Let C denote a vertex cover of G such that |C| = k. Let S 0 = C ∩ L and T = C ∩ R. Let
S = L − S 0 . Consider the cut (A, B) where A = {s} ∪ S ∪ T and T contains the remaining vertices
of F . The capacity of this cut is exactly |S 0 | + |T | = k since there are no edges from any vertex in
S to any vertex in R − T . This proves the claim.

The above two claim tell us that if we find an s-t cut (A, B) in F with minimum capacity, then
(L − A ∩ L) ∪ (A ∩ R) is a minimum vertex cover of G. Fortunately, we know how to find an s-t cut
with minimum capacity in any network. Here is the algorithm for this problem. The correctness
follows from the previous claims.

BipartiteVC(G)
- Construct the network F from G as given above
- Run the Ford-Fulkerson algorithm on F and let f be the flow returned
- Let A be the vertices reachable from s in the residual graph Gf
- return((L − A ∩ L) ∪ (A ∩ R))

Running time: Constructing the network from the given bipartite graph will take O(n + m) time.
Running Ford-Fulkerson algorithm on this graph will take time O(n · (m + n)) time. Finding sets
A and taking other intersections and unions will take O(n + m) time. So, the total running time of
the algorithm is O(n(n + m)).

2 of 4
COL702: Advanced Data Structures and Algorithms (CSE, IITD, Semester-I-2022-23) Homework-6

3. (25 points) You are given n pairs of integers (d1 , d01 ), ..., (dn , d0n ) such that ∀i, di , d0i ≥ 0. You have to
design an algorithm that determines if there exists a directed graph G = ({1, ..., n}, E) such that the
in-degree of vertex i is di and the out-degree of vertex i is d0i . Your algorithm should also output a graph
with the given degree sequence, in case there exists one. Give pseudocode, discuss running time and give
proof of correctness.

Pn Pn
Solution: If i=1 di 6= i=1 d0i , then there cannot exist Pnsuch a graph
Pn and we can simply
Pn return
0
“no”.
Pn So, for the remaining discussion, assume that i=1 d i = i=1 di . Let D = i=1 di =
0 0 0
i=1 di . Let G((d 1 , d 1 )..., (dn , dn )) denote the proposition that there exists a directed graph with
in/out-degrees denoted by these numbers. Given (d1 , d01 ), ..., (dn , d0n ), let us construct the following
network F ((d1 , d01 ), ..., (dn , d0n )):

There is a source node s and a sink node t. There are vertices v1 , ..., vn corresponding to
numbers d1 , ..., dn and vertices v10 , ..., vn0 corresponding to numbers d01 , ..., d0n . For every
i, there is an edge with weight di from s to vi and an edge with weight d0i from vi0 to t.
Also there are edges of weight 1 from vi to vj0 such that i 6= j.

The next two claims help us design an algorithm.

Claim 1: G((d1 , d01 ), ..., (dn , d0n )) ⇒ there is an s-t flow in F ((d1 , d01 ), ..., (dn , d0n )) with value D.

Proof. Let G = ({1, ..., n}, E) be a graph with in/out-degrees of vertices denoted by these numbers
(d1 , d01 ), ..., (dn , d0n ). That is the in-degree of vertex i in G is di and the out-degree is d0i . Consider
the following flow in the network F . For all i, f (s, vi ) = di and f (vi0 , t) = d0i . Furthermore,
or all (i, j) ∈ E, f (vi , vj ) = 1 and for all (i, j) ∈ / E, f (vi , vj ) = 0. Note that f is an s-t flow
since the capacity constraints are met and furthermore for all i, f in ({vi }) = di = f out ({vi }) and
f in ({vi0 }) = d0i = f out ({vi0 }). Further, note that the value of f is D.

Claim 2: G((d1 , d01 ), ..., (dn , d0n )) ⇐ there is an s-t flow in F ((d1 , d01 ), ..., (dn , d0n )) with value D.

Proof. Let f be the s-t flow in F with value D. Let us construct a graph G = ({1, ..., n}, E) using
this flow f . For any i, j, (i, j) ∈ E if and only if f (vi , vj0 ) = 1. Note that for any i, the total in-degree
of vertex i in the constructed graph G is equal to di since by flow conservation, the total in-flow
into vi is equal to di and hence there are di edges with flow value 1 incident on vi . Similarly, the
out-degree of vertex i is equal to d0i . This proves the claim.

The correctness of the following algorithm follows from the above claims.

CheckDegrees((d1 , d01 ), ..., (dn , d0n ))

- If ( i di 6= i d0i ) return(“no”)
P P
P
- D ← i di
- If (D > n(n − 1)) return(“no”)
- Construct network F as described above
- Run Ford-Fulkerson on F and obtain flow f with maximum value
- If (v(f ) 6= D)return(“no”)
- else return(“yes”)

Running time: Constructing the flow network takes O(n2 ) time. Ford-Fulkerson takes O(n4 ) time
on the constructed network. So, the total running time of this algorithm is O(n4 ).

3 of 4
COL702: Advanced Data Structures and Algorithms (CSE, IITD, Semester-I-2022-23) Homework-6

(Note that you may be able to give algorithms with better running time either using a better Flow
algorithm or a completely different idea altogether.)

4 of 4