The Game of Hamiltonian Paths: Part 9 of Ann's Visit to G'Raph

A Hamiltonian path visits each node in a graph exactly one time. The problem of determining whether a graph has a Hamiltonian path is NP-Hard.

"Mister Mayor, I think that there is a wizard casting spells on the scholars of G'Raph," Ann repeated. "Everyone to whom the wizard has spoken became obsessed with finding a polynomial solution to a specific NP-hard problem. Have you heard any stories about a stranger in a dark cloak asking scholars NP-hard computational problems?"

The mayor looked confused. "NP-Hard? I am not exactly sure what that means, but I had a man in a dark cloak ask me a hard question once."

"You did?" asked Ann, Edgar, and Florence in unison. None of them could hide the shocked looks on their faces.

"Yes," answered the mayor. "It was about twenty years ago -- right after I left school. He had just come from the library. I think he stopped to talk to Geoffrey about some salesman problem. Geoffrey was my favorite teacher, you know. He would always have the easiest tests. Anyway, the man asked me if I could solve a game: Find a path through G'Raph such that I go through each island at most one time."

"The Hamiltonian Path problem," stated Ann. "It is also NP-hard."

"It is related Geoffrey's traveling salesman problem," added Florence.

"But why did the wizard ask you about Hamiltonian paths?" Ann asked, trying to phrase the question tactfully. From her limited time with the mayor, he had yet to strike her as one of G'Raph's great scholars.

The mayor shrugged. "I don't know, but it sounded like a fun game."

"It is a popular game in G'Raph," Edgar agreed. "We played Hamiltonian paths as kids. We would draw out different hopscotch graphs and have to traverse them in Hamiltonian paths. Of course you were not allowed to solve them ahead of time. You had to determine the Hamiltonian path as you were hopping. If you got stuck or stepped on the same node twice, you were out."

Ann looked skeptical. "You really played that as a kid? That was how you spent your childhood?" she asked.

Edgar smiled at the fond memory. "Those were good times,” he answered.

"What did you say to the wizard?" Ann asked the mayor. "You did not solve it, did you?"

The mayor smiled. "I sure did. I told the man in the cloak: 'That's easy. I would just build a few more bridges.' The man left shortly after that. I think he said something about my future as a politician."

"That is cheating," objected Edgar. "You cannot add bridges in a game of Hamiltonian paths!"

"Mister Mayor," interrupted Ann. "Do you know anyone else who met the wizard?"

The mayor thought for a moment. "Not here in G'Raph. But I had an intern that told me a story that sounded similar to what you are claiming. He had a good friend in the town of Bool who became obsessed with one of these hard problems. What did you call them? NT? ND?"

"NP," offered Ann.

"Sure. Sure. Anyway, my intern's friend had a fun little problem called 3-SAT or something like that. Sounded like the type of thing you would find in the Sunday paper."

"The town of Bool? Are you sure?" asked Ann.

The mayor nodded. "You always know a Boolean when you meet one," Ann could not agree more.

After a few more minutes of discussion, Ann decided that she was not going to find any more answers here. She knew that there was a wizard that was casting spells on computational scholars; now she had to figure out why.

For the first time in her quest, Ann knew where to go next. She needed to pay a visit to the one place where she might find more information about NP-hard problems -- the library of Alexandria.

Read Ann's visit to G'Raph from the beginning with Part 1: The City of G'Raph. Or read about Ann's first (and highly unpleasant) visit to the city of Bool.