NP problem

[Samanatha123]

A workplace has a set of n computers that are connected in pairs by a set of m cables. The longer the cable, the more expensive it is. The engineer wants to save on cable cost, so she would like to determine the minimum total cable length that ensures that each computer has a way to communicate with any other computer. Each computer must have exactly one cable going in and one cable going out.

So what I got from this problem is that it can be solved in polynomial time by determining the shortest path that touches every vertex. This can be done with the traveling salesman reduction where it will visit each vertex once and find the minimum path. But then I realized, how would this apply to this problem if the cables have to go out and in so you would be visiting each vertex more than once. In this case, is it not NP-complete?

 

[Cubist]

So what I got from this problem is that it can be solved in polynomial time by determining the shortest path that touches every vertex. This can be done with the traveling salesman reduction where it will visit each vertex once and find the minimum path.

The travelling salesman problem is NP-complete, it can't be solved in polynomial time.

But then I realized, how would this apply to this problem if the cables have to go out and in so you would be visiting each vertex more than once. In this case, is it not NP-complete?

This sounds like a directed graph to me (since there is only one "in" and one "out" per node). Therefore each node is visited once.

Even if it isn't directed, could you draw a fully connected graph where each node has two edges such that it doesn't form a single loop/ ring (see the diagram of a graph at the top of the travelling salesman link)

Therefore I think your first instinct is correct, this is the travelling salesman problem in disguise.