Venice Bridge challenge

[Anny_Middon]

I thought this was going to be a discussion of the advantages of opening a 17-point balanced hand One Club (as in the Italian Blue System) instead of One No Trump (Standard American).

Leading to a bad joke: Why will The Donald never be a Life Myster? Because he refuses to bid No Trump.

[ftg]

@Chronos

But I like this complicated decision space!

And the reason I suspect that the Y-bridge problem is NP-complete is because it looks an awful lot like the Boolean satisfiability problem. It’s not exactly the same, since the bridges have three states, not just two, and I’m not sure that the islands can give us the equivalent of all of the Boolean operations, but it’s at least enough to hang a suspicion on.

With Y-bridges, it’s effectively the cubic Hamitonian Path Problem (the islands themselves are minor annoyances). The current best algorithm for that is O(1.251[sup]n[/sup]). While still exponential, the base is small enough to suggest it is barely exponential at most. This implies it’s likely not NP-Complete.

Oh, you do allow 3-d layouts, right? Bridges crossing over other bridges? Once you go planar, things usually get even easier.

[Peter_Morris]

@bob_2

That’s the theory - there are over 400 bridges in Venice, so the next challenge would be to find the shortest possible route.

@beowulff

Better have a fast computer.

Beowulf links to the Travelling Salesman problem. This is incorrect. It should be the Chinese Postman Problem.

They are both shortest route problems. The difference is this: In the TSP the object is to visit every island at least once. It doesn’t matter if there are some bridges you never visit. In the CPP, the object is to cross every bridge at least once.

There *are *algorithms to solve the CPP in a reasonable amount of time. There are none for the TSP.

[septimus]

@ftg

With Y-bridges, it’s effectively the cubic Hamitonian Path Problem (the islands themselves are minor annoyances). The current best algorithm for that is O(1.251[sup]n[/sup]). While still exponential, the base is small enough to suggest it is barely exponential at most. This implies it’s likely not NP-Complete.

The link you gave seems to state that some small-base problems are NP-complete (“remain NP-complete even for undirected planar graphs of maximum degree three”). Do I misunderstand?

Hamilton cycles have been suggested for use in zero-knowledge proofs. Are they ever used for this in practical applications?

[Chronos]

If you cross every (two-endpoint) bridge exactly once, then wouldn’t every path have the same length, the sum of the lengths of the bridges? Or are we including the distance traveled on the islands, from one bridge to the next?

Quoth ftg:

With Y-bridges, it’s effectively the cubic Hamitonian Path Problem (the islands themselves are minor annoyances).

I’m not sure how you’re dealing with that minor annoyance: If you treat the islands as also being vertices, then you no longer have a Hamilton path problem, since the islands need not be visited exactly once. I thought for a moment that you could treat each island as a complete graph connecting its bridges, but in that case, you’d be missing some of those vertices. If each island has exactly two bridges to it, then you could call the islands edges and be done with it, but an island could have any number of bridges.