Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I have a problem in my mind, I think it is a NPC problem but I don't know how to prove it.

Here is the problem:

There are k islands in a very big lake, and there are n fan-shaped pontoons. Those pontoons are in the same size but have different initial directions and are in different original positions in the lake. The pontoons can rotate freely around its center of mass, and no cost associated with rotation.

Now we need to move those pontoons so that all islands in the lake can be connected. We can guarantee the number of pontoons is enough to connect all the islands.

[Note]: We cannot reuse the pontoons!!

The task is to find the solution having the minimum total distance of the moving pontoons in order to make all islands connected. The distance of moving one pontoon can be calculated as the distance between the center of mass's original position and its deployed position.

To make it clear, I have drawn such a figure. Suppose we have 3 islands A, B and C. They are located somewhere in the lake. And I have several fan-shaped pantoons. Now the solution is to find a minimum moving distance summation to connect A, B and C, shown in bottom part of the figure. Hope it help understand the problem. :)

enter image description here

It seems that the problem is a NPC one, but I don't know to prove it. Can anyone help me on this?

share|improve this question
    
@vsaxena No, I don't think the final solution is a straight line, sometime if already form an arch but we don't need to move any of them. Most of the cases, a straight line will be good, but as the pontoons getting denser, the solution may not be a straight line. The figure is just an example. :) –  little-eyes Jun 6 '12 at 20:51
1  
Seems very close to Steiner Tree. In a metric space, many techniques to solve work on both. en.wikipedia.org/wiki/… –  Nicholas Mancuso Jun 7 '12 at 2:16
    
@NicholasMancuso the bridges are node to node so it is not a classic Steiner tree where the bridge connects multiple nodes. There are many problems in VLSI layout which have similar characteristics. –  VSOverFlow Jun 7 '12 at 6:40
1  
@vsaxena: The problem is underspecified. Suppose I have three islands A,B,C in an equilateral triangle, and the pontoons initially form a connected Y shape with the islands at the ends. Is doing nothing a valid solution, or must the pontoons be moved further? If this solution is not valid, then what precisely constitutes a valid configuration of the pontoons? –  JeffE Jun 7 '12 at 17:30
1  
@vsaxena: And while we're at it, are the islands just points, or circles, or some more complicated shape specified in the input? Are the pontoons line segments, or ellipses, or some other shape? Are all islands the same size and shape, or can they be different? Are all pontoons the same size and shape, or can hey be different? –  JeffE Jun 7 '12 at 17:35
show 3 more comments

migrated from stackoverflow.com Jun 6 '12 at 23:20

This question came from our site for professional and enthusiast programmers.

3 Answers

First: This is not the Travelling Salesman Problem. The TSP requires the identification of a minimal weight Hamiltonian cycle; this cycle does not require a cycle, or even a minimal weight path at all. It requires a minimal cost construction of a connecting set of edges, where the construction cost is based on moving the pontoons around.

Second: This is not the Minimal Weight Spanning Tree Problem. See above-- we require a minimal cost construction not minimal weight identification.

Third: It seems that the constructed path will be a spanning tree, but not necessarily a minimal weight one. The alternative is that it would be a spanning tree plus some additional edges resulting in a cycle; but if we start in a configuration with no edges, then every edge has some positive cost and we can always find a lower weight spanning tree by simply not constructing the extra edges.

Fourth: You say the pontoons rotate freely; I assume that means that no costs is associated with rotating the pontoons. However, you do not specify what the pontoons rotate about: Their points? Their centers of mass? Any internal point? (If any external point, then we would have zero weight constructions, yes?)

This is a little bit subtle, because if we're rotating 90 degrees about an internal point, say, the center of mass, what is the cost? Nothing, because it's a rotation? Some finite amount because the point moved? Now we also need to know the size of the pontoons.

Fifth: One assumes both the pontoons and the islands both are embedded in the Euclidean Plane?

share|improve this answer
    
Thanks for your answering. The rotate is around the center of mass and no cost associated with rotation, only movement involves cost. Yes, both pontoons and the islands are embedded in the Euclidean plane. I will modified the post to make it clear. –  little-eyes Jun 6 '12 at 20:57
    
I disagree that this is not essentially the TSP. This whole post is wrapped around the axle in terminology, but the fact of the matter is that if one drew a line between each pontoon and each potential end pontoon position, and calculated the distance of each line to be it's weight, then with the exception of the end point getting back to the starting point, the graph that is formed looks almost exactly (to a tee) like the TSP. A pontoon or an end position is a node in the graph, and the weights are made up by the distances. The hamiltonian cycle ONLY means it ends where it started. –  trumpetlicks Jun 6 '12 at 21:09
2  
This is not an answer, but a series of comments. –  Raphael Jun 7 '12 at 13:04
add comment

After looking at the new diagrams, I see that you may need multiple pontoons to cross between islands. Given that, you could get very close to a solution of the Steiner Tree problem by turning the nodes into islands and creating a sufficiently diverse collection of pontoons with small arcs. Wikipedia says that there is in fact a PTAS for the Steiner tree problem, so I can't say immediately that this renders it NP-complete. However looking at the details of the Steiner tree might either get you a good approximate solution or show that the problem is NP-Complete.

share|improve this answer
    
What you are describing is an approximate algorithm to get to a near optimal solution. However how do you even verify that the solution is optimal? –  vsaxena Jun 6 '12 at 19:36
    
I think the real problem is that you need multiple pontoons to cross between islands, which makes this look a lot like a Steiner tree. Have a look at Branch and Bound for how to go from a lower bound (e.g. generated by neglecting a constraint) to a known optimal solution. –  mcdowella Jun 7 '12 at 4:25
2  
@mcdowella It is not a Steiner tree since each pontoon can appear in only one bridge; it is a point to point system. Further since the cost function is the movement of pontoons, you can have a case where the bridge is formed in wide arcs which still have a lower cost than the straight line solution.. –  VSOverFlow Jun 7 '12 at 6:37
    
This cannot possibly be the steiner from another perspective. WE CANNOT ADD POINTS just to suit our needs. –  trumpetlicks Jun 7 '12 at 14:04
1  
If Y junctions are allowed this is at least as hard as the Steiner tree problem, because any Steiner tree problem can be turned into one of these- just create a lot of pontoons and put them so far away from the islands that it doesn't really matter which pontoon you use where. Then if you could solve this, you could solve the Steiner tree problem: for this argument it doesn't matter that there are some configurations of pontoons which do not result in Steiner tree problems. If Y junctions are not allow we need to know exactly what the rules are. Do the paths cross at the junction? –  mcdowella Jun 7 '12 at 18:46
show 1 more comment

After the drawing, This is still an NPC problem. Even if we cut the problem down to each pontoon can assume 1 of n positions (i.e. known connection lines. To get the most optimal answer, we would have to try each pontoon in each position, adding their distance to get to those repsective positions each time, and comparing against all others. if each pontoon has to be tested in each position, then there are n! combinations needing to be tested.

Ive chosen to edit the original poster's images with some additions to show the graph ideas behind this problem.

The below image shows all (minus 2 to make it simpler) pontoons in differing colors, with all potential pontoon end locations in RED. I have only drawn the lines between 3 pontoons and all of the end locations, but one could see how CRAZY this could get.

Say that just for the heck of it, we choose for the turquoise pontoon to be placed at the end location closest to it as the first step (although FROM THE TSP we know that this may not be optimal in the end).

Below we see exactly that, the pontoon and the distance (a.k.a. weighted traveling distance) it will have to travel.

enter image description here

From here a virtual node with the two end locations next to the just placed location may be made. Distance from the set node, and the two adjacent nodes within the virtual node have a virtual travel distance of 0.

Below we see the virtual node created with ALL potential travel distance weights that can be placed there.

enter image description here

Seeing how this would continue, and how the most optimal solution (as seen many times with the TSP) will not always be by choosing the shortest distance for every choice, we would have to test essentially all paths for all nodes / virtual nodes.

In the end the first node of the (TSP) problem could be any one of the potential end pontoon points, and the lines drawn from that are the distances from that endpoint to all other pontoons. all other nodes afterwards become virtual nodes as I have depicted with their lines coming off as the distances / weights to all remaining pontoons, and so on and so forth. How this graph problem is NOT EXACTLY the traveling salesman problem without the LAST JUMP requirement from the hamiltonian cycle is beyond me. In order to have the exact answer one must test all paths through the graph.

share|improve this answer
1  
Leaving aside whether this is a reasonable model of the stated problem or whether this is even actually a TSP model, this is not how NP reductions work. You don't show that your target problem can be framed as an instance of an NPC problem. You need to show that an instance of an NPC problem can be framed as your target problem. –  mhum Jun 6 '12 at 23:13
3  
It seems that your understanding of complexity is deeply flawed. Size of search space is not the same as computational complexity. There are plenty of problems that can be solved without brute-forcing the matter, that is without checking every element of the solution space. Sorting was one example. Or take Vertex Cover, another NP-complete problem: it can be solved in worst-case time $O(1.3^n)$, so clearly without checking every subset of nodes. –  Raphael Jun 7 '12 at 15:36
2  
Oh dear. If you had bothered to read my comment and the link I provided, you had learned that the referenced algorithm is exact (they prove that) and therefore contradicts your understanding. Note that your opinion suggests that P!=NP -- this is still an open question. So no, you have not understood this, sorry. (Even if it were true that NP-complete problems could be solved no better than naively, the reasoning you use would be wrong.) –  Raphael Jun 7 '12 at 16:05
2  
@trumpetlicks: There is no contradiction. The algorithm Raphael refers to solves the NP-hard vertex cover exactly in $O({1.3}^n)$ time, which is exponential in $n$, but not by brute force enumeration. More importantly, though, "NP-complete" does not mean "I can't see how to solve it in less than exponential time." –  JeffE Jun 7 '12 at 16:38
3  
@JeffE: In other words, this answer only proves that the problem is probably-istically NP-complete. –  Tsuyoshi Ito Jun 8 '12 at 12:40
show 9 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.