Mike Hewner's Homepage

With the help of the textbook associated with the graph library I was using, I was able to build some graphs that require exponential runtime. Actually, factorial runtime which is slow, as my laptop’s second processor can attest to at this moment. The key to defeating the algorithm was to come up with a graph that was Biconnected but had no Hamiltonian Cycle. Once I had that, it was easy enough to to attach it to arbitrary-size complete graphs. The algorithm always checks the edges in order, so having this “unhamiltonianable” appendage stuck onto the end forced it to try every permutation of the first n – 7 vertices.

This may not be the most elegant solution ever, but it is a bit gratifying to know I haven’t completely lost everything I learned in algorithms class.

An for those who are curious, here, is an honest-to-goodness graph of an exponential algorithm sucking for real. Not quite as smooth as I would like, but then again I don’t think I’ll be able to get n = 20 even if I let this thing run overnight.