مسئله طولانیترین مسیر، مسئله یافتن مسیری ساده با بیشترین تعداد رأس بین دو رأس معین در گراف است. این مسئله یکی از مسائل انپی سخت مشهور در نظریه گراف است. مسئلهای در ردۀ پی است اگر در مان چند جملهای قابل حل باشد. مسئلهای در ردۀ انپی است که در زمان چند جملهای قابل راستی آزمایی باشد، یعنی با داشتن یک جواب بالقوه بتوان در زمان چندجملهای راستی آزمایی کنیم که این جواب واقعا یک جواب درست برای مسئله است یا خیر. مسئله انپی سخت مسئلهای است که همه مسائل انپی را بتوان در زمان چند جملهای به آن کاهش داد. مسئله A به مسئله B کاهش مییابد اگر بتوان هر نمونه از مسئله A را به یک نمونه از مسئله B تبدیل کرد و از روی جواب مسئله B بتوان جواب مسئله A را به دست آورد. مسئله مسیر همیلتونی، یعنی تصمیمگیری در مورد اینکه آیا مسیری ساده بین دو رأس معین در گراف وجود دارد که هر رأس دقیقاً یک بار ملاقات شود، حالت خاصی از مسئله طولانیترین مسیر است. این مسئله کاربردهای زیادی در طراحی تراشههای VLSI، تجسم اطلاعات، روباتیک و غیره دارد ]1[ و تنها برای ردههای خاصی از گراف الگوریتم زمان چندجملهای ارائه شده است ]2[ و هنوز برای برخی از انواع ردههای گراف این مسئله باز است ]3[. گراف توری اولین بار در سال 1978 توسط لوسیو و موگنیا معرفی شد ]4[. ایتای و همکارانش ]5[ ثابت کردند که مسئله مسیر همیلتونی برای گرافهای توری عمومی انپی کامل است، آنها همچنین مسئله مسیر همیلتونی بین دو رأس معین در گرافهای توری مستطیلی را حل کردند. چن و همکارانش ]6[ الگوریتمی موازی برای ساختن مسیر همیلتونی در گراف توری مستطیلی ارائه کردند. چانگ و همکارانش ]7[ مسئله طولانیترین مسیر بین دو رأس معین که دقیقا یک رأس از گراف توری مستطیلی حذف شده باشد را حل کردند. هیدارا و همکارانش ]8[ مسئله طولانیترین مسیر بین دو رأس معین که دقیقا دو رأس از گراف توری مستطیلی حذف شده باشد را حل کردند
