Twin-width
غیر ہدایت شدہ گراف کی جڑواں چوڑائی گراف سے وابستہ ایک قدرتی نمبر ہے، جو گراف الگورتھم کی پیرامیٹرائزڈ پیچیدگی کا مطالعہ کرنے کے لیے استعمال ہوتا ہے۔ بدیہی طور پر، یہ پیمائش کرتا ہے کہ گراف ایک کوگراف سے کتنا ملتا جلتا ہے، ایک قسم کا گراف جسے ایک ہی پڑوسیوں والے جڑواں بچوں، عمودی حصوں کو بار بار ضم کرکے ایک ہی سرے تک کم کیا جا سکتا ہے۔ جڑواں چوڑائی کی تعریف بار بار انضمام کے سلسلے سے کی جاتی ہے جہاں عمودی جڑواں ہونے کی ضرورت نہیں ہوتی ہے، لیکن پڑوسیوں کے تقریبا برابر سیٹ ہوتے ہیں۔ تعریف جڑواں چوڑائی کی تعریف محدود سادہ غیر ہدایت شدہ گراف کے لیے کی گئی ہے۔ ان میں عمودی کا ایک محدود مجموعہ ہوتا ہے، اور کناروں کا ایک مجموعہ ہوتا ہے جو عمودی کے غیر ترتیب شدہ جوڑے ہوتے ہیں۔ کسی بھی ورٹیکس کا کھلا پڑوس دوسرے عمودی حصوں کا مجموعہ ہے جس کے ساتھ اسے گراف کے کناروں میں جوڑا جاتا ہے۔ بند پڑوس کھلے پڑوس سے خود ورٹیکس کو شامل کرکے تشکیل پاتا ہے۔ دو عمودی حقیقی جڑواں ہوتے ہیں جب ان کا ایک ہی بند پڑوس ہوتا ہے، اور جھوٹے جڑواں ہوتے ہیں جب ان کا ایک ہی کھلا پڑوس ہوتا ہے۔ زیادہ عام طور پر، حقیقی جڑواں اور جھوٹے جڑواں دونوں کو بغیر اہلیت کے جڑواں کہا جا سکتا ہے۔ گراف کی بہت سی مساوی تعریفیں ہیں، لیکن ان میں سے ایک یہ ہے کہ یہ وہ گراف ہیں جنہیں بار بار کسی بھی دو جڑواں عمودی کو تلاش کرنے اور انہیں ایک واحد عمودی میں ضم کرنے کے عمل کے ذریعے ایک واحد عمودی تک کم کیا جا سکتا ہے۔ کوگراف کے لیے، یہ تخفیف کا عمل ہمیشہ کامیاب رہے گا، اس بات سے کوئی فرق نہیں پڑتا کہ جڑواں بچوں کو ضم کرنے کا انتخاب ہر مرحلے پر کیا جاتا ہے۔ ایک ایسے گراف کے لیے جو کوگراف نہیں ہے، یہ ہمیشہ ایک ذیلی گراف میں پھنس جائے گا جس میں دو سے زیادہ عمودی ہیں جن میں کوئی جڑواں نہیں ہے۔ جڑواں چوڑائی کی تعریف اس کمی کے عمل کی نقل کرتی ہے۔ سکڑنے کی ترتیب، اس تناظر میں، مراحل کا ایک سلسلہ ہے، جس کا آغاز دیئے گئے گراف سے ہوتا ہے، جس میں ہر قدم عمودی جوڑے کی جگہ ایک واحد سرے سے لے لیتا ہے۔ یہ سرخ اور سیاہ رنگ کے کناروں کے ساتھ گراف کی ایک ترتیب پیدا کرتا ہے ؛ دیئے گئے گراف میں، تمام کناروں کو سیاہ سمجھا جاتا ہے۔ جب دو عمودی حصوں کو ایک واحد عمودی حصے سے تبدیل کیا جاتا ہے، تو نئے عمودی حصے کا پڑوس تبدیل شدہ عمودی حصوں کے پڑوسیوں کا اتحاد ہوتا ہے۔ اس نئے محلے میں، دونوں چوٹیوں کے محلوں میں سیاہ کناروں سے آنے والا ایک کنارہ سیاہ رہتا ہے ؛ دیگر تمام کناروں کا رنگ سرخ ہوتا ہے۔ سنکچن سیکوینس کو-سیکوینس کہا جاتا ہے اگر، پورے سیکوینس میں، ہر ورٹیکس زیادہ سے زیادہ سرخ کناروں کو چھوتا ہے۔ گراف کی جڑواں چوڑائی سب سے چھوٹی قدر ہے جس کے لیے اس کی ترتیب ہوتی ہے۔ ایک گھنے گراف میں اب بھی جڑواں چوڑائی ہو سکتی ہے ؛ مثال کے طور پر، گراف میں تمام مکمل گراف شامل ہوتے ہیں۔ جڑواں چوڑائی، غیر معمولی جڑواں چوڑائی کی تبدیلی، انفرادی گرافوں کے بجائے گراف کے خاندانوں پر لاگو ہوتی ہے۔ گرافوں کے ایک ایسے خاندان کے لیے جو محرک ذیلی گراف لینے کے تحت بند ہوتا ہے اور جڑواں چوڑائی سے جڑا ہوتا ہے، درج ذیل خصوصیات مساوی ہیں: خاندان میں گراف بہت کم ہوتے ہیں، جس کا مطلب ہے کہ ان کے پاس متعدد کنارے ہوتے ہیں جو ان کی عمودی تعداد کے لکیری فنکشن سے جڑے ہوتے ہیں۔ خاندان میں تمام مکمل دو طرفہ گراف شامل نہیں ہیں۔ دیئے گئے خاندان میں گراف کے تمام ذیلی گرافوں کے خاندان نے جڑواں چوڑائی کو پابند کیا ہے۔ خاندان نے توسیع کو محدود کر دیا ہے، جس کا مطلب ہے کہ اس کے تمام اتلی نابالغ کم ہیں۔ کہا جاتا ہے کہ اس طرح کے خاندان میں کم از کم جڑواں چوڑائی ہوتی ہے۔ جڑواں چوڑائی کے تصور کو گراف سے لے کر مختلف مکمل طور پر ترتیب شدہ ڈھانچوں تک عام کیا جا سکتا ہے (بشمول ان کے عمودی حصوں پر کل ترتیب سے لیس گراف)، اور غیر ترتیب شدہ گرافوں کے مقابلے میں ترتیب شدہ ڈھانچوں کے لیے بہت سے طریقوں سے آسان ہے۔ پابند ڈگری کے علاوہ مختلف ضروریات کے ساتھ سنکچن سیکوینس کا استعمال کرتے ہوئے گراف کی چوڑائی کے دیگر تصورات کے لیے مساوی تعریفیں وضع کرنا بھی ممکن ہے۔ باؤنڈڈ جڑواں چوڑائی والے گرافوں میں جڑواں چوڑائی صفر ہوتی ہے۔ گراف کے لیے تخفیف کے عمل میں، کوئی سرخ کنارے نہیں ہوں گے: جب دو عمودی مل جاتے ہیں، تو ان کے محلے برابر ہوتے ہیں، اس لیے دو محلوں میں سے صرف ایک سے آنے والے کنارے سرخ رنگ کے نہیں ہوتے ہیں۔ کسی بھی دوسرے گراف میں، کسی بھی سنکچن کی ترتیب سے کچھ سرخ کنارے پیدا ہوں گے، اور جڑواں چوڑائی صفر سے زیادہ ہوگی۔ زیادہ سے زیادہ تین چوٹیوں والے پاتھ گراف گراف ہوتے ہیں، لیکن ہر بڑے پاتھ گراف میں جڑواں چوڑائی ہوتا ہے۔ ایک سنکچن سیکوینس کے لیے جو بار بار راستے کے آخری دو کناروں کو ضم کرتا ہے، صرف واحد ضم شدہ ورٹیکس کے کنارے کا واقعہ سرخ ہوگا، لہذا یہ 1-سیکوینس ہے۔ درختوں کی زیادہ سے زیادہ دو چوڑائی ہوتی ہے، اور کچھ درختوں کے لیے یہ تنگ ہوتا ہے۔ کسی بھی درخت کے لیے 2-سکڑنے کا تسلسل جڑ کا انتخاب کرکے پایا جا سکتا ہے، اور پھر بار بار دو پتوں کو ضم کیا جا سکتا ہے جن کا ایک ہی مول ہے یا، اگر یہ ممکن نہیں ہے تو، سب سے گہرے پتے کو اس کے مول میں ضم کر دیا جا سکتا ہے۔ صرف سرخ کنارے پتوں کو ان کے والدین سے جوڑتے ہیں، اور جب ایک ہی والدین میں دو ہوتے ہیں تو انہیں ضم کیا جا سکتا ہے، سرخ ڈگری کو زیادہ سے زیادہ دو پر رکھتے ہوئے۔ زیادہ عام طور پر، گراف کی درج ذیل کلاسوں میں جڑی چوڑائی ہوتی ہے، اور ان کے لیے جڑی چوڑائی کا ایک سنکچن تسلسل کثیر الجہتی وقت میں پایا جا سکتا ہے: جڑی ہوئی کلیک چوڑائی، یا جڑی ہوئی رینک چوڑائی کے ہر گراف میں بھی جڑی چوڑائی ہوتی ہے۔ جڑواں چوڑائی کلک چوڑائی میں سب سے زیادہ متغیر ہے، اور درجہ چوڑائی میں زیادہ سے زیادہ دوگنا متغیر ہے۔ ان گرافوں میں، مثال کے طور پر، فاصلہ-موروثی گراف، کے پابند اقدار کے لیے-پتی کی طاقت، اور پابند تین چوڑائی کے گراف شامل ہیں۔ بے حسی گراف (مساوی طور پر، یونٹ وقفہ گراف یا مناسب وقفہ گراف) میں زیادہ سے زیادہ دو جڑواں چوڑائی ہوتی ہے۔ یونٹ ڈسک گراف کی وضاحت یونٹ ڈسک کے سیٹوں سے کی گئی ہے جو طیارہ کے ہر نقطہ کا احاطہ کرتے ہیں۔ اعلی طول و عرض میں یونٹ بال گراف کے لیے بھی یہی سچ ہے۔ ممنوعہ تعدد نمونے کے ساتھ تعدد سے آنے والے تعدد گرافوں نے جڑواں چوڑائی کو محدود کیا ہے۔ یہ ممنوعہ نمونوں کے ساتھ ترتیبات پر الگورتھمک مسائل پر جڑواں چوڑائی کا اطلاق کرنے کی اجازت دیتا ہے۔ ممنوعہ نابالغوں کے ذریعہ بیان کردہ گراف کے ہر خاندان نے جڑواں چوڑائی کو پابند کیا ہے۔ مثال کے طور پر، ویگنر کے نظریہ کے مطابق، پلانر گراف کے لیے ممنوع نابالغ دو گراف ہیں اور، اس لیے پلانر گراف نے جڑواں چوڑائی کو محدود کیا ہے۔ باؤنڈڈ اسٹیک نمبر یا باؤنڈڈ کیو نمبر کے ہر گراف میں بھی باؤنڈڈ جڑواں چوڑائی ہوتی ہے۔ باؤنڈڈ اسپارس جڑواں چوڑائی کے گراف کے خاندان موجود ہیں جن میں باؤنڈڈ اسٹیک نمبر نہیں ہے، لیکن قطار نمبر کے لیے متعلقہ سوال کھلا رہتا ہے۔ باؤنڈڈ جڑواں چوڑائی کے کسی بھی دو گراف کا مضبوط پروڈکٹ، جس میں سے ایک باؤنڈڈ ڈگری ہے، دوبارہ باؤنڈڈ جڑواں چوڑائی رکھتا ہے۔ اس کا استعمال گرافوں کی کلاسوں کی باؤنڈڈ جڑواں چوڑائی کو ثابت کرنے کے لیے کیا جا سکتا ہے جن میں راستوں کے مضبوط پروڈکٹ اور باؤنڈڈ-ٹری وڈتھ گراف، جیسے-پلینر گراف میں سڑنا ہوتا ہے۔ گراف کے لیکسیگرافک پروڈکٹ کے لیے، جڑواں چوڑائی بالکل دو فیکٹر گراف کی چوڑائی کی زیادہ سے زیادہ ہوتی ہے۔ جڑواں چوڑائی کئی دیگر معیاری گراف مصنوعات کے تحت بھی اچھی طرح سے برتاؤ کرتی ہے، لیکن گراف کے ماڈیولر پروڈکٹ کے تحت نہیں۔ باؤنڈڈ جڑواں چوڑائی کے گراف کے ہر موروثی خاندان میں، اس کے گراف کے عمودی حصوں کے لیے کل آرڈرز کا ایک خاندان تلاش کرنا ممکن ہے تاکہ انڈیوسڈ سب گراف پر وراثت میں ملنے والا آرڈر بھی خاندان میں ایک آرڈر ہو، اور اس طرح ان آرڈرز کے حوالے سے خاندان چھوٹا ہو۔ اس کا مطلب یہ ہے کہ، عمودی پر کل ترتیب کے لیے، اس ترتیب سے مطابقت رکھنے والے خاندان میں گراف کی تعداد زیادہ سے زیادہ واحد میں ایکسپونینشل ہوتی ہے۔ اس کے برعکس، ترتیب شدہ گرافوں کا ہر موروثی خاندان جو اس لحاظ سے چھوٹا ہے، جڑواں چوڑائی سے جڑا ہوا ہے۔ اصل میں یہ قیاس کیا گیا تھا کہ لیبل شدہ گرافوں کا ہر موروثی خاندان جو چھوٹا ہے، اس معنی میں کہ گرافوں کی تعداد زیادہ سے زیادہ ایک واحد ایکسپونینشیل فیکٹر اوقات ہے، نے جڑواں چوڑائی کو محدود کیا ہے۔ تاہم، اس قیاس کو ایک لامحدود کیلی گراف کے انڈیوسڈ سب گراف کے ایک خاندان کا استعمال کرتے ہوئے غلط ثابت کیا گیا تھا جو لیبل شدہ گراف کے طور پر چھوٹے ہیں لیکن ان میں جڑواں چوڑائی نہیں ہے۔ گراف کے درج ذیل خاندانوں میں لامحدود جڑواں چوڑائی کے گراف موجود ہیں: باؤنڈ ڈگری کے گراف۔ وقفہ گراف۔ یونٹ ڈسک گراف۔ ان میں سے ہر ایک معاملے میں، نتیجہ ایک گنتی کی دلیل کے بعد آتا ہے: دی گئی قسم کے اس سے زیادہ گراف ہوتے ہیں جو پابند جڑواں چوڑائی کے گراف ہو سکتے ہیں۔ خصوصیات اگر کسی گراف نے جڑواں چوڑائی کو محدود کیا ہے، تو سنکچن کا ایک ورسٹائل ٹری تلاش کرنا ممکن ہے۔ یہ سنکچن ترتیبات کا ایک بڑا خاندان ہے، کچھ (بڑے) پابند چوڑائی، تاکہ ہر ترتیب میں ہر مرحلے پر لکیری طور پر عمودی طور پر بہت سے جداگانہ جوڑے ہوں جن میں سے ہر ایک کو ترتیب میں اگلے مرحلے پر سکڑایا جا سکتا ہے۔ اس سے یہ پتہ چلتا ہے کہ دیئے گئے عمودی حصوں کے کسی بھی سیٹ پر باؤنڈڈ جڑواں چوڑائی کے گرافوں کی تعداد صرف ایک واحد ایکسپونینشل عنصر سے بڑی ہوتی ہے، کہ باؤنڈڈ جڑواں چوڑائی کے گرافوں میں ایک ملحقہ لیبلنگ اسکیم ہوتی ہے جس میں صرف بٹس فی ورٹیکس کی لوگرتھمک تعداد ہوتی ہے، اور یہ کہ ان کے پاس کثیر الجہتی سائز کے عالمگیر گراف ہوتے ہیں جس میں باؤنڈڈ جڑواں چوڑائی کا ہر-ورٹیکس گراف ایک محرک ذیلی گراف کے طور پر پایا جا سکتا ہے۔ الگورتھم زیادہ سے زیادہ ایک جڑواں چوڑائی کے گراف کو کثیر الجہتی وقت میں پہچانا جا سکتا ہے۔ تاہم، یہ طے کرنا این پی مکمل ہے کہ آیا دیئے گئے گراف میں زیادہ سے زیادہ چار پر جڑواں چوڑائی ہے، اور 5/4 سے بہتر تخمینہ تناسب کے ساتھ جڑواں چوڑائی کا تخمینہ لگانے کے لیے این پی سخت ہے۔ ایکسپونینشیل ٹائم مفروضے کے تحت، جڑواں چوڑائی کا حساب لگانے کے لیے کم از کم ایکسپونینشیل وقت درکار ہوتا ہے، آن-ورٹیکس گرافز میں۔ عملی طور پر، ایس اے ٹی حل کرنے والوں کا استعمال کرتے ہوئے اعتدال پسند سائز کے گراف کی جڑواں چوڑائی کا حساب لگانا ممکن ہے۔ باؤنڈڈ جڑواں چوڑائی کے گراف کے زیادہ تر معروف خاندانوں کے لیے، کثیر الجہتی وقت میں باؤنڈڈ چوڑائی کا سنکچن تسلسل بنانا ممکن ہے۔ ایک بار سنکچن سیکوینس دیے جانے یا تعمیر کیے جانے کے بعد، اس کا استعمال کرتے ہوئے بہت سے مختلف الگورتھمک مسائل کو حل کیا جا سکتا ہے، بہت سے معاملات میں ان گرافوں کے مقابلے میں زیادہ مؤثر طریقے سے حل کیا جا سکتا ہے جن میں جڑواں چوڑائی نہیں ہوتی ہے۔ جیسا کہ ذیل میں تفصیل سے بتایا گیا ہے، ان میں این پی ہارڈ مسائل کے لیے عین مطابق پیرامیٹرائزڈ الگورتھم اور تخمینہ الگورتھم کے ساتھ ساتھ کچھ مسائل بھی شامل ہیں جن میں کلاسیکی کثیر الجہتی وقت کے الگورتھم ہوتے ہیں لیکن اس کے باوجود باؤنڈڈ جڑواں چوڑائی کے مفروضے کا استعمال کرتے ہوئے تیز کیا جا سکتا ہے۔ پیرامیٹرائزڈ الگورتھم گرافوں پر ایک الگورتھمک مسئلہ جس میں ایک متعلقہ پیرامیٹر ہوتا ہے اسے فکسڈ پیرامیٹر ٹریکٹ ایبل کہا جاتا ہے اگر اس میں کوئی الگورتھم ہوتا ہے جو عمودی اور پیرامیٹر ویلیو والے گرافوں پر کچھ مستقل اور کمپیوٹیبل فنکشن کے لیے وقت پر چلتا ہے۔ مثال کے طور پر، اس لحاظ سے ایک رننگ ٹائم فکسڈ پیرامیٹر ٹریک ایبل ہوگا۔ تجزیہ کا یہ انداز عام طور پر ان مسائل پر لاگو ہوتا ہے جن کا پولینومیل ٹائم الگورتھم معلوم نہیں ہوتا ہے، کیونکہ بصورت دیگر فکسڈ پیرامیٹر ٹریکٹیبلٹی معمولی ہوگی۔ اس طرح کے بہت سے مسائل کو پیرامیٹر کے طور پر جڑواں چوڑائی کے ساتھ فکسڈ پیرامیٹر ٹریک ایبل دکھایا گیا ہے، جب باؤنڈڈ چوڑائی کا سنکچن تسلسل ان پٹ کے حصے کے طور پر دیا جاتا ہے۔ یہ، خاص طور پر، اوپر درج پابند جڑواں چوڑائی کے گراف خاندانوں پر لاگو ہوتا ہے، جس کے لیے ایک سنکچن ترتیب کو مؤثر طریقے سے بنایا جا سکتا ہے۔ تاہم، یہ معلوم نہیں ہے کہ کم جڑواں چوڑائی کے صوابدیدی گراف کے لیے ایک اچھا سنکچن تسلسل کیسے تلاش کیا جائے، جب کہ گراف میں کوئی دوسری ساخت معلوم نہیں ہے۔ دی گئی سنکچن سیکوینس کے ساتھ باؤنڈڈ جڑواں چوڑائی کے گراف کے لیے فکسڈ پیرامیٹر ٹریکٹ ایبل مسائل میں شامل ہیں: یہ جانچنا کہ آیا دیا گیا گراف گراف کی فرسٹ آرڈر منطق میں کسی دی گئی پراپرٹی کو ماڈل کرتا ہے۔ یہاں، پراپرٹی کی جڑواں چوڑائی اور تفصیل کی لمبائی دونوں تجزیہ کے پیرامیٹرز ہیں۔ اس قسم کے مسائل میں باؤنڈ سائز کے سب گراف کے لیے سب گراف آئسومورفزم، اور باؤنڈ سائز کے کور یا غالب سیٹوں کے لیے ورٹیکس کور اور ڈومینیٹنگ سیٹ کے مسائل شامل ہیں۔ پراپرٹی کو بیان کرنے والے منطقی فارمولے کی لمبائی پر ان عمومی طریقوں کا انحصار ٹیٹریشنل ہے، لیکن آزاد سیٹ، غالب سیٹ، اور متعلقہ مسائل کے لیے اسے آزاد یا غالب سیٹ کے سائز میں ایکسپونینشل تک کم کیا جا سکتا ہے، اور ذیلی گراف آئسومورفزم کے لیے اسے ذیلی گراف کے عمودی حصوں کی تعداد میں فیکٹوریئل تک کم کیا جا سکتا ہے۔ مثال کے طور پر، ایک دی گئی ترتیب کے ساتھ ایک-ورٹیکس گراف کے لیے، ایک-ورٹیکس آزاد سیٹ تلاش کرنے کا وقت، ایک متحرک پروگرامنگ الگورتھم کے ذریعے ہے جو سکڑنے کی ترتیب کی آگے کی سمت میں سرخ گراف کے چھوٹے منسلک ذیلی گراف پر غور کرتا ہے۔ یہ وقت کی حدود بہترین ہیں، ایکسپونینٹ میں لوگرتھمک عوامل تک، ایکسپونینشل ٹائم مفروضے کے تحت۔ گراف کی فرسٹ آرڈر منطق کو مکمل طور پر ترتیب شدہ عمودی کے ساتھ گراف تک بڑھانے کے لیے، اور منطقی پیش گوئیاں جو اس ترتیب کی جانچ کر سکتی ہیں، ماڈل چیکنگ اب بھی پابند جڑواں چوڑائی کے موروثی گراف خاندانوں کے لیے فکسڈ پیرامیٹر ٹریکٹ ایبل ہے، لیکن (معیاری پیچیدگی-نظریاتی مفروضوں کے تحت) غیر محدود جڑواں چوڑائی کے موروثی خاندانوں کے لیے نہیں۔ منسلک جڑواں چوڑائی کے رنگین گراف، متعدد رنگوں کا استعمال کرتے ہوئے جو ان کے جڑواں چوڑائی اور ان کے سب سے بڑے گروہ کے سائز کے فنکشن سے منسلک ہوتے ہیں۔ مثال کے طور پر، جڑواں چوڑائی کے مثلث سے پاک گرافوں کو لالچی رنگ کے الگورتھم کے ذریعے رنگا جا سکتا ہے جو عمودی حصوں کو اس ترتیب کے الٹا رنگ دیتا ہے جس ترتیب میں وہ تنگ کیے گئے تھے۔ اس نتیجے سے پتہ چلتا ہے کہ باؤنڈڈ جڑواں چوڑائی کے گراف χ-باؤنڈڈ ہیں۔ باؤنڈڈ اسپارس جڑواں چوڑائی کے گراف خاندانوں کے لیے، عام رنگ کے نمبر باؤنڈ ہوتے ہیں۔ یہاں، عمومی رنگ نمبر زیادہ سے زیادہ ہوتا ہے اگر عمودی کو لکیری طور پر اس طرح ترتیب دیا جا سکتا ہے کہ ہر عمودی ترتیب میں سب سے پہلے عمودی تک پہنچ سکے، ترتیب میں بعد کے عمودی راستوں کے ذریعے لمبائی کے راستوں کے ذریعے۔ کلاسیکی الگورتھم کے اسپیڈ اپس باؤنڈڈ جڑواں چوڑائی کے گرافوں میں، چوٹیوں والے گراف پر چوڑائی سے پہلی تلاش کرنا ممکن ہے، وقت کے ساتھ، یہاں تک کہ جب گراف گھنے ہو اور اس کے کنارے اس وقت سے زیادہ ہوں۔ لگ بھگ الگورتھم میں جڑواں چوڑائی والے الگورتھم کا بھی اطلاق کیا گیا ہے۔ خاص طور پر، پابند جڑواں چوڑائی کے گرافوں میں، پابند تخمینہ تناسب کے ساتھ کم از کم غالب سیٹ کا تخمینہ لگانا ممکن ہے۔ یہ زیادہ عام گراف کے برعکس ہے، جس کے لیے لگ بھگ تناسب حاصل کرنا NP-مشکل ہے جو لوگرتھمک سے بہتر ہے۔ زیادہ سے زیادہ آزاد سیٹ اور گراف رنگنے کے مسائل کا تخمینہ باؤنڈڈ جڑواں چوڑائی کے گرافوں پر کثیر الجہتی وقت میں، ہر ایک کے لیے، تخمینہ تناسب کے اندر لگایا جا سکتا ہے۔ اس کے برعکس، باؤنڈڈ جڑواں چوڑائی کے مفروضے کے بغیر، اس فارم کے کسی بھی تخمینہ تناسب کو حاصل کرنا NP-مشکل ہے۔ حوالہ جات مزید پڑھنا گراف غیر متغیرات