Degree-constrained spanning tree
வரைபடக் கோட்பாட்டில், ஒரு டிகிரி-கட்டுப்படுத்தப்பட்ட ஸ்பானிங் ட்ரீ என்பது அதிகபட்ச உச்சநிலை டிகிரி ஒரு குறிப்பிட்ட மாறிலி k க்கு மட்டுப்படுத்தப்பட்ட ஒரு ஸ்பானிங் ட்ரீ ஆகும். டிகிரி-கட்டுப்படுத்தப்பட்ட ஸ்பானிங் ட்ரீ சிக்கல் என்பது ஒரு குறிப்பிட்ட வரைபடத்தில் ஒரு குறிப்பிட்ட k க்கு அத்தகைய ஸ்பானிங் ட்ரீ உள்ளதா என்பதைத் தீர்மானிப்பதாகும். முறையான வரையறை உள்ளீடுஃ n-முனை திசைதிருப்பப்படாத வரைபடம் G (V, E); நேர்மறை முழு எண் k <n. கேள்விஃ G க்கு ஒரு ஸ்பானிங் ட்ரீ உள்ளதா, அதில் எந்த முனையும் k ஐ விட டிகிரி அதிகமாக இல்லை? NP-முழுமை இந்த சிக்கல் NP-முழுமை. ஹாமில்டோனியன் பாதை சிக்கலில் இருந்து குறைப்பதன் மூலம் இதைக் காட்டலாம். k ஒரு மதிப்பு ≤2 ஆக நிர்ணயிக்கப்பட்டாலும் அது NP-முழுமையடைகிறது. டிகிரி ≤ k ஆக இருக்க வேண்டும் என்று சிக்கல் வரையறுக்கப்பட்டால், டிகிரி-கட்டுப்படுத்தப்பட்ட ஸ்பானிங் ட்ரீயின் k = 2 வழக்கு ஹாமில்டோனியன் பாதை சிக்கலாகும். டிகிரி-கட்டுப்படுத்தப்பட்ட குறைந்தபட்ச பரவலான மரம் ஒரு எடையுள்ள வரைபடத்தில், ஒரு டிகிரி-கட்டுப்படுத்தப்பட்ட குறைந்தபட்ச பரவலான மரம் (டி. சி. எம். எஸ். டி) என்பது ஒரு டிகிரி-கட்டுப்படுத்தப்பட்ட பரவலான மரம் ஆகும், இதில் அதன் விளிம்புகளின் கூட்டுத்தொகை குறைந்தபட்ச சாத்தியமான தொகையைக் கொண்டுள்ளது. ஒரு டிசிஎம்எஸ்டியைக் கண்டுபிடிப்பது ஒரு என். பி-ஹார்ட் சிக்கலாகும். மரபணு மற்றும் எறும்பு அடிப்படையிலான வழிமுறைகள் உட்பட பல்லுறுப்புக்கோவை நேரத்தில் சிக்கலைத் தீர்க்கக்கூடிய ஹூரிஸ்டிக் வழிமுறைகள் முன்மொழியப்பட்டுள்ளன. தோராயமான வழிமுறை ஒரு மறுசுழற்சி பல்லுறுப்புக்கோவை நேர வழிமுறையைக் கொடுக்கிறது, இது ஒரு வரைபடத்தைக் கொடுத்தால், அதிகபட்ச டிகிரி கொண்ட ஒரு பரவலான மரத்தை விட பெரியதாக இருக்காது, இது அனைத்து பரவலான மரங்களுக்கும் குறைந்தபட்ச அதிகபட்ச டிகிரி ஆகும். எனவே, அத்தகைய வழிமுறை அதிகபட்ச டிகிரி அல்லது ஒரு பரவலான மரத்தைத் திருப்பித் தரும். மரத்தில் பரவியிருக்கும் குறிப்புகள் NP-முழுமையான சிக்கல்கள்