CS 6550 Algorithm Design: Flows, Matchings, and Graph Coloring

This assignment delves into the design and analysis of algorithms, specifically focusing on matching reductions and graph theory concepts. It covers topics such as Konig's theorem, Hall's theorem, and the max-flow/min-cut theorem in the context of bipartite graphs. The solution provides proofs and explanations for various problems related to maximum and minimum weight matchings, d-regular bipartite graphs, and edge coloring. The assignment also explores the application of these concepts in solving practical problems related to network flows and graph algorithms. Desklib offers a wealth of resources, including similar solved assignments and past papers, to aid students in mastering these complex topics.

Design Analysis of Algorithm
Design Analysis of Algorithm
CS – 6550
1

Design Analysis of Algorithm
Table of Contents
Solution Exercise 1 1
Solution Exercise 2 2
Solution Exercise 3 3
Solution Exercise 4 4
Solution Exercise 5 5
Solution Exercise 6 6
2

Design Analysis of Algorithm
Exercises
1. *Flows, Kings, Halls, and Colors. Recall that Koenig’s theorem says for a
bipartite graph G, the size of the maximum cardinality of a matching in G is
equal to the size of the minimum vertex cover.
(a) Use the max-flow/min-cut theorem to prove Koenig’s theorem. (Recall that the
max-flow/min-cut theorem says that in any flow network, the maximum s􀀀t flow
equals the minimum s􀀀t cut. Moreover if the arc capacities are integers, then there
is a max flow which is integral.)
Solution-
Bipartite Graph
A Bipartite Graph also known as Bi-graph is a graph having set of vertices decomposed into two
disjoint set of vertices such that no two vertices in the graph within the same set are adjacent. It
is considered as a special case of K-Partite graph. A Bipartite Graph G= {U, R, V} consists of
two disjoint sets Land R and a set of edge E such that it has one vertex in L and one in R.
Koenig’s Theorem
3

Design Analysis of Algorithm
According to Koenig’s Theorem the size of minimum vertex cover is equal to the size of minimum
vertex cover is equal to the size of the maximum matching. For a Bipartite graph G, the maximum
size of a matching equals the minimum size of a vertex cover.
Proof of Koenig’s Theorem through Max- Flow/Min-Cut Theorem
According to the Max-Flow /Min –Cut Theorem, a minimum cut is equal to the maximal flow.
Now using the definition of Bipartite Graph, for any finite Bipartite Graph g, the number of
edges in maximal equals to the number of vertices in the Minimal Vertex Cover.
In order to prove this we extend the Bipartite Graph G to a network by adding source and sink
in it. By doing this it is observed that in the new graph the maximal flow corresponds to the
maximal matching and the Minimum Cut corresponds to the minimum cover. Here Let X and Y
be the Bipartite separation for the graph G, now by this we draw a digraph G1 = {V1, E1}, where
V1 represents the set of vertices in V with source s and sink t, E1 represents the set of edges in E,
along with this their consists of the other new edges leading from s to every vertex in Set X and
leading from vertex Y to t. The Edges according to the assumption has infinite capacity, and to
each added new edge in E1 the capacity assigned is 1. It is assumed that the cardinality of
matching to be k, so the flow will also be k. The Flow 1 is pushed in the path s-x, x-y and y-t
where (x, y) is one of the matched observations with flow 1. Thus the maximal flow in G1
corresponds to the cardinality of G.
Let the M be the Cover of G with r vertices , let M(X) and M(Y) be the subsets of M having
vertices of M in X and Y. It is assumed that the X1 = X-M(X) and Y1 = Y-M(Y). The Cover M
implies that there is no edge from X1 to Y1. Further it is assumed that S be the Union of s, M(Y)
4

Design Analysis of Algorithm
and Y1. Similarly let T be Union of t, M(Y) and Y1. Further it is observed that the cardinality of
cut (S, T) of G1 is r which is also the cardinality of M, so the cover of vertex cut is same. Again
by the rule the edges from X to Y will have infinite capacity and edges from S to T will have
capacity 1. Since the cut had cardinality r so the number of arcs is also r.
Now we observe for Minimal value, here let M be the set of vertices x in X such that sx in
(S,T) , similarly set of vertices y in Y such that sy in ( S,T). As proved before that the number of
vertices in M are r . So it is observed that every cover in G corresponds to the G1. So minimum
cut corresponds to the minimal covering in G.
*(b) Use Konigs theorem to prove Hall's theorem:
In a bipartite graph G = (L;R;E), for any set S _ L, let N(S) = fr 2 Rj9` 2 S; (`; r) 2
E g be the neighbors of S. Then G has a matching of size jLj if and only if jN(S)j _
jSj for all S _ L
Proof
Hall’s Theorem
According to Hall ‘s Theorem , A Bipartite graph G with Bi-partition, Here Let L and R be the
Bipartite separation for the graph G . Then there is matching of size X if and only if every set S
is subset of L of vertices at least connected to |S| vertices in B.
Now using the Konig’s theorem - The size of minimum vertex cover is equal to the size of
minimum vertex cover is equal to the size of the maximum matching . For a Bipartite graph G,
the maximum size of a matching equals the minimum size of a vertex cover. So by using the
result of konig’s theorem the S will be subset of L as both have same capacity and flow with
maximal matching.
5

Design Analysis of Algorithm
Now through another result of Hall’s Theorem if L and R are both countable and every vertex
has finite number of neighbors then for every S that is subset of L , has at least |S| neighbors,
then there is matching touching every vertex of L, now it is given-
According to above given specification there are finite number of neighbors, in order to check
we assume to take arbitrary x ϵ L and yϵ R such that both have at least one neighbor in both.
We match the neighbors of both the sets and observe that the flow or cardinality of both the cut
set are equal. L-x and R-y, so there are vertices that match to S1 to the L.
*(c) Use Koenig’s or Halls theorems to show that in a bipartite graph where every
vertex has the same degree d (also called a d-regular bipartite graph), there is a
perfect matching.
Proof
D-regular Bipartite Graph
A Bipartite Graph is called regular –d bipartite graph if and only if every vertex of G has degree
d. As it is evident the degree of a vertex implies the number of edges incident on the vertex. By
Koenig’s Theorem- the Edges according to the assumption has infinite capacity, and to each
added new edge in E1 the capacity assigned is 1. It is assumed that the cardinality of matching to
be k, so the flow will also be k. The Flow 1 is pushed in the path s-x, x-y and y-t where ( x,y) is
one of the matched observation with flow 1. Thus the maximal flow in G1 corresponds to the
cardinality of G. Since the graph is regular and the edges go from X to Y then for generality we
assume that the A be subset of X .Let A⊆X be an arbitrary subset, and denote by the set of
6

Design Analysis of Algorithm
neighbors N of elements of A .Every edge in the Bipartite graph has endpoint in A has an
endpoint in N(A) (N(A) is the set of neighbours of A) , so letting EA and EN(A) denote the
respective edge sets, . Then since G is regular (d is the degree of each vertex), |EA|=d|A| and |
EN(A)|=d|N(A)| , hence |A|≤|N(A)| . By Hall’s theorem there is a complete matching. But |X|=|Y|,
so every vertex in is matched to a vertex in , which together match every vertex in the graph.
Thus the complete matching is a perfect matching
*(d) Use the above part to show that the edges of a d-regular bipartite graph can be
colored using d colors so that all edges incident on each vertex have different
colors.
Color of Edges in Graph
The coloring of edges in a graph defines the way in which no vertex is incident on two edges
having the same color, a graph is Bipartite if the graph is 2 colorable otherwise not.
Cloring of Edges in Regular Bipartite graph with degree d
A Bipartite Graph is called regular –d Bipartite graph if and only if every vertex of G has degree
d. For coloring the graph two set of possible path from graph is required to create from subsets
X,Y such that their vertices are not repeated and one color to one set of path and another color to
another set of path is drawn. As it is evident the degree of a vertex implies the number of edges
incident on the vertex. By Konig’s Theorem- The Edges according to the assumption has infinite
capacity , and to each added new edge in E1 the capacity assigned is 1. It is assumed that the
cardinality of matching to be k, so the flow will also be k. The Flow 1 is pushed in the path s-x,
x-y and y-t where ( x,y) is one of the matched observation with flow 1. Thus the maximal flow
in G1 corresponds to the cardinality of G. Since the graph is regular and the edges go from X to
7

Design Analysis of Algorithm
Y then for generality we assume that the A be subset of X .Let A⊆X be an arbitrary subset, and
denote by the set of neighbors N of elements of A .Every edge in the Bipartite graph has
endpoint in A has an endpoint in N(A) (N(A) is the set of neighbours of A) , so letting EA and
EN(A) denote the respective edge sets,
In order to perform coloring the Subsets of vertices X , Y are done and path , s-x , s-y is drawn,
t-x, t-y is drawn using the result of konig’s Theorem Again by the rule the edges from X to Y
will have infinite capacity and edges from S to T will have capacity 1. Since the cut had
cardinality r so the number of arcs is also r , the flow of all the path is 1 . According to rule each
bigraph should be divided in two parts so by using the halls result matching is performed . In
order to check we assume to take arbitrary x ϵ X and yϵ Ysuch that both have at least one
neighbor in both. We match the neighbours of both the sets and observe that the flow or
cardinality of both the cut set are equal. X-x and Y-y , so there are vertices that matches to S1 to
the L. only coloring is done to unmatched set of edges.
2. *Some Matching Reductions. Suppose you have an algorithm that solves max-
weight perfect matchings (MaxWPM) for all non-negative weight functions. Give
reductions that allow you to solve (a) min-weight perfect matchings (MinWPM)
and (b) min-weight max cardinality matchings (MinWMaxM)i.e., among all
matchings of size equal to MM(G), _nd the one with least weight. If the MinWPM
and MinWMaxM instances are bipartite, ensure that the reductions give you
MaxWPM instances that are bipartite too
8

Design Analysis of Algorithm
Proof-
According to Maximum weighted matching algorithm , a non negative weight wi ,j is assigned to
each edge in the xi and yi in the set in Knn. Here we have to find the perfect matching M for
maximizing the total weight w(M) = ∑ e ∈ M W(e) .
In order to perform this a weighted cover , let u1, u2, u3---------un and v1, v2, v3------vn is selected
such that ui + vj ≥ w i.j for all i and j. Along with above the cost of c(u,v) is ∑ ui+¿ ∑ vj¿. Here
we have to find the cover with minimum cost.
For a perfect matching M in the Bipartite graph G with cover C (u,v) is that in any case the
C(u,v) ≥ w(M) . For matching this is possible only if M (matching ) consists of edges such that
ui+ vj = w ij. Here (u,v) is considered to be optimal. In the cover excess for i, j is ui+ vj – wi,j. we
are applying the Hingerian Algorithm for min-weight perfect matchings (MinWPM) .
Input : A matrix Wi,j of weights on edges on Kn,n with partite sets X and Y.
Concept : Adjusting the cover (u,v) iteratively until subgraph Gu,v has a perfect matching.
Initialization: Let ui = max { Wi,j : j=1,2…..n} and vj = 0.
Iteration: In order to perform the iteration first the two sets GU,V are designed and perfect
matching M is applied. The iteration will be stopped when the M has maximum matching and
(u,v) has minimal cost cover. Else the update of (u,v) will be done and same iterative operation is
applied until M has maximum matching and (u,v) has minimal cost cover.
B) Now to find the min-weight max cardinality matchings (MinWMaxM) i.e., among all
matching of size equal to MM(G), _nd the one with least weight. If the MinWPM and
MinWMaxM instances are bipartite, ensure that the reductions give you MaxWPM instances that
are bipartite too. We apply the result of Konig’s Theorem in it it is observed that the cardinality
9

Design Analysis of Algorithm
of cut (S,T) of G1 is r which is also the cardinality of M, so the cover of vertex cut is same. Again
by the rule the edges from X to Y will have infinite capacity and edges from S to T will have
capacity 1. Since the cut had cardinality r so the number of arcs is also r. so by applying this the
required criteria is fulfilled.
*3. Min-weight Perfect Matching’s. Suppose G = (L;R;E) is a undirected bipartite
graph with (possibly negative) integer edge weights we, suppose M is some perfect
matching. Let HM be the digraph obtained by directing edges in E n M from left-
to-right and putting weights we on them, and directing all edges in M from right-
to-left and putting weights 􀀀we on them.
(a) Show that HM has a negative-weight cycle if and only if M is not a min-
weight perfect matching.
Prove
Here it is given that there is unidirected Bipartite Graph G= (L;R;E) , means that the graph G
can be divided into two sub graphs X having set of vertices L and Sub graph Y with set of
vertices R, and the set of edges E. It has edge weights Wi,j inclined in it. For perfect Bipartite
graph to check the Maximum matching M , for any non-existing edge we add a edge with zero
weight .As we have shown how to find the min-weight max cardinality matchings
(MinWMaxM)i.e., among all matching of size equal to MM(G), _nd the one with least weight in
previous prove , we will continue with the same result. Now in order to prove that HM has a
negative-weight cycle if and only if M is not a min-weight perfect matching we will first check
10

Design Analysis of Algorithm
for any negative cycle in HM, if there exists a negative cycle then matching cannot be
Maximum. We assume that there is no negative Cycle in HM and M is not a maximum
matching. Let there exists a maximum matching M1, we take sub graph D1 of Graph D. Therefore
there exists a maximum matching M′. This contains the edges in MM ′. This graph is made up of
single disjoint edges (e∈ M∩M′) and alternating cycles (C⊂(M∪M′)−(M∩M′)). We assume
W(M′)> W(M)and W(e) fore ∈ M∩M ′is equal for both matching’s, then we have W(M′−M)>
W(M−M), which means there exists the negative cycle C⊂(M∪M′)−(M∩M′) = (M−M′)∪(M′
−M) in D′, and therefore in D, with a weight at most W(M−M)−W(M′−M). This method is not
very efficient because there is no scope in of improvement in each iteration and when w max=
max i,j{wi,j }, it is large compared to w min= min i,j{wi,j} so the time complexity becomes
O(m n×n (w max−w min), which is not polynomial in the inputs . According to Goldberg and
Tarjan , that if one finds negative cycles with minimum average weight W(C)/|C|,the time
complexity will be strongly polynomial.
(b) Consider the algorithm: Start with any perfect matching M. While there exists a
negative-weight cycle C in HM, set M M_C. Show that you will eventually get a
MwPM. If T(n) is the time to _nd a negative-weight cycle in an n-node graph, and
W := maxe2Ejwej, a naïve bound on the runtime of the above algorithm would be
O(nW)_T(n), plus the time to _nd the _rst perfect matching.
Proof
Here in the Bipartite Graph G , we assume with Weight W i,j , there exists the negative cycle C in
HM as proved in previous solution. We set the M ← M ∆C. In order to find the shortest
11

Design Analysis of Algorithm
augmenting time for matching in the negative cycle we use the result of Bellman –Ford
algorithm, which runs on O(mn) time. According to previous discussion we will get the
M←{ maxi , j, Wi.j}
Now directing the edges from left to right , putting weight we on it, here T(n) is the time to find
the negative weight cycle , as through Bellman result the maximum matching is at n/2 in
Bipartite graph.
So by above rule we get the Mw PM. Now it is given that W := maxe2 Ejwej, so according to
the above specification the naïve bound on the runtime of the above algorithm would be
O(nW) . T. Here the time for calculating the first perfect matching be let T1 (n). So the timing run
time of above algorithm will be – T = O(nW)+ T1(n).
(c) For matching M, denote w(M) := P e2M we. Show that if w(M) > w(M) then
there exists a cycle in HM with weight-ratio1 at most w(M)􀀀w(M)
n , where M_ is a min-weight perfect matching.
Proof
Here now using the above specification
Let for matching M the Weight w(M):= P e2M we , where P is the perfect path for perfect
matching. A matching in graph G is the set M is a subset of E such that no two edge in M share
12