THE SOCIAL CIRCLE

OF

EMILY

THE SIBERIAN CRANE

The Siberian cranes have come for their yearly visit, said Baby Bear excitedly.

Emily the Siberian Crane is here, barked Mickey the Lapso.

 

How are you faring, Emily? asked Mama Bear.

I am having a problem, said Emily. It is in keeping track of all my friends.

Tell me your problem, said Papa Bear to Emily.

We visit so many places and countries, said Emily. Over 100 of them and everywhere I have friends.

That is only natural, said Grandma Bear.

The problem is keeping in touch with all of them, said Emily. At least I would like to keep some channel open.

What do you mean by channel? asked Uncle Bear.

I would like to find out how my friends are faring, said Emily.There must be some way of news about them reaching me.

It is difficult when the circle of friends becomes hundreds and thousands, said Grandma Bear.

What you should do is to isolate some key persons in each area, said Uncle Bear. These are persons who have a wide circle.

If you know a key person, he or she will keep track of a large circle of your friends, said Mama Hippo who had walked in.

You only have to keep in touch withy these key persons, said Baby Elephant. Together they will keep track of all your friends.

How do I find how many of these key persons I should keep track of? asked Emily.

Yes, when the circle is large, over 40, it is difficult, said Grandma Wolf. You can consult Uncle Owl in the middle of the forest.

Emily goes to Uncle Owl.

What is your problem, Emily? asked Uncle Owl.

I want to find out key friends, said Emily. Through them I will know about all my friends.

Yes, finding the smallest set of key friends is difficult, said Mama Owl.

You will find you do not have the time, effort or money to determine the key persons, said Grandma Owl.

It is a very difficult problem, said Uncle Owl. No Crane has ever been able to determine the set of key persons.

The time is not enough to try all the possibilities, said GreatGrandpa Owl.

Many Wise Owls all over the Global Village have studied the problem for centuries, said GreatGrandma Owl.

There is a solution but King Lion has forbidden it, said Auntie Owl.

There is a magic potion to be taken by Emily the Baby Crane, said Papa Owl.

The Wicked Wizard on the mountain supplies this, said Baby Owl.

Emily can take this magic potion, said Grandma Owl. Then she will become Emily the Baby WizCrane.

She can make multiple copies of herself when there is a choice of key persons, said Papa Owl.Each copy takes a different path.

All copies act in parallel, said Baby Owl. A copy when it has a choice makes copies of itself.

Only the copy that succeeds counts, said Auntie Owl. The copies that fail do not count.

Emily the Baby WizCrane can thus easily do what Emily the Baby Crane cannot do, said Papa Owl. She can easily identify the set of key persons, said Mama Owl.

King Lion has forbidden the use of the magic potion, said Grandma Owl.

There is an alternative, said Uncle Swan family. Baby Swan has been keeping track of friends in over a hundred places.

She consults the clever Hippo family, said Mama Bear. The Hippo family though very lazy is very clever in guessing the key persons one should keep track of. They are gifted with this skill, said Auntie Bear. They have been in the business for generations.

Baby Pelican visits the Hippo family.

Here is your the list of key persons, said Baby Hippo to Emily.

All the animals in the forest are excited about the the solution, said Mama Wolf.

They go to the Wise Owl.

Give us some details about the solution to Emilys problem, said the animals to the Wise Owl.

The magic potion may really not be useful, said Papa Owl. Also magic potions are dangerous in the long run.

However nobody knows if Emily could have managed without the magic potion, said Mama Owl.

How should we manage in case they want to visit all our relatives exactly once, asked the animals.

The problem Emily the Baby WizCrane followed to visit all the relatives is called a Vertex Cover Problem, said Grandpa Owl. In case they ever come across a similar problem they should be careful.

The problem is like the Big Bad Tiger, said Mama Owl. "If they ever see the Big Bad Tiger on the road then they should avoid him.

You should take to the side paths and muddle your way to get home, said Papa Owl. This does not always guarantee the Big Bad Tiger will be avoided.

It works in most cases, said Baby Owl.

The same thing should be done if you have to find the Vertex Cover Problem, said Grandma Owl.

You should try trial and error methods, concluded Papa Bear.

This is the famous Crane = WizCrane debate and problem, Uncle Monkey told King Lion.

 

It is the most famous problem of the 21st century, said Professor NitWit.