Hamiltonian completion
ہیملٹنین تکمیل کا مسئلہ یہ ہے کہ اسے ہیملٹنین بنانے کے لیے گراف میں شامل کرنے کے لیے کم سے کم کناروں کی تعداد تلاش کی جائے۔ عام معاملے میں مسئلہ واضح طور پر این پی سخت ہے (کیونکہ اس کا حل این پی مکمل مسئلے کا جواب دیتا ہے کہ آیا دیئے گئے گراف میں ہیملٹنین سائیکل ہے)۔ اس بات کا تعین کرنے کا متعلقہ فیصلہ مسئلہ کہ آیا ہیملٹنین گراف تیار کرنے کے لیے دیئے گئے گراف میں کے کناروں کو شامل کیا جا سکتا ہے، این پی مکمل ہے۔ مزید برآں، ہیملٹنین تکمیل کا تعلق اے پی ایکس پیچیدگی کلاس سے ہے، یعنی اس بات کا امکان نہیں ہے کہ اس مسئلے کے لیے موثر مستقل تناسب تخمینہ الگورتھم موجود ہوں۔ اس مسئلے کو گراف کی بعض کلاسوں کے لیے کثیر الجہتی وقت میں حل کیا جا سکتا ہے، بشمول سیریز متوازی گراف اور ان کی عمومی کاری، جس میں بیرونی طیارہ گراف کے ساتھ ساتھ درخت کے لائن گراف یا کیکٹس گراف کے لیے بھی شامل ہیں۔ گامرنک اور دیگر۔ درختوں پر موجود مسئلے کو حل کرنے کے لیے لکیری ٹائم الگورتھم کا استعمال کریں تاکہ کناروں کی غیر علامتی تعداد کا مطالعہ کیا جا سکے جنہیں کم بے ترتیب گرافوں کے لیے شامل کیا جانا چاہیے تاکہ انہیں ہیملٹنین بنایا جا سکے۔ حوالہ جات NP-مکمل مسائل ہیملٹنین راستے اور سائیکل