Graph sandwich problem
வரைபடக் கோட்பாடு மற்றும் கணினி அறிவியலில், வரைபட சாண்ட்விச் சிக்கல் என்பது ஒரு குறிப்பிட்ட வரைபடக் குடும்பத்தைச் சேர்ந்த ஒரு வரைபடத்தைக் கண்டுபிடிப்பதில் உள்ள ஒரு சிக்கலாகும், மேலும் இரண்டு வரைபடங்களுக்கு இடையில் "சாண்ட்விச்" செய்யப்படுகிறது, அவற்றில் ஒன்று துணை வரைபடமாகவும் மற்றொன்று விரும்பிய வரைபடத்தின் சூப்பர் கிராஃபாகவும் இருக்க வேண்டும். வரைபட சாண்ட்விச் சிக்கல்கள் கொடுக்கப்பட்ட வரைபடம் வரைபடங்களின் குடும்பத்தைச் சேர்ந்ததா என்பதைச் சோதிக்கும் சிக்கலை பொதுமைப்படுத்துகின்றன, மேலும் அவற்றின் பயன்பாடுகள் மற்றும் அங்கீகார சிக்கல்களின் இயற்கையான பொதுமைப்படுத்தல் காரணமாக கவனத்தை ஈர்த்துள்ளன. சிக்கல் அறிக்கை மேலும் துல்லியமாக, ஒரு உச்சி தொகுப்பு V, ஒரு கட்டாய விளிம்பு தொகுப்பு E1, மற்றும் ஒரு பெரிய விளிம்பு தொகுப்பு E2 கொடுக்கப்பட்டால், ஒரு வரைபடம் G = (V, E) ஜோடிக்கு சாண்ட்விச் வரைபடம் என்று அழைக்கப்படுகிறது G1 = (V, E1), G2 = (V, E2) என்றால் E1 = E2. பண்பு Π க்கான கிராஃப் சாண்ட்விச் சிக்கல் பின்வருமாறு வரையறுக்கப்படுகிறதுஃ பண்பு Π க்கான கிராஃப் சாண்ட்விச் சிக்கல்ஃ எடுத்துக்காட்டுஃ வெர்டெக்ஸ் செட் V மற்றும் எட்ஜ் செட் E1-E2-V × V. கேள்விஃ ஒரு கிராஃப் G = (V, E) உள்ளதா, அதாவது E1-E2-E2 மற்றும் G பண்பு Π ஐ திருப்திப்படுத்துகிறதா? ஒரு வகை வரைபடங்களுக்கான அங்கீகார சிக்கல் (ஒரு பண்பு Π ஐ திருப்திப்படுத்துபவை) குறிப்பிட்ட வரைபட சாண்ட்விச் சிக்கலுக்கு சமம், அங்கு E1 = E2, அதாவது விருப்ப விளிம்பு தொகுப்பு காலியாக உள்ளது. கணக்கீட்டு சிக்கலானது கிராஃப் சாண்ட்விச் சிக்கல் NP-முழுமையானது, Π என்பது ஒரு கார்டல் கிராஃப், ஒப்பீட்டு கிராஃப், வரிசைமாற்ற கிராஃப், கார்டல் இருதரப்பு கிராஃப் அல்லது சங்கிலி கிராஃப் ஆகியவற்றின் பண்பு ஆகும். பிளவு வரைபடங்கள், வாசல் வரைபடங்கள் மற்றும் வரைபடங்களுக்கான பல்லுறுப்புக்கோவை நேரத்தில் இதைத் தீர்க்க முடியும், இதில் ஒவ்வொரு ஐந்து செங்குத்துகளும் அதிகபட்சம் ஒரு நான்கு-வெர்டெக்ஸ் தூண்டப்பட்ட பாதையைக் கொண்டுள்ளன. நான்கு-வெர்டெக்ஸ் வரைபடங்களில் ஒவ்வொன்றிற்கும் எச்-இலவச வரைபட சாண்ட்விச் சிக்கல்களுக்கான சிக்கலான நிலையும் தீர்க்கப்பட்டுள்ளது. எச். குறிப்புகள் மேலும் வாசிப்பு. வரைபடக் கோட்பாட்டில் கணக்கீட்டு சிக்கல்கள்