Matching Flashcards
Matching
Set of edges in wich vertices are not common (edges do not have any common vertex)
No two edges share a commonn end point
Relation between matching and vertex cover
every edge of the matching obtains at least one element of the vertex cover.
Relationship between matching and vertex cover
at least one vertex of the edge of the maximal matching is in the vertex cover
Rekationship between maximal matching and vertex cover
size of maximum matching is <=size of a minimum vertex cover
In bipartite graph , relationship between maximum matching and vertex cover and
Size of maximum matching is equal to the size of the minimum vertex cover
Maximum matching can be computed in poly-time
true
We can find the size of minimum vertex cover in bipartite graph in poly-time
true
Lower bound of vertex cover
Maximum matching.
size of maximum matching is <=size of a minimum vertex cover.
My vertex cover cannot be less than that
Upper bound of vertex cover
twice the size of maximum matching
If we find a maximal matching and take all matched vertices into a vertex cover solution, the resulting vertex cover is of size <= twice of the size of a minimum vertex cover
True
Vertex cover problem is solvable in polynomial time for bipartite graph
true
VC approximation algorithm for bipartite graph using maximal matching
• VC Approximation Algorithms
1- Compute a maximal matching
2- Put all the matched vertices (under M) in a VC solution S
3- return S
Advantage: Poly-time result does not exceed twice optimum (in poly-time)
Result: Vertex cover has a factor-two poly-time approximation algorithm (can be approximated within a factor 2 in polytime)
Another polytime vertex cover approximation
- Input graph G
- Output a vertex cover C for G
C empty Set
HG
While H has edges
e an edge of H
(v,w) end points of e
Add v and w to C
for each edge f incident to v or w
Remove edge
- return C
Every chosen edge e has both ends in C
But e must be covered by an optimal cover
hence, one end of e must be in optimal
Thus, there is at most twice as many vertices in C as in OPT
That is, C is a 2-opproximation of OPT
Running time O(m) : number of edges
Give an efficient a;gorithm for Vertex Cover on Trees and Forests ( Acyclic undirected graphs)
Is this problem solvable in polynomial time as optimal?
Yes, because every tree is a bipartite graph
A leaf in a tree is vertex that has only one edge (v only covers one edge which is covered by w , whenever I spot a leaf I put it is parent in the solution; delete (the leaf =vertex of degree 1 ) and continue until you consume the tree
Observation: It will be solvable efficiently on Linear time ( It will take same time as the BFS)
Spanning Tree
Tree that have all the vertices of the graphs
Minimum Spanning Tree is
Minimum Spanning Tree is a Tree that have all the vertices of the graph with total sum of weight of edges is minimum
o We are given a problem instance X that has many “feasible” solutions. We are trying to minimize or maximize some cost functions c(S) for a solution S of X. For example.
Finding a minimum spanning tree of a graph
Finding a smallest vertex cover of a graph
Finding a smallest travelling salesperson tour in a graph
An approximation produces a solution T that is called a k-approximation to the optimal solution (OPT) if
o k>=c(T)/c(OPT) for minimization
o k>=c(OPT)/c(T) for a maximization; for a clique if I find clique of size 50 and we have 100 as optimal 100/50=2; We guaranteed a 2 factor approximation.
The Travelling-Salesman Problem (TSP)
Given complete, undirected graph G=(V,E) with non-negative integer cost c(u,v) for each edge
Find cheapest hamiltonian cycle of G (Find a cycle that goes through all vertices of G such that edge cost is miunimum)
We consider two cases: with or without triangle inequalltiy
In case of triangle inequality (implies not Euclidean),if the cost c satisfies triangle inequality , it is always cheapest to go directly from some u to some w without passing by intermediate vertivces
• Euclidean TSP
In the traveling sales man problem, you are given a number of vertices with all the possible edges between them with weight on the edges, and you are looking for a cycle that goes through all the vertices so the sum of the weight of the edges on the cycle you produce is minimum (You are looking for a Hamiltonian circle so that the sum of the weight of the edges is minimum) It is like Shikri wants to travel and wants the minimum cost.
It can be proved NP-hard from reduction from the Hamiltonian circle which can be proved NP-hard from reduction from 3SAT
The approximation of TSP is also hard
We consider the EUcliden TSP
Euclidean : The way our universe is assumed to be (the straight lone distance between two points is the shortest)
o This gives us the triangle inequality theorm Meaning that if I have 3 points A,B and C; Distance from A to B is < distance from A to C to B (Euclidean Space)
Euclidean TSP has 3/s approximation
see
