Maximum cut
گراف کے لیے، زیادہ سے زیادہ کٹ ایک کٹ ہے جس کا سائز کم از کم کسی دوسرے کٹ کے سائز کا ہوتا ہے۔ یعنی، یہ گراف کے عمودی حصوں کو دو تکمیلی سیٹوں میں تقسیم کرنا ہے اور، اس طرح کہ اور کے درمیان کناروں کی تعداد ہر ممکن حد تک بڑی ہو۔ اس طرح کا کٹ تلاش کرنا میکس کٹ مسئلہ کے نام سے جانا جاتا ہے۔ مسئلہ کو صرف اس طرح بیان کیا جا سکتا ہے: کوئی بھی ورٹیکس سیٹ کا ایک ذیلی سیٹ چاہتا ہے جیسے کہ اور تکمیلی ذیلی سیٹ کے درمیان کناروں کی تعداد زیادہ سے زیادہ ہو۔ اسی طرح، کوئی بھی گراف کا دو طرفہ ذیلی گراف چاہتا ہے جس میں زیادہ سے زیادہ کنارے ہوں۔ ویٹڈ میکس کٹ نامی مسئلے کا ایک اور عمومی ورژن ہے، جہاں ہر کنارے کا تعلق ایک حقیقی نمبر، اس کے وزن سے ہوتا ہے، اور اس کا مقصد کناروں کی تعداد کے بجائے کناروں کے درمیان اور اس کی تکمیل کے کل وزن کو زیادہ سے زیادہ کرنا ہے۔ مثبت اور منفی دونوں وزنوں کی اجازت دینے والے وزن والے زیادہ سے زیادہ کٹ کے مسئلے کو تمام وزنوں میں نشان کو پلٹ کر معمولی طور پر وزن والے کم سے کم کٹ کے مسئلے میں تبدیل کیا جا سکتا ہے۔ نچلی حدود ایڈورڈز نے نقاط اور کناروں کے ساتھ گراف پر میکس کٹ کے لیے درج ذیل دو نچلی حد حاصل کی ((a) من مانی ہے، لیکن (b) میں یہ جڑا ہوا ہے): (a) (b) باؤنڈ (b) کو اکثر ایڈورڈز-ایرڈس باؤنڈ کہا جاتا ہے جیسا کہ ایرڈس نے قیاس کیا تھا۔ ایڈورڈز نے ممکنہ طریقہ کار کا استعمال کرتے ہوئے ایڈورڈز-ایرڈس کے پابند ہونے کو ثابت کیا۔ کروسٹن اور دیگر۔ لکیری الجبرا اور فرضی بولین افعال کے تجزیے کا استعمال کرتے ہوئے باؤنڈ کو ثابت کیا۔ کروسٹن اور دیگر کا ثبوت۔ ہمیں ایڈورڈز-ایرڈس کو توسیع دینے کی اجازت دیتا ہے جو دستخط شدہ گرافوں پر بیلنسڈ سب گراف پروبلم (بی ایس پی) سے منسلک ہے، یعنی۔ گراف جہاں ہر کنارے کو + یا-تفویض کیا گیا ہے۔ ذیلی سیٹوں میں تقسیم کے لیے اور، ایک کنارے کو متوازن کیا جاتا ہے اگر یا تو اور اور ایک ہی ذیلی سیٹ میں ہوں، یا اور اور مختلف ذیلی سیٹ ہوں۔ بی ایس پی کا مقصد ایک ایسی تقسیم تلاش کرنا ہے جس میں زیادہ سے زیادہ متوازن کناروں کی تعداد ہو۔ ایڈورڈز-ایرڈس ہر منسلک دستخط شدہ گراف کے لیے نچلی حد دیتا ہے۔ گراف کی خصوصی کلاسوں کے لیے باؤنڈ (a) کو بہتر بنایا گیا: مثلث سے پاک گراف، دی گئی زیادہ سے زیادہ ڈگری کے گراف،-فری گراف وغیرہ، مثال کے طور پر دیکھیں۔ پولجاک اور ٹرزک نے ایڈورڈز-ایرڈوس کو بڑھا کر وزن والے میکس کٹ تک بڑھا دیا: کہاں اور کہاں ہیں اور اس کا کم از کم وزن درخت پر پھیلا ہوا ہے۔ حال ہی میں، گٹن اور ییو نے وزن والے گراف کی خصوصی کلاسوں کے لیے من مانی وزن والے گراف اور حدود کے لیے پولجک-ترزک کو بڑھانے والے وزن والے میکس کٹ کے لیے کئی نچلی حدود حاصل کیں۔ کمپیوٹیشنل پیچیدگی زیادہ سے زیادہ کٹوتیوں سے متعلق مندرجہ ذیل فیصلہ سازی کے مسئلے کا نظریاتی کمپیوٹر سائنس میں وسیع پیمانے پر مطالعہ کیا گیا ہے: گراف G اور انٹیجر k کو دیکھتے ہوئے، اس بات کا تعین کریں کہ آیا G میں کم از کم k سائز کا کٹوتی ہے۔ یہ مسئلہ NP مکمل ہونے کے لیے جانا جاتا ہے۔ یہ دیکھنا آسان ہے کہ مسئلہ این پی میں ہے: کافی بڑا کٹ پیش کرکے ہاں کا جواب ثابت کرنا آسان ہے۔ مسئلے کی این پی تکمیل کو دکھایا جا سکتا ہے، مثال کے طور پر، زیادہ سے زیادہ 2-اطمینان سے کمی (زیادہ سے زیادہ اطمینان بخش مسئلے کی پابندی) کے ذریعے۔ فیصلہ کے مسئلے کا وزن ورژن کارپ کے 21 این پی مکمل مسائل میں سے ایک تھا۔ کارپ نے تقسیم کے مسئلے سے کمی کے ذریعے این پی مکمل ہونے کو ظاہر کیا۔ مندرجہ بالا فیصلہ کے مسئلے کے کینونکل آپٹیمائزیشن ورژن کو عام طور پر زیادہ سے زیادہ کٹ مسئلہ یا زیادہ سے زیادہ کٹ کے نام سے جانا جاتا ہے اور اس کی تعریف اس طرح کی جاتی ہے: گراف G کو دیکھتے ہوئے، زیادہ سے زیادہ کٹ تلاش کریں۔ اصلاح کا متغیر این پی-ہارڈ کے طور پر جانا جاتا ہے۔ اس کے برعکس مسئلہ، کم از کم کٹ تلاش کرنے کا مسئلہ فورڈ-فلکرسن الگورتھم کے ذریعے مؤثر طریقے سے حل کرنے کے لیے جانا جاتا ہے۔ الگورتھم کثیر الجہتی وقت کے الگورتھم جیسا کہ زیادہ سے زیادہ کٹ کا مسئلہ این پی سخت ہے، عام گراف میں زیادہ سے زیادہ کٹ کے لیے کوئی کثیر الجہتی وقت کے الگورتھم معلوم نہیں ہیں۔ تاہم، پلانر گرافوں میں، زیادہ سے زیادہ کٹ کا مسئلہ روٹ انسپیکشن کے مسئلے سے دوگنا ہے (ایک مختصر ترین ٹور تلاش کرنے کا مسئلہ جو کم از کم ایک بار گراف کے ہر کنارے پر جاتا ہے)، اس معنی میں کہ وہ کنارے جو گراف G کے زیادہ سے زیادہ کٹ سیٹ سے تعلق نہیں رکھتے ہیں وہ کناروں کے ڈوئل ہیں جو G کے ڈوئل گراف کے زیادہ سے زیادہ انسپیکشن ٹور میں دوگنا ہوتے ہیں۔ زیادہ سے زیادہ انسپیکشن ٹور ایک سیلف انسیکٹنگ وکر بناتا ہے جو طیارہ کو دو ذیلی سیٹوں میں الگ کرتا ہے، پوائنٹس کا سب سیٹ جس کے لیے وکر کا وائنڈنگ نمبر یکساں ہوتا ہے اور وہ سب سیٹ جس کے لیے وائنڈنگ نمبر عجیب ہوتا ہے۔ یہ دونوں سب سیٹ ایک کٹ بناتے ہیں جس میں وہ تمام کنارے شامل ہوتے ہیں جن کے ڈوئل ظاہر ہوتے ہیں۔ روٹ انسپیکشن کا مسئلہ کثیر الجہتی وقت میں حل کیا جا سکتا ہے، اور یہ دوہری پن پلانر گراف کے لیے کثیر الجہتی وقت میں زیادہ سے زیادہ کٹ کے مسئلے کو بھی حل کرنے کی اجازت دیتا ہے۔ تاہم زیادہ سے زیادہ تقسیم کا مسئلہ این پی ہارڈ کے طور پر جانا جاتا ہے۔ زیادہ سے زیادہ کٹ کا مسئلہ اے پی ایکس سخت ہے، جس کا مطلب ہے کہ اس کے لیے کوئی کثیر الجہتی وقت کا تخمینہ اسکیم (پی ٹی اے ایس) نہیں ہے، جو من مانی طور پر زیادہ سے زیادہ حل کے قریب ہے، جب تک کہ پی = این پی نہ ہو۔ اس طرح، ہر معروف کثیر الجہتی وقت کا تخمینہ الگورتھم ایک تخمینہ تناسب حاصل کرتا ہے جو سختی سے ایک سے کم ہوتا ہے۔ ایک سادہ بے ترتیب 0.5-approximation الگورتھم ہے: ہر ورٹیکس کے لیے ایک سکے کو پلٹائیں تاکہ یہ فیصلہ کیا جا سکے کہ پارٹیشن کے کس نصف حصے کو اسے تفویض کرنا ہے۔ توقع میں، آدھے کنارے کٹے ہوئے ہیں۔ اس الگورتھم کو مشروط امکانات کے طریقہ کار سے الگ کیا جا سکتا ہے۔ اس لیے ایک سادہ تعیناتی کثیر الجہتی وقت 0.5-approximation الگورتھم بھی ہے۔ اس طرح کا ایک الگورتھم دیئے گئے گراف کے عمودی حصوں کی من مانی تقسیم سے شروع ہوتا ہے اور بار بار تقسیم کے ایک طرف سے ایک سرے کو دوسری طرف منتقل کرتا ہے، ہر مرحلے پر حل کو بہتر بناتا ہے، جب تک کہ اس قسم کی مزید بہتری نہ کی جا سکے۔ تکرار کی تعداد زیادہ سے زیادہ ہے کیونکہ الگورتھم ہر مرحلے پر کم از کم ایک کنارے سے کٹ کو بہتر بناتا ہے۔ جب الگورتھم ختم ہوتا ہے، تو ہر سرے پر واقع کناروں میں سے کم از کم نصف کا تعلق کٹ سے ہوتا ہے، کیونکہ بصورت دیگر سرے کو منتقل کرنے سے کٹ میں بہتری آئے گی۔ لہذا، کٹ میں کم از کم کنارے شامل ہوتے ہیں۔ سب سے مشہور تخمینہ تناسب کے ساتھ میکس کٹ کے لیے کثیر الجہتی وقت کا تخمینہ الگورتھم گومینس اور ولیمسن کا ایک ایسا طریقہ ہے جس میں سیمی فائنائٹ پروگرامنگ اور بے ترتیب راؤنڈنگ کا استعمال کیا جاتا ہے جو ایک تخمینہ تناسب حاصل کرتا ہے جہاں اگر منفرد گیم کا قیاس درست ہے، تو یہ زیادہ سے زیادہ کٹ کے لیے بہترین ممکنہ تخمینہ تناسب ہے۔ اس طرح کے غیر مصدقہ مفروضوں کے بغیر، یہ ثابت ہوا ہے کہ این پی سے بہتر تخمینہ تناسب کے ساتھ زیادہ سے زیادہ کٹ ویلیو کا تخمینہ لگانا مشکل ہے۔ اس میں اس مسئلے کے لیے 10 تحقیقات کا ایک توسیعی تجزیہ ہے، جس میں اوپن سورس نفاذ بھی شامل ہے۔ پیرامیٹرائزڈ الگورتھم اور کرنلائزیشن اگرچہ یہ ثابت کرنا معمولی بات ہے کہ کم از کم (پیرامیٹر) کے سائز کا کٹ تلاش کرنے کا مسئلہ فکسڈ پیرامیٹر ٹریکٹیبل (ایف پی ٹی) ہے، لیکن یہ فیصلہ کرنے کے مسئلے کے لیے فکسڈ پیرامیٹر ٹریکٹیبلٹی دکھانا بہت مشکل ہے کہ آیا گراف جی میں کم از کم ایڈورڈز-ایرڈس لوور باؤنڈ (اوپر لوور باؤنڈ دیکھیں) پلس (پیرامیٹر) کے سائز کا کٹ ہے یا نہیں۔ کروسٹن اور دیگر۔ ثابت کیا کہ مسئلہ وقت پر حل کیا جا سکتا ہے اور سائز کے دانے کو تسلیم کرتا ہے۔ کروسٹن اور دیگر۔ فکسڈ پیرامیٹر ٹریکٹیبلٹی کے نتیجے کو بیلنسڈ سب گراف پروبلم (بی ایس پی، اوپر نچلی حدود دیکھیں) تک بڑھایا اور دانے کے سائز کو بہتر بنایا (بی ایس پی کے لیے بھی ہے)۔ Etscheid اور Mnich نے بی ایس پی کے لیے فکسڈ پیرامیٹر ٹریکٹیبلٹی نتیجہ اور عمودی طور پر دانا سائز کے نتیجے کو بہتر بنایا۔ ایپلی کیشنز مشین لرننگ اس کے نوڈس کو خصوصیات اور اس کے کناروں کو فاصلے کے طور پر دیکھتے ہوئے، میکس کٹ الگورتھم ایک گراف کو دو اچھی طرح سے الگ الگ ذیلی سیٹوں میں تقسیم کرتا ہے۔ دوسرے لفظوں میں، اسے قدرتی طور پر بائنری درجہ بندی انجام دینے کے لیے لاگو کیا جا سکتا ہے۔ زیادہ عام درجہ بندی کے الگورتھم کے مقابلے میں، اس کے لیے فیچر اسپیس کی ضرورت نہیں ہے، صرف اندر موجود عناصر کے درمیان فاصلے۔ نظریاتی طبیعیات شماریاتی طبیعیات اور بے ترتیب نظاموں میں، میکس کٹ کا مسئلہ اسپن گلاس ماڈل کے ہیملٹنین کو کم کرنے کے مترادف ہے، جو کہ صرف آئزنگ ماڈل ہے۔ گراف G پر آئزنگ ماڈل کے لیے اور صرف قریب ترین پڑوسی تعاملات کے لیے، ہیملٹنین ہے۔ یہاں گراف کا ہر ورٹیکس i ایک اسپن سائٹ ہے جو ایک اسپن ویلیو لے سکتی ہے۔ ایک اسپن کنفیگریشن پارٹیشن کو دو سیٹوں میں تقسیم کیا جاتا ہے، جن میں اسپن اپ اور جن میں اسپن ڈاؤن ہوتا ہے۔ ہم ان کناروں کے سیٹ سے اشارہ کرتے ہیں جو دونوں سیٹوں کو جوڑتے ہیں۔ اس کے بعد ہم ہیملٹنین کو دوبارہ لکھ سکتے ہیں کیونکہ اس توانائی کو کم کرنا کم سے کم مسئلہ کے برابر ہے یا گراف کے وزن کو زیادہ سے زیادہ کٹ مسئلہ کے طور پر ترتیب دے کر۔ سرکٹ ڈیزائن زیادہ سے زیادہ کٹ کے مسئلے کی وی ایل ایس آئی ڈیزائن میں ایپلی کیشنز ہیں۔ یہ بھی دیکھیں کہ کم از کم کٹ کم از کم کے-کٹ آڈ سائیکل ٹرانسورسل، جو کہ سب سے بڑے دو طرفہ انڈیوسڈ سب گراف غیر دوستانہ پارٹیشن کے لیے پوچھنے کے مساوی ہے، جو لامحدود گراف نوٹ حوالہ جات کے لیے ایک متعلقہ تصور ہے۔ ۔ اپینڈکس بی (صفحہ 399) میں زیادہ سے زیادہ کٹ (اصلاح ورژن) این ڈی 14 کا مسئلہ ہے۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ زیادہ سے زیادہ کٹ (فیصلہ ورژن) ضمیمہ A2.2 میں مسئلہ ND16 ہے۔ زیادہ سے زیادہ دو طرفہ ذیلی گراف (فیصلہ ورژن) ضمیمہ A1.2 میں GT25 کا مسئلہ ہے۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ بیرونی روابط پیئرلوگی کریسینزی، ویگو کن، میگنس ہالڈورسن، مارک کارپنسکی، گیرہارڈ ووینجر (2000)، "میکسمم کٹ"، "این پی آپٹیمائزیشن کے مسائل کا مجموعہ" میں۔ اینڈریا کیسینی، نکولا ریباگلیاٹی (2012)، "میکس کٹ کو حل کرنے کے لیے ایک ازگر لائبریری" گراف تھیوری آبجیکٹ کمبینٹوریئل آپٹیمائزیشن این پی-مکمل گراف تھیوری میں کمپیوٹیشنل مسائل