Hamiltonian completion
હેમિલ્ટોનિયન પૂર્ણતાની સમસ્યા એ છે કે તેને હેમિલ્ટોનિયન બનાવવા માટે ગ્રાફમાં ઉમેરવા માટે કિનારીઓની ન્યૂનતમ સંખ્યા શોધવી. સામાન્ય કિસ્સામાં સમસ્યા સ્પષ્ટ રીતે એન. પી.-સખત હોય છે (કારણ કે તેનો ઉકેલ આપેલ આલેખમાં હેમિલ્ટોનિયન ચક્ર છે કે કેમ તે નક્કી કરવાની એન. પી.-પૂર્ણ સમસ્યાનો જવાબ આપે છે). હેમિલ્ટોનિયન આલેખ બનાવવા માટે આપેલ આલેખમાં K ધાર ઉમેરી શકાય છે કે કેમ તે નક્કી કરવાની સંકળાયેલ નિર્ણય સમસ્યા NP-પૂર્ણ છે. વધુમાં, હેમિલ્ટોનિયન કમ્પ્લીશન એ. પી. એક્સ. કોમ્પ્લેક્સિટી ક્લાસ સાથે સંબંધિત છે, એટલે કે, આ સમસ્યા માટે કાર્યક્ષમ સ્થિર ગુણોત્તર અંદાજિત અલ્ગોરિધમ્સ અસ્તિત્વમાં હોવાની શક્યતા નથી. શ્રેણી-સમાંતર આલેખ અને તેમના સામાન્યીકરણ સહિત આલેખના ચોક્કસ વર્ગો માટે બહુપદી સમયમાં સમસ્યાનું સમાધાન થઈ શકે છે, જેમાં બાહ્ય સમતલ આલેખ, તેમજ વૃક્ષના રેખા આલેખ અથવા કેક્ટસ આલેખનો સમાવેશ થાય છે. ગેમર્નિક એટ અલ. વૃક્ષો પરની સમસ્યાને ઉકેલવા માટે રેખીય સમય અલ્ગોરિધમનો ઉપયોગ કરો જેથી અસિંપ્ટોટિક સંખ્યાબંધ ધારોનો અભ્યાસ કરી શકાય જે તેમને હેમિલ્ટોનિયન બનાવવા માટે વિરલ રેન્ડમ આલેખ માટે ઉમેરવી આવશ્યક છે. સંદર્ભો એન. પી.-સંપૂર્ણ સમસ્યાઓ હેમિલ્ટોનિયન માર્ગો અને ચક્ર