Hamiltonian completion
হ্যামিল্টনিয়ান সমাপ্তির সমস্যাটি হ 'ল একটি গ্রাফে যোগ করার জন্য ন্যূনতম সংখ্যক প্রান্ত খুঁজে বের করা যাতে এটি হ্যামিল্টনিয়ান হয়। সাধারণ ক্ষেত্রে সমস্যাটি স্পষ্টভাবে এন. পি-হার্ড (যেহেতু এর সমাধান একটি প্রদত্ত গ্রাফের হ্যামিল্টনিয়ান চক্র আছে কিনা তা নির্ধারণের এন. পি-সম্পূর্ণ সমস্যার উত্তর দেয়)। হ্যামিল্টনিয়ান গ্রাফ তৈরি করার জন্য প্রদত্ত গ্রাফে কে প্রান্তগুলি যুক্ত করা যেতে পারে কিনা তা নির্ধারণের সম্পর্কিত সিদ্ধান্ত সমস্যাটি এনপি-সম্পূর্ণ। উপরন্তু, হ্যামিল্টনিয়ান সমাপ্তি এপিএক্স জটিলতা শ্রেণীর অন্তর্গত, অর্থাৎ, এই সমস্যার জন্য দক্ষ ধ্রুবক অনুপাত আনুমানিক অ্যালগরিদম বিদ্যমান থাকার সম্ভাবনা কম। সিরিজ-সমান্তরাল গ্রাফ এবং তাদের সাধারণীকরণ সহ নির্দিষ্ট শ্রেণীর গ্রাফের জন্য বহুপদী সময়ে সমস্যাটি সমাধান করা যেতে পারে, যার মধ্যে বাইরের সমতলীয় গ্রাফের পাশাপাশি একটি গাছের লাইন গ্রাফ বা ক্যাকটাস গ্রাফ অন্তর্ভুক্ত রয়েছে। গামার্নিক এবং অন্যান্য। গাছের সমস্যা সমাধানের জন্য একটি রৈখিক সময় অ্যালগরিদম ব্যবহার করুন যাতে অ্যাসিম্পটোটিক প্রান্তের সংখ্যা অধ্যয়ন করা যায় যা বিরল র্যান্ডম গ্রাফের জন্য হ্যামিল্টনিয়ান করার জন্য যোগ করা আবশ্যক। রেফারেন্স এনপি-সম্পূর্ণ সমস্যা হ্যামিল্টনিয়ান পথ এবং চক্র