Graph sandwich problem
গ্রাফ তত্ত্ব এবং কম্পিউটার বিজ্ঞানে, গ্রাফ স্যান্ডউইচ সমস্যা হল এমন একটি গ্রাফ খুঁজে বের করার সমস্যা যা গ্রাফের একটি নির্দিষ্ট পরিবারের অন্তর্গত এবং অন্য দুটি গ্রাফের মধ্যে "স্যান্ডউইচড", যার মধ্যে একটি অবশ্যই একটি সাবগ্রাফ হতে হবে এবং অন্যটি অবশ্যই পছন্দসই গ্রাফের একটি সুপারগ্রাফ হতে হবে। গ্রাফ স্যান্ডউইচ সমস্যাগুলি প্রদত্ত গ্রাফটি গ্রাফের একটি পরিবারের অন্তর্গত কিনা তা পরীক্ষা করার সমস্যাটিকে সাধারণীকরণ করে এবং তাদের প্রয়োগের কারণে এবং স্বীকৃতি সমস্যার প্রাকৃতিক সাধারণীকরণ হিসাবে মনোযোগ আকর্ষণ করেছে। সমস্যা বিবৃতি আরও সুনির্দিষ্টভাবে, একটি ভার্টেক্স সেট V, একটি বাধ্যতামূলক প্রান্ত সেট E1, এবং একটি বৃহত্তর প্রান্ত সেট E2 দেওয়া হলে, G1 = (V, E1), G2 = (V, E2) জুটির জন্য একটি গ্রাফ G = (V, E) কে স্যান্ডউইচ গ্রাফ বলা হয় যদি E1 = E2 হয়। সম্পত্তি Π-এর জন্য গ্রাফ স্যান্ডউইচ সমস্যাটি নিম্নরূপ সংজ্ঞায়িত করা হয়েছেঃ সম্পত্তির জন্য গ্রাফ স্যান্ডউইচ সমস্যা Π: দৃষ্টান্তঃ ভার্টেক্স সেট V এবং প্রান্ত সেট E1-E2-V × V। প্রশ্নঃ এমন কোনও গ্রাফ G = (V, E) আছে কি যাতে E1-E2-E2 এবং G সম্পত্তি Π-কে সন্তুষ্ট করে? গ্রাফের একটি শ্রেণীর জন্য স্বীকৃতি সমস্যা (যারা একটি বৈশিষ্ট্য Π সন্তুষ্ট করে) নির্দিষ্ট গ্রাফ স্যান্ডউইচ সমস্যার সমতুল্য যেখানে E1 = E2, অর্থাৎ, ঐচ্ছিক প্রান্ত সেট খালি। গণনামূলক জটিলতা গ্রাফ স্যান্ডউইচ সমস্যাটি এনপি-সম্পূর্ণ হয় যখন Π একটি কর্ডাল গ্রাফ, তুলনামূলক গ্রাফ, বিন্যাস গ্রাফ, কর্ডাল দ্বিদলীয় গ্রাফ বা চেইন গ্রাফ হওয়ার বৈশিষ্ট্য। এটি বিভক্ত গ্রাফ, প্রান্তিক গ্রাফ এবং গ্রাফের জন্য বহুপদী সময়ে সমাধান করা যেতে পারে যেখানে প্রতি পাঁচটি শীর্ষে সর্বাধিক একটি চার-ভার্টেক্স প্ররোচিত পথ থাকে। চার-ভার্টেক্স গ্রাফ এইচ-এর প্রত্যেকটির জন্য এইচ-মুক্ত গ্রাফ স্যান্ডউইচ সমস্যার জন্য জটিলতার অবস্থাও নিষ্পত্তি করা হয়েছে। গ্রাফ তত্ত্বে গণনামূলক সমস্যা