انجمن کامپیوتر ایران

پیدا کردن دو مسیر ساده از دو مجموعه نقطه مجزا اولین بار توسط جف اریکسون مطرح شد. این مسئله می‌تواند در مسیریابی حرکت ربات‌ها، تولید چندضلعی‌های تصادفی، طراحی مدارهای VLSI و غیره کاربرد داشته باشد. در این مقاله اثبات می‌کنیم که حالت عمومی این مسئله یعنی رسم r زنجیره قرمز ساده و b زنجیره آبی ساده از دو مجموعه نقطه مجزای داده‌شده به‌طوری‌که تمام نقاط را پوشش دهند ان پی‌کامل است. برای اثبات ان پی-کامل بودن، از مسئله «پیدا کردن مسیر همیلتونی در گراف‌های مسطح که با یال‌های خط مستقیم رسم شده‌اند» که خود یک مسئله ان پی-کامل است استفاده می‌کنیم و آن را به مسئله مطرح‌شده کاهش می‌دهیم.