Graph sandwich problem
આલેખ સિદ્ધાંત અને કોમ્પ્યુટર વિજ્ઞાનમાં, આલેખ સેન્ડવિચ સમસ્યા એ આલેખ શોધવાની સમસ્યા છે જે આલેખના ચોક્કસ પરિવાર સાથે સંબંધિત છે અને અન્ય બે આલેખ વચ્ચે "સેન્ડવિચ" થયેલ છે, જેમાંથી એક સબગ્રાફ હોવો જોઈએ અને બીજો ઇચ્છિત ગ્રાફનો સુપરગ્રાફ હોવો જોઈએ. ગ્રાફ સેન્ડવિચ સમસ્યાઓ પરીક્ષણની સમસ્યાને સામાન્ય બનાવે છે કે શું આપેલ ગ્રાફ ગ્રાફના પરિવાર સાથે સંબંધિત છે કે કેમ, અને તેમના ઉપયોગોને કારણે અને માન્યતા સમસ્યાઓના કુદરતી સામાન્યીકરણ તરીકે ધ્યાન આકર્ષિત કર્યું છે. સમસ્યાનું નિવેદન વધુ ચોક્કસપણે, શિરોબિંદુ સમૂહ V, ફરજિયાત ધાર સમૂહ E1, અને મોટા ધાર સમૂહ E2ને જોતાં, G = (V, E) ગ્રાફને જોડી G1 = (V, E1), G2 = (V, E2) માટે સેન્ડવિચ ગ્રાફ કહેવામાં આવે છે. ગુણધર્મ Π માટે આલેખ સેન્ડવિચ સમસ્યાને નીચે પ્રમાણે વ્યાખ્યાયિત કરવામાં આવી છેઃ ગુણધર્મ માટે આલેખ સેન્ડવિચ સમસ્યા Π: ઉદાહરણ તરીકેઃ વર્ટેક્સ સમૂહ V અને ધાર સમૂહ E1-E2-V × V. પ્રશ્નઃ શું કોઈ આલેખ G = (V, E) એવો છે કે જેથી E1-E2-E2 અને G ગુણધર્મને સંતોષે? આલેખના વર્ગ માટે ઓળખની સમસ્યા (જે ગુણધર્મ Π ને સંતોષ આપે છે) ચોક્કસ આલેખ સેન્ડવિચ સમસ્યાની સમકક્ષ છે જ્યાં E1 = E2, એટલે કે વૈકલ્પિક ધાર સમૂહ ખાલી છે. કોમ્પ્યુટેશનલ જટિલતા ગ્રાફ સેન્ડવિચ સમસ્યા એન. પી.-પૂર્ણ હોય છે જ્યારે Π એ કોર્ડલ ગ્રાફ, તુલનાત્મક ગ્રાફ, ક્રમચય ગ્રાફ, કોર્ડલ દ્વિપક્ષી ગ્રાફ અથવા સાંકળ ગ્રાફ હોવાનો ગુણધર્મ હોય છે. તેને વિભાજીત આલેખ, થ્રેશોલ્ડ આલેખ અને આલેખ માટે બહુપદી સમયમાં ઉકેલી શકાય છે જેમાં દરેક પાંચ શિરોબિંદુઓમાં વધુમાં વધુ એક ચાર-શિરોબિંદુ પ્રેરિત માર્ગ હોય છે. દરેક ફોર-વર્ટેક્સ આલેખ માટે એચ-ફ્રી ગ્રાફ સેન્ડવિચ સમસ્યાઓ માટે પણ જટિલતાની સ્થિતિનું સમાધાન કરવામાં આવ્યું છે. આલેખ સિદ્ધાંતમાં કોમ્પ્યુટેશનલ સમસ્યાઓ