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.

The Traveling Salesman's Problem: Part 6 of Ann's Visit to G'Raph

The traveling salesman problem is a route planning problem. The goal is to find the shortest path through a graph that visits each node exactly one time and returns to the starting node. The problem is also a classic example of a class of computational difficult problems, called NP-hard. There are no known efficient solutions (polynomial time) for solving NP-hard problems, and it has yet to be determined whether or not such a solution even exists.

Ann looked at the depressed scholar in the corner. "You have been working on the same problem for twenty-five years?" she asked.

"I am so close," he answered.

Behind her, Florence and Edgar had stopped arguing. They peeked their heads around the stack of books.

"Oh. I see you met Geoffrey," said Edgar. "Never mind him."

"I want to hear more about this problem," stated Ann. "What do you mean by shortest path?"

Geoffrey did not answer. He was hunched over his paper and mumbling to himself.

Ann turned back to Edgar and Florence. "You just told me about a shortest path algorithm,” she said.

"This is different," explained Florence. "The traveling salesman problem is a particularly difficult path planning problem. The goal is to find the shortest path through a graph that visits each node exactly once and returns to the starting node."

"Here are two example paths through G'Raph's school neighborhood," offered Edgar, drawing a crude sketch on a nearby blackboard.

Path 1

Path 2

"Both paths cross each node exactly once. Path 1 has a distance of 55 meters, and path 2 has a distance of 66 meters," he explained.

"That seems simple enough," commented Ann. "There is really no algorithm to solve it? Why not try all possible orderings of nodes? For each ordering, you could compute the total distance traveled if you visited the nodes in that order."

"There is no known efficient algorithm to solve it," explained Edgar. "No polynomial solution at least. The method you suggested would work, but it is factorial. You have to look at N! different orderings. For the 5 nodes in our simple example, there are 5! = 120 different permutations."

"Polynomial solution?" asked Ann.

"An algorithm where the running time scales polynomially with the size of the problem -- O(N^k) for some fixed value of k. For example linear algorithms O(N), quadratic algorithms O(N^2), and cubic algorithms O(N^3) are all polynomial. But the algorithm you suggested is O(N!); it scales as the factorial of N." Edgar explained.

Florence shrugged. "No one actually knows if there is an efficient solution or not. At least no one has found an efficient solution yet. There are good approximations and reasonable heuristics, of course, but no polynomial time algorithm."

"I played with it for a while," offered Edgar. "I never made much progress."

"Geoffrey has been working on it for twenty-five years?" asked Ann.

Both scholars nodded. "Ever since he met that man, Geoffrey has been unnaturally obsessed with this problem. He does not think about anything else. In the past, he would work on 3 or 4 different problems at the same time. It is as though he is under some sort of spell." Edgar explained.

Edgar's words sent a shiver through Ann. A vague memory floated through the back of her mind, but she was unable to latch onto it.

"Has anyone else met that man?" Ann asked.

Edgar shrugged. "I do not think so. Geoffrey said that he was probably a visiting salesman."

"He was selling questions," Geoffrey said quietly. Ann jumped at the sudden statement. Even though she had spoken to him only a minute ago, she had forgotten he was there.

"What did he look like?" asked Ann. The undefined memory continued nag at the back of her mind. She was miss a connection.

"Dark cloak and a large wooden staff that was covered with mathematical symbols," answered Geoffrey. "Never did see his face though."

"You only saw him that on time? Twenty-five years ago?" she confirmed. Why should an event from twenty-five years ago strike any memories with her?

"Three times," answered Geoffrey. "The first time was twenty-five years ago. Then, I saw him again ten years later. I was about to give up on the problem, but he found me and asked if I had solved it. That question rekindled the fire. I knew I could find a solution."

"And the third time?" asked Ann. She could feel a pit of fear building inside her, but she was not sure why.

"This morning," mumbled Geoffrey. "As I walked by the school, I saw him talking to some girl. He stopped for a moment and waved with his staff. I still have not found a solution yet, so I kept walking. I know I can find one. I am so close."

Ann did not wait for the rest of the story, she ran out the door and toward the school.

To be continued in Part 7: Panicked Depth First Search…

Follow Ann's Visit to G'Raph from the beginning with Part 1: The City of G'Raph.