دوست عزیز درباره NP-complete بودن این مسئله بیشتر به مورد پیدا کردن بیشترین فاصله بین دو راس گراف به طوری که تعداد یال مشاهده شده از یه مقداری که ورودی مسئله است بیشتر یا مساوی باشه صدق میکنه.به این لینک سری بزن
http://www.csc.liv.ac.uk/~ped/teacha...otated_np.html