Dense subgraph
گراف تھیوری اور کمپیوٹر سائنس میں، گھنے ذیلی گراف ایک ذیلی گراف ہے جس کے ہر سرے پر بہت سے کنارے ہوتے ہیں۔ اسے اس طرح رسمی شکل دی گئی ہے: ایک غیر ہدایت شدہ گراف ہونے دیں اور اس کا ذیلی گراف ہونے دیں۔ پھر کی کثافت کی تعریف اس طرح کی جاتی ہے: سب گراف کا سب سے گھنے مسئلہ زیادہ سے زیادہ کثافت والے سب گراف کو تلاش کرنا ہے۔ گراف کے زیادہ سے زیادہ گھنے ذیلی گراف کی کثافت کو بعض اوقات اس کی ذیلی گراف کثافت کہا جاتا ہے۔ 1984 میں، اینڈریو وی گولڈ برگ نے میکس فلو تکنیک کا استعمال کرتے ہوئے زیادہ سے زیادہ کثافت والے ذیلی گراف کو تلاش کرنے کے لیے ایک کثیر الجہتی ٹائم الگورتھم تیار کیا۔ اسے 1989 میں گیلو، گریگوریڈس اور ٹارجن نے وقت پر چلانے کے لیے بہتر بنایا ہے۔ بہترین حل تلاش کرنے کے لیے ایک سادہ ایل پی 2000 میں چرکر نے دی تھی۔ ذیلی گراف کی کثافت آربریسیٹی اور گراف انحطاط سے متعلق تصور کے لیے غیر علامتی ہے۔ سب سے گھنے سب گراف سب سے گھنے سب گراف کے مسئلے پر بہت سے تغیرات ہیں۔ ان میں سے ایک گھنے سب گراف کا مسئلہ ہے، جہاں مقصد بالکل عمودی پر زیادہ سے زیادہ کثافت والے سب گراف کو تلاش کرنا ہے۔ یہ مسئلہ گروہ کے مسئلے کو عام کرتا ہے اور اس طرح عام گراف میں این پی سخت ہوتا ہے۔ ایک کثیر الجہتی الگورتھم موجود ہے جو ہر ایک کے تناسب کے اندر سب سے گھنے ذیلی گراف کا تخمینہ لگاتا ہے، جبکہ یہ کثیر الجہتی وقت میں-ضمیمہ کو تسلیم نہیں کرتا ہے جب تک کہ ایکسپونینشیل ٹائم مفروضہ غلط نہ ہو۔ ایک کمزور مفروضے کے تحت کہ اس مسئلے کے لیے کوئی پی ٹی اے ایس موجود نہیں ہے۔ مسئلہ دو طرفہ گرافوں اور کورڈل گرافوں میں این پی سخت رہتا ہے لیکن درختوں اور تقسیم شدہ گرافوں کے لیے کثیر الجہتی ہے۔ یہ کھلا ہے کہ آیا مسئلہ این پی ہارڈ ہے یا (مناسب) وقفہ گراف اور پلانر گراف میں کثیر الجہتی ؛ تاہم، اس مسئلے کی ایک تغیر جس میں ذیلی گراف کو جوڑنا ضروری ہے، پلانر گراف میں این پی ہارڈ ہے۔ زیادہ سے زیادہ ذیلی گراف پر سب سے زیادہ گھنے کا مقصد زیادہ سے زیادہ عمودی پر زیادہ سے زیادہ کثافت والے ذیلی گراف کو تلاش کرنا ہے۔ اینڈرسن اور چیلاپلا نے دکھایا کہ اگر اس مسئلے کے لیے کوئی قربت موجود ہے تو یہ سب گراف کے سب سے گھنے مسئلے کے لیے قربت کا باعث بنے گا۔ سب سے گھنے کم از کم سب گراف سب سے گھنے مسئلے کی تعریف اسی طرح کی جاتی ہے جیسے زیادہ تر سب گراف مسئلے میں سب سے زیادہ۔ مسئلہ این پی مکمل ہے، لیکن کثیر الجہتی وقت میں 2-ضمیمہ کو تسلیم کرتا ہے۔ مزید برآں، اس بات کے کچھ شواہد موجود ہیں کہ یہ تخمینہ الگورتھم بنیادی طور پر بہترین ممکن ہے: چھوٹے سیٹ کے توسیعی مفروضے کو فرض کرتے ہوئے (ایک کمپیوٹیشنل پیچیدگی کا مفروضہ جو منفرد گیم قیاس سے قریب سے متعلق ہے)، پھر ہر مستقل کے لیے عنصر کے اندر مسئلے کا تخمینہ لگانا این پی مشکل ہے۔ - کلک ڈینسسٹ سب گراف چارالمپوس سوراکاکس نے-کلک ڈینسسٹ سب گراف کا مسئلہ متعارف کرایا۔ سب گراف کے سب سے گھنے مسئلے کی اس تغیر کا مقصد انڈیوسڈ کلکس کی اوسط تعداد کو زیادہ سے زیادہ کرنا ہے، جہاں انڈیوسڈ-کلکس کا مجموعہ ہے۔ نوٹ کریں کہ سب گراف کا سب سے گھنے مسئلے کو ایک خصوصی کیس کے طور پر حاصل کیا جاتا ہے۔ یہ عمومی کاری بڑے پیمانے پر حقیقی دنیا کے نیٹ ورکس سے قریب قریب کلکس نکالنے کے لیے ایک تجرباتی طور پر کامیاب پولی ٹائم نقطہ نظر فراہم کرتی ہے۔ مقامی طور پر سب سے زیادہ گھنے ذیلی گراف کن اور دیگر۔ گراف میں ٹاپ-کے مقامی طور پر گھنے سب گراف کی دریافت کا مسئلہ متعارف کرایا گیا، جن میں سے ہر ایک گراف میں اپنے مقامی علاقے میں سب سے زیادہ کثافت حاصل کرتا ہے: یہ نہ تو کسی بھی سپر گراف میں موجود ہے جس میں اتنی ہی یا زیادہ کثافت ہے، اور نہ ہی اس میں ایسے سب گراف شامل ہیں جن کی کثافت باقی مقامی گھنے سب گراف کے ساتھ ڈھیلی طور پر جڑی ہوئی ہے۔ نوٹ کریں کہ سب گراف کا سب سے گھنے مسئلے کو ایک خصوصی کیس کے طور پر حاصل کیا جاتا ہے۔ گراف میں مقامی طور پر گھنے سب گرافوں کے سیٹ کا حساب کثیر الجہتی وقت میں کیا جا سکتا ہے۔ حوالہ جات مزید پڑھنا۔ ۔ ۔ ۔ ۔ گراف تھیوری