Would this be an NP complete problem?

[LightCode Gaming]

Say you have n location that you need to get to, but you want the shortest route/connection/whatever.

You are allowed to only have 2 things connected to any location at one time, but you can have as few as 1. All points must have a "connection" to the rest, be it directly or through traversal of the other points.


Is this NP or NP-complete?

[WanderingFool]

Perhaps it's been too long since my algo classes and graph theory, but is there additional information for the problem?

 

Say each location is a vertex, so you have n vertices.

 

How are they connected?  Are the edges (paths/roads) connecting two points a-b defined already/are there one way edges?

 

I could be wrong, but I would imagine there might be a way to set this form of a question up as a flow network.  If this could be setup as a flow network (in polynomial time), then it may be a polynomial time (Minimum-cost flow problem).

 

I hope this helps, or at least sparks a bit of insight into the problem.

 

If it is an NP problem, then I would just try thinking of a way to formulate it into a 3-sat...thus making it a np-complete problem

[fizzlesticks]

So it's the traveling salesman problem but the first and last node don't connect to each other?

[LightCode Gaming]

Perhaps it's been too long since my algo classes and graph theory, but is there additional information for the problem?

 

Say each location is a vertex, so you have n vertices.

 

How are they connected?  Are the edges (paths/roads) connecting two points a-b defined already/are there one way edges?

 

I could be wrong, but I would imagine there might be a way to set this form of a question up as a flow network.  If this could be setup as a flow network (in polynomial time), then it may be a polynomial time (Minimum-cost flow problem).

 

I hope this helps, or at least sparks a bit of insight into the problem.

 

If it is an NP problem, then I would just try thinking of a way to formulate it into a 3-sat...thus making it a np-complete problem

 

 

So it's the traveling salesman problem but the first and last node don't connect to each other?

It is like a network flow, but limited directions. You can only have 2 edges per node tops. 

And yes, its like the traveling salesman without the first and last connecting.

[madknight3]

It is like a network flow, but limited directions. You can only have 2 edges per node tops. 

And yes, its like the traveling salesman without the first and last connecting.

 

Do you have to travel to every node? Can you visit the same node more than once?

 

If there's no other difference to the travelling salesman problem, wouldn't it have the same complexity? That being that the optimization problem is NP-Hard and the decision problem is NP-Complete?

[LightCode Gaming]

Do you have to travel to every node? Can you visit the same node more than once?

 

If there's no other difference to the travelling salesman problem, wouldn't it have the same complexity? That being that the optimization problem is NP-Hard and the decision problem is NP-Complete?

But there is a difference; you don't have to make a round trip. Oh, and you don't get to set the start/end point either. 

Let me try to explain it better.

You have n location. You have to hit each location once and only once, and you have to hit all locations. You want the shortest path.

Here is a visual example.

1_2  3_4

     |   |   |

5_6  7  8

|            |

9_a_b_c

[madknight3]

- snip -

 

It sounds to me like a shortest Hamiltonian path problem. To satisfy the start/end requirement, you can add a temporary node and edge to start/end nodes if necessary. The problem would remain the same.

[LightCode Gaming]

It sounds to me like a shortest Hamiltonian path problem. To satisfy the start/end requirement, you can add a temporary node and edge to start/end nodes if necessary. The problem would remain the same.

But is it an NP problem?

[madknight3]

But is it an NP problem?

 

Well technically, for a problem to be NP or NP-Complete it would have to be a decision problem. You have phrased the question as an optimization problem. This paper, assuming it's correct, says that the longest Hamiltonian path problem is NPO-Complete. I could be wrong but I believe that would also apply to the shortest Hamiltonian path problem.

[LightCode Gaming]

Well technically, for a problem to be NP or NP-Complete it would have to be a decision problem. You have phrased the question as an optimization problem. This paper, assuming it's correct, says that the longest Hamiltonian path problem is NPO-Complete. I could be wrong but I believe that would also apply to the shortest Hamiltonian path problem.

Would NPO be comparable to NP in any way? Like, if we got a really good algorithm for NPO, could it be used on an NP to be faster than (I think it was) (N!)?

[madknight3]

Would NPO be comparable to NP in any way? Like, if we got a really good algorithm for NPO, could it be used on an NP to be faster than (I think it was) (N!)?

 

If a decision problem can be extended to an optimization problem, then the algorithm for the decision problem would be at least as efficient, if not more efficient than the algorithm of the optimization problem. It may even be guaranteed to always be more efficient but I don't know for sure.

[LightCode Gaming]

If a decision problem can be extended to an optimization problem, then the algorithm for the decision problem would be at least as efficient, if not more efficient than the algorithm of the optimization problem. It may even be guaranteed to always be more efficient but I don't know for sure.

Well shit... There goes my plan to break the P=NP barrier...

[Art Vandelay]

Isn't that just the travelling salesman problem?

[LightCode Gaming]

Isn't that just the travelling salesman problem?

No, as you do not have to end up back at the same start point.

[Art Vandelay]

No, as you do not have to end up back at the same start point.

Oh, then it's probably similar to Kruskal's algorithm.

[LightCode Gaming]

Oh, then it's probably similar to Kruskal's algorithm.

There goes me breaking the P=NP barrier then...