Mike Hewner's Homepage

This is a question any theory-oriented friends of mine should feel free to jump in on.

So I wanted to make some graphs for explaining Big O. And I wanted to include exponential functions on that graph. But unlike my previous examples of such things, I didn’t want to say “oh wow, look at this graph of 2^n….see how terrible it is” because I know that real exponential functions in practice are often much happier than 2^n. I wanted real run-time data, ideally using source code from some trustworthy seeming source (i.e. not me).

“So heck,” said I, “surely Mathematica has implementations of some of these famous NP-Complete problems. I’ll run some of those and I think that that’s at least plausibly trustworthy.” So I poked around and found some graph algorithms – specifically traveling salesman and Hamiltonian cycle.

Then came the difficulty of generating good problem examples. I initially thought I’d just use random graphs but the runtime varied so much it just wasn’t reasonable. Then I noticed that if I passed in complete graph to Hamiltonian Cycle with one completely disconnected vertex, the Hamiltonian Cycle algorithm would be pretty dang slow:

But was it really exponential? This is where I’m stuck. I don’t really understand the algorithm that’s generating these solutions – for all I know it might be detecting the disconnected vertex (albeit somewhat late) and might be evidencing merely some (bad) polynomial time.

HamiltonianCycle[g_Graph,flag_:One] :=
        Module[{s={1},all={},done,adj=Edges[g],
                e=ToAdjacencyLists[g],x,v,ind,n=V[g]},
                ind=Table[1,{n}];
                While[ Length[s] > 0,
                        v = Last[s];
                        done = False;
                        While[ ind[[v]] < = Length[e[[v]]] && !done,
                               x = e[[v,ind[[v]]++]];
                               done = !MemberQ[s, x] && 
                                       (Length[s] == 1 ||
                                        BiconnectedQ[DeleteVertices[AddEdges[g, {{1, x}}], Rest[s]]])
                        ];
                        If[done, AppendTo[s,x], s=Drop[s,-1]; ind[[v]] = 1];
                        If[(Length[s] == n),
                                If [MemberQ[adj, Sort[{x, 1}]],
                                    AppendTo[all,Append[s,First[s]]];
                                    If [SameQ[flag,All],
                                        s=Drop[s,-1],
                                        all = Flatten[all]; s={}
                                    ],
                                    s = Drop[s,-1]
                                ]
                        ]
                ];
                all
        ]

Does that look familiar to anyone? Any guesses to Big-O for this kind of input?

OR – say you wanted to provide an example of real running exponential function. What would you use instead of my Hamiltonian Cycle hack?