Vertex Cover

Loading...

From the course by University of California San Diego

Advanced Algorithms and Complexity

247 ratings

University of California San Diego

Advanced Algorithms and Complexity

247 ratings

Course 5 of 6 in the Specialization Data Structures and Algorithms

You've learned the basic algorithms now and are ready to step into the area of more complex problems and algorithms to solve them. Advanced algorithms build upon basic ones and use new ideas. We will start with networks flows which are used in more typical applications such as optimal matchings, finding disjoint paths and flight scheduling as well as more surprising ones like image segmentation in computer vision. We then proceed to linear programming with applications in optimizing budget allocation, portfolio optimization, finding the cheapest diet satisfying all requirements and many others. Next we discuss inherently hard problems for which no exact good solutions are known (and not likely to be found) and how to solve them in practice. We finish with a soft introduction to streaming algorithms that are heavily used in Big Data processing. Such algorithms are usually designed to be able to process huge datasets without being able even to store a dataset.

From the lesson

Coping with NP-completeness

After the previous module you might be sad: you've just went through 5 courses in Algorithms only to learn that they are not suitable for most real-world problems. However, don't give up yet! People are creative, and they need to solve these problems anyway, so in practice there are often ways to cope with an NP-complete problem at hand. We first show that some special cases on NP-complete problems can, in fact, be solved in polynomial time. We then consider exact algorithms that find a solution much faster than the brute force algorithm. We conclude with approximation algorithms that work in polynomial time and find a solution that is close to being optimal.

Vertex Cover9:13

Metric TSP12:50

TSP: Local Search6:18

Meet the Instructors

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Michael Levin
Lecturer
Computer Science
Daniel M Kane
Assistant Professor
Department of Computer Science and Engineering / Department of Mathematics
Neil Rhodes
Adjunct Faculty
Computer Science and Engineering

Hello, and welcome to the next and

actually the last lesson in the Coping with NP-completeness module.

In this lesson we're going to design approximation algorithms.

Such algorithms work in depending on the size of the input and plus their return.

Is might not be an optimal solution but

it is guaranteed to be a solution which is close to optimal.

The first problem for which we are going to design an approximation

algorithm is called the vertex cover problem.

The input of this problem consists of a non-directed graph.

And what we'd like to find is a subset of its vertices of minimum size,

which touch or covers every edge.

To give a specific example, consider the following graph of eight vertices.

Well for any graph, we can take all the vertices into a cover.

This is clearly a vertex cover, it touches every edge.

And the other thing is, in this graph, we can also take the following six vertices.

It is not difficult to see that each edge is touched by green vertices.

And an optimal vertex cover in this case consists of the following three vertices.

Again, it is not difficult to check that for each edge,

at least one of its endpoints is green.

For example, for this edge, it is covered with this vertex.

For this edge, it's covered with two green vertices, and

there are no vertices that was not green, they are connected by a niche.

So the green set of vertices indeed touch every edge.

The approximation algorithm for

this problem that we are going to consider is surprisingly simple.

Namely it works as follows.

Initially our Vertex Cover is empty, so, we initialize C as an empty cell.

Then we repeat the following while the set of edges of our graph is not empty.

We select any edge denoted by u,v of the current set of edges and

then we add these vertices to the set C.

Then we remove from the graph all edges that are already attached by U and V.

So we remove all edges that are adjacent to U or V.

So we repeat this while there is at least one edge in E,

and when E is empty we just return C.

Let me illustrate this on our previous graph.

So first assume that we select this red edge.

Then we add its two vertices to a solution, and

then we remove from the graph all edges adjacent to these green vertices

because they are already covered.

We did not need to cover them.

Then we select some other edge, for example this one,

we add to its endpoints in the solution, and we remove all edges

that are adjacent to these two newly added green vertices.

So this leaves just one edge in our graph, so we select it, and

we add two vertices into our solution.

And we get the following,, the following solution consisting of six vertices.

So just to show that it is indeed a solution,

let me show you the initial edges of the graph.

So we see the green vertices,

the six green vertices indeed cover all the edges of our initial graph.

We are now going to prove that the present algorithm is 2-approximate.

This means that the running time of this algorithm is pretty normal and

also that the solution, which is found by this algorithm,

is at most twice as large as the optimal solution.

Well the fact that the running time of our algorithm is polynomial is clear

just from its implementation.

In fact, its running time is linear.

So we proceed to show that it returns a solution, which is at least at most,

twice as large as an optimum one.

First observe that the set of edges selected by our algorithm

is it forms a matching.

This means that all the end points of edges selected by our algorithm,

the end points of all the edges are just joined.

Why is that?

Well, assume that this is the first edge selected by our algorithm.

So this is u, v.

Recall that after selecting this edge, the algorithm,

discards all the edges adjacent to u and v, which means that for this algorithm,

Neither this, neither this and point coincides with u of v, neither this one.

This is also, this also means that any vertex cover must take at least

one vertex from each of these edges, which in turn means that any vertex cover of our

graph must If you have size, it leaves the current analogy, or the size of M, right?

Now that the same times that we know the size of the vertex covered returned by

our algorithm.

It equals to just 2 times the size of M.

This is just because the size of M is the number of edges

in the set M and each edge has two vertices, two end points.

So this allows us to conclude that the size of the vertex cover found

by our algorithm is equal to 2M precisely.

And we know that M is at most the optimum value,

the size of the optimum vertex cover.

So 2M is at most two times OPT which justifies that what our algorithm returns

is a vertex cover whose size is at most twice the size of an optimum vertex cover.

Let me also show you the set of edges selected by our algorithm

in the previous example so it selected the following three edges.

And you can see that indeed, all these three edges form a matching.

So the end points of these three edges are disjoined.

And this also means that to cover these three edges,

we must take at least three different vertices.

So we must take either this vertex or this vertex to cover this, to cover this edge.

And this will not help us to cover any of the other red edges right?

So we also must take either this vertex or this vertex and

then either this vertex or this vertex.

In total, at least three vertices.

Let me emphasize here the following thing.

So we have somehow managed to prove that the size of the vertex cover

constructed by our algorithm is at most 2 times the optimal value.

At the same time, note that we do not know the optimal value.

We do not know how to compute it in polynomial time.

So our algorithm runs in polynomial time.

So we don't know how to compute optimal polynomial time.

So our algorithm doesn't compute it.

However, what it computes is that we know for

sure that it is at most twice times the optimal value.

So how it can possibly be that we proved some upper bond on

C in terms of OPT without knowing the exact value of OPT?

Well, this is because we know some lower bond are not and

it is the size of the matching that we constructed.

So the size of M gives a good lower bound on OPT.

More over the matching M can be used to construct some vertex cover.

And just by taking all the end points of these M edges we get a vertex

cover whose size is twice the size of M so this gives us the final lower bound.

So C is equal to two times M, which is, in turn, at most, two times OPT.

So this allows us to prove an upper bound on C.

Not in terms of some quantities that we don't know, namely OPT but

in terms of the size of M which we can compute quickly and

which we can use to construct the vertex cover.

Let me conclude this video with a few remarks.

So first of all the bound we've proved that

our algorithm is to approximately tied.

This means that there are graphs for which our algorithm will return,

an answer which is exactly twice as large as an optimum vertex cover.

And this can be viewed as follows,

lets just consider a full, well a full bipartite graph.

Or we can just, just consider the following bipartite graph, okay.

Assume that we have n vertices here and n vertices here.

So our algorithm is going to do the following.

So with each step, it will select one vertex, one edge, and

add the both vertices to the solution.

So in the end it is going to return a solution of size 2n, right?

At the same time all the edges of this graph

can be covered just by one of its part.

So there is a solution of size m, but our algorithm returns a solution of size 2m.

The last remark is that surprisingly,

this algorithm is almost the best one that we know.

In particular, we do not know how to find an approximation of this algorithm with

the factor 1.99, for example.

Explore our Catalog

Join for free and get personalized recommendations, updates and offers.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2019 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play