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 اور G پراپرٹی Π کو مطمئن کرتا ہے؟ گراف کی ایک کلاس کے لیے شناخت کا مسئلہ (جو کسی پراپرٹی Π کو مطمئن کرتے ہیں) مخصوص گراف سینڈوچ کے مسئلے کے برابر ہے جہاں E1 = E2، یعنی اختیاری ایج سیٹ خالی ہے۔ کمپیوٹیشنل پیچیدگی گراف سینڈوچ کا مسئلہ این پی مکمل ہوتا ہے جب Π ایک کورڈل گراف، تقابلی گراف، پرموٹیشن گراف، کورڈل دو طرفہ گراف، یا چین گراف ہونے کی خاصیت ہوتی ہے۔ اسے تقسیم شدہ گرافوں، حد گرافوں اور گرافوں کے لیے کثیر الجہتی وقت میں حل کیا جا سکتا ہے جس میں ہر پانچ عمودی حصوں میں زیادہ سے زیادہ ایک چار ورٹیکس پر مبنی راستہ ہوتا ہے۔ پیچیدگی کی حیثیت کو چار ورٹیکس گرافوں میں سے ہر ایک کے لیے ایچ فری گراف سینڈوچ کے مسائل کے لیے بھی طے کیا گیا ہے۔ گراف تھیوری میں کمپیوٹیشنل مسائل