Design Analysis of Algorithm

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

Design Analysis of Algorithm
Table of Contents
Solution Exercise 1 1
Solution Exercise 22
Solution Exercise 3 3
Solution Exercise 4 4
Solution Exercise 55
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