Network design algorithm

Hi,

I need an algorithm to design the most efficient way of converting an existing set of PC's in a network to server's so that the network has the minimum number of servers such that every machine in the final network is administered by at least one of the machines converted to a server.

Consider this:
If I have 5 computers (A,B,C,D,E).
There are 4 paths that connect them say:
A B
A C
B E
B D

In this case most efficient way would be to convert A and B to servers as the remaining machines are connected to these 2.

Please help.

Hmm... it's not easy to draw graphs here...

C - A - B
E - B - D

Do you really have a physical network like that? Well theoretically, I suppose these could all be routers, in which case this might make sense. Usually however, what you really have are machines on subnets in a network and you can generally ignore the routers and switches for purposes of most distributed computing systems.

Given only your original post, I think you should begin studying graph theory. You will probably find that you need to solve one of the many subgraph problems and that is is likely to be an NP complete kind of problem, but there are efficient enough solutions/approximations available.

I suspect that your problem description is not complete enough. You probably don't have a wiring scheme that matches your example if A and B are not already setup as routers of some kind. If this is a homework assignement, you might as well post the assignment so we can actually assist you in learning how to solve the problem.

Hi jwdonahue,

Here is the complete question.

You will be given a list of machines which have a direct connection between them. You need to compute the least cost that the company needs to incur so that every machine in the final network is administrable by at least one of the machines converted to administrative machines.
Input

The first line of input will contain an integer 't', the number of test cases (1 ≤ t ≤ 100). Each test case starts with a blank line followed by an integer 'n' which specifies the number of connections between machines (0 ≤ n ≤ 100). Each of the 'n' lines that follows contains a pair of upper-case characters between A and Z that are separated by a space. Each distinct character represents a machine.
Output

For each test case, your output should contain the least amount of money in dollars that you need to spend so that every machine in the network is administered by at least one administrator machine.
Example

Input:
1

4
A B
A C
B E
B D

Output:
200


Explanation: In this case, the least cost you have to incur is $200 and it can be achieved by converting machines A and B to administrative machines.

Need an algorithm to figure this out. Any help will be appreciated.

It's called minimum vertex cover, and it is NP-complete. The link provides an approximation algorithm, but it apparently cannot be approximated arbitrarily well.

However, I'm a bit puzzled by the fact that the problem requires each computer to be "administered by" a server; it never says that each computer must have a direct connection to a server. The two are not necessarily the same.

What algorithms have you considered so far?
Have you tried manually working the problem and writing down the steps you take to come up with the solution?

Here's my simple minded interpretation of the input data:

Number of test cases.
Number of edges (E) in the network graph.
A list of edge labels that also contain all of the vertex labels (implied by the format of the edge labels) and some vertices may be listed multiple times. So "A B" is an edge label for the link between vertices A and B.
There is no cost metric, but the example seems to imply a cost of $100 per server.

First step is to always clarify the requirements. Never assume anything. There's lots of mathematical ways the listed example could cost $200 without holding to the $100/server relationship (particularly if cost/server goes up or down with the number of servers). Perhaps your teacher doesn't care what metric you use provided you code and document this consistently? Ask them!

Lets ignore the multiple test case processing overhead for now and just focus on a single test case. The data supplied is sufficient to construct a complete graph right? So your first order of business is write down the algorithm you use to draw the graph based on the supplied data, then convert that to computer terms; constructing either a number of edge objects (with node labels) or a number of nodes (with edge labels). Which of those two solutions you pick will depend on the algorithm you choose to solve this problem (I am pretty sure there's more than one).

Post your results here, someone will continue to assist you. Don't allow your mind blocks to halt progress in areas where you can make progress. This problem can be decomposed into smaller pieces that can be solved independently of each other.

I was thinking of creating a NxN matrix where N is the number of nodes. In this case N=5. Then storing a value say 1 when a connection exists between 2 nodes and 0 when there is no connection. Then selecting the nodes which have the maximum total if I add the values of all the elements in the individual columns. This will give me the nodes with the most connectivity.

Would this be a feasible/efficient solution?

But then how would I find out efficiently how many of these nodes with most connectivity(administrative machines) would I need to administer the whole network. And how would I efficiently select other nodes as administrators that are not connected to any of these nodes with high connectivity?

Sorry for not mentioning this first. But there is a cost of 100$ per server.

It's natural to go down that route, but nobody so far has ever turned that idea into a correct and efficient algorithm. Will you be the first?

Actually, you know what? We're all dunces. Consider each way to pick one server out of the bunch and see if any covers your network. If not, consider each way to pick two servers and see if any covers your network. If not, move on to three servers, four servers, etc. Since the machines are labeled by uppercase letters, A, ..., Z, there are at most 26 machines. A set of 26 items has 2^26-1 = 67,108,863 nonempty subsets, about 67 million. That's how many possible ways there are to select machines to be servers. In the worst case, you end up testing all 67 million, which is actually not that bad, provided that you can efficiently determine whether a given selection of servers covers the network.

Lux is correct here. The brute force method is probably computable on the order of tens of kilowatts or less energy which is pretty good for this class of problems. Lets assume however that you are going to score extra points for a "greener" solution that has some hope of scaling to hundreds or thousands of nodes.

So close and yet so far.

The matrix that you propose is a natural enough solution until you start thinking about the memory it consumes. 5^2 or even 26^2 isn't too big a number, but what about 1000^2? How much memory will 1M node records consume? How does that impact performance? There's a better way to store the data.

I'll give you some clues here. What are binary trees used for? Must they always be balanced? How do you decide whether to insert left or insert right? How do they behave when the source data is either sorted or not sorted? You have a list of edges that just happen to have node labels embedded in them. Can you use that to your advantage?

I am a bit confused. In a binary tree a parent node always has a maximum of 2 child nodes right? How can this help if a node in a network has more than 2 connections?

Hmm... lets see... did I say anything about any one to one relationship between vertices in your network graph and nodes in the binary tree? Anyway, I was trying to get you to think about this without completely spilling the beans. Such a one to one relationship might actually be part of the solution but I suspect there's more than one way to do this. In any case, you're going to get more out of this if you come up with your own solution. I am only trying to nudge you in the direction of a more or less optimal solution without having to implement a amoeba or other optimizing function.

Lets say you have a list that looks this:

B A
D B
C A

Each of those lines is effectively an edge label. The node/vertex names on the ends of the edges are simply encoded in those labels. Because the edge labels are constructed from the node names you can rename edges and still have an equivalent network:

A B
A C
D B

So now we have two lists of edges that describe exactly the same network right? Those edge labels are nothing more than simple strings. I just want you to think about the properties of those strings and how they relate to a network graph and how you might construct other abstract views of the same data. Tree structures are often used to sort and count things. They do not have to be balanced and there is no requirement that every node be unique either. The nodes themselves are just containers. You can put anything you want in them. The structure you wind up with depends on your criteria for pushing left or right and on the order of the data that is presented, so you might get different tree shapes using those two lists I presented if the sorting criteria is a simple string comparison right?

In the second list I made two permutations from the first list. First I normalized the edge labels so that the node with the lower character in the alphabet was on the left, instead of accepting the random order of the original and then I sorted with a simple string comparison. Can you think of any other ways to sort the list? Any attribute that might be important to selecting servers?