Problem $2$

We have a computer network with n computers. For each pair of computers we know whether

this pair is directly connected by a cable. The cables are bi$-$directional, that is for a cable

connecting computer A to computer B$,$ we can route a packet from A to B$,$ or from B to A$.$

To protect this network, we would like to monitor the traffic through all the cables. We

will designate some of the computers as $$trusted$$ a software engineer will be assigned to

each trusted computer and they will monitor the traffic through all the cables the trusted

computer is directly connected to$.$ However, such monitoring is expensive. Therefore, we

want to designate as few computers as trusted as possible while still monitoring every single

cable in the network.

Professor Smart came up with a brilliant plan: Let$$s designate as trusted the computer

that is directly connected to the largest number of other computers $($if there are more such

computers, choose one of them$).$ Then pretend to remove this computer and all its cables

from the network, getting a smaller network. Repeat this process, designating the next

trusted computer, while there are still cables in the network.For example, if our network has four computers A$,$ B$,$ C$,$ and D$,$ and the pairs of computers directly connected by cables are $($A$,$B$),($A$,$C$),($B$,$C$),$ and $($C$,$D$),$ then Professor Smart$$s

algorithm would designate computer C as trusted, since it is connected to three other computers. After removing C and its cables, we are left with a single cable connecting A and B$,$

so the algorithm would designate one of these computers as trusted $$ maybe it chooses A$.$

We would have two designated computers, A and C$,$ which is the smallest possible number

of computers covering all the cables in this computer network.

$$ Give a pseudo code for Professor Smart$$s algorithm. In particular: Specify the variables and$/$or data structure$($s$)$ in which you store the input data. Give names to the

main data structures and variables in your pseudo code. Write the pseudo code using indentation, while$-$ and$/$or for$-$loops, if$-$conditions, and other typical pseudo code

keywords.

$$ Estimate the algorithm$$s running time using asymptotic notation as a function of n

and reason your estimate. Aim for a low polynomial estimate $($it does not have to be

optimal$).$

$$ Does the algorithm work? That is$,$ does it always produce a smallest set of computers

that cover all the cables? If not, provide a counterexample. That is$,($a$)$ draw a

computer network on which the algorithm fails, $($b$)$ trace the algorithm on your example

and show the algorithm$$s output $($the set of computers it chose $$ it is ok to assume

that the algorithm made a $$bad choice$$ when having multiple computers to choose

from$),$ and $($c$)$ highlight an optimal solution $($a smallest set of computers that cover all

the cables$).$

Note: This problem is known as the Vertex Cover. We will learn more about it later in the

term.