0:00

[MUSIC]

In this video, we're going to be looking at another one of these problems that

you could potentially look at solving as part of your Capstone project.

Now again, we're just giving you some ideas about problems you could

potentially solve.

You could go about solving this exact problem I'm going to be talking through

which could also see some inspiration potentially from this problem for

other types of problems you might want to solve yourself.

So again, don't feel obligated to solve this exact problem

as part of your Capstone.

0:29

So, by the end of this video,

I'm hoping that you understand the problem that I'm going to suggest and then,

I hope you recognize that there's some limitations related to this problem.

So, without further ado, what problem are we talking about?

Well, let's say, I've got a large social network.

And I want to make an announcement which is able to reach everybody.

0:46

How many people do I need to have announce that?

So, maybe there's some cost associated with the number of people who have

to whenever they announce.

Maybe I just want to find the smallest number of people

to influence to convince that they need to make the announcement.

Whatever the case, I just want to find the smallest number of people

to essentially announce to the social network that something's true,

and everyone will hear it.

So, let me show you a graphic of essentially a large social network.

Everything in red here would be essentially a small set.

So, if I just have those people in red announce,

everyone's going to hear immediately.

Which means everyone in this network is either a red dot or

is directly connected to a red dot.

1:26

So, how would I go about solving this problem?

Well, the first step is understand the problem a little bit more concretely.

So now, I've formalized the problem description in that I'm now saying,

given a graph, find the smallest set of vertices S,

such that every vertex not in S is adjacent to at least one vertex in S.

So, that's again,

just a formalized way of saying the problem that we just talked about.

1:57

So, when looking at this problem on your own, I hope you found that if you

just color these two red nodes, you're in fact going to be able to reach everybody.

And what I've done here in this next version of this graphic is I've just

slightly colored all the edges to show you that there's an edge connecting

every vertex in the graph that connects to at least one of these red nodes.

So, this is pretty neat.

If I want to make an announcement to everyone in this graph and

there's a lot of vertices here,

I just have to tell these two people to make the announcement.

2:24

It's pretty cool.

So, what do I do next?

So, this is an interesting problem.

How do I go about solving it?

Well, my first intuition of this was I started doing a whole bunch

of sample problems associated with it.

And I started realizing that this had a feeling to it,

kind of like that traveling salesperson problem back in course 3.

You remember that problem, that problem was NP hard.

It's actually difficult for a computer to solve.

This sort of had the same feeling to me.

It didn't mean that that meant it was hard to solve, but

I recognized it was actually really similar to a problem known as set cover.

Set cover is actually not related to graphs.

But I notice a lot of commonalities between those, and I knew that set cover

was NP hard, or the optimization version of set cover is NP hard.

So, what I could have done is continued exploring this and try to,

essentially, find a way to solve set cover using this problem.

But it turned out to be a little bit easier for me.

It was a little bit easier because I jut explained the problem to Mia, and

Mia immediately said, well, that's the minimum dominated set.

So, she happened to know that this was, in fact, a well know problem.

And that this was an NP hard problem.

So, let's talk a little bit more about what's meant by a dominated set and

see how that connects to the problem I'm trying to solve here.

3:42

So, a dominating set has this formal definition.

If this formal definition sounds a lot like the one we were just talking about,

it really is the same, like this is really close.

So, a dominating set is that set of vertices, just as we described,

such that either you have your vertex in the set, or

it's directly connected to one of the members in the set.

4:12

The answer is yes, these are a dominated set.

But what you might notice is this may not be the smallest.

What I want you to do is just take a moment.

And see if you can think of what might be smaller.

4:25

All right.

So, if you recognize that you could actually just color these two, that,

in fact, would be the minimum dominating set.

Just these two nodes.

And now, I've rephrased my problem here in blue

to be the minimum dominating set problem.

And if again,

this sound a lot like our initial problem of us trying to make an announcement to

4:55

Well, I already have a really big hint.

And that I got is what I got from Mia,

which is that this is a known problem and it's a known NP hard problem.

Now, I happen to know Mia, and

she has this encyclopedic knowledge of NP hard problems.

But what do you do when you don't know someone like that?

Well, you would have continued on the same path I was already on.

And what you could do is write a proof showing

that this is in fact an NP-Hard problem, and I would have to say that because it's

all a set cover using a solution essentially to minimum dominating set.

Now, that's not for the faint of heart.

If you have a really strong mathematical background,

you can always feel free to dive into that.

But it is a bit difficult.

Your other option,

this is actually the one I recommend the most, is just do some more exploration.

Look in various text books or websites about graph algorithms to see if there's

some similar problems related to the one that you're trying to solve and

I bet you'll find something.

Graphs have been really well studied over the years.

There are a lot of different problems that have been studied.

So, it was actually a really good text for NP complete slash NP hard problems,

and it's Computers and Intractability by Garey and Johnson.

This book has a number of known NP hard problems and in fact,

included minimum dom name set.

So, if you have access to it, I highly recommend it.