Current Proceedings on Technology

Yazarlar: Eva Milková, Karel Petránek

Konular:-

Anahtar Kelimeler:Keywords Puzzle,Graph theory,Combinatorial combination,Path avoiding forbidden pairs

Özet: Algorithmic complexity is often viewed as a difficult part of IT education. This paper describes a puzzle “Pilgrimage” whose aim is to find a path avoiding forbidden pairs of vertices in a given graph with special properties. Finding a path that avoids forbidden pairs of vertices is known to be NP-complete in general and a few restricted versions of the problem are known to be in P. Contrary to the intuition that the puzzle “Pilgrimage” is solvable by a polynomial algorithm, we prove that even this special case is NP-complete and thus a fast algorithm is unlikely to exist. First, we show that the problem lies in NP and second, we show a reduction from SAT, a well-known NP-complete problem. The puzzle serves as an excellent educational example. Its formulation is interesting and attractive for students and the NP-completeness proof is straighforward enough to further improve student motivation.

---