غير مانع

في نظرية المخططات ، تُعرف المجموعة غير المُعطِّلة بأنها مجموعة جزئية من الرؤوس في مخطط غير موجه ، جميعها مجاورة لرؤوس خارج المجموعة الجزئية. وبصورة مكافئة، تُعرف المجموعة غير المُعطِّلة بأنها مُكمِّلة المجموعة المُهيمنة . ^{[ 1 ]}

صاغ باباديميتريو وياناكاكيس (1991) المسألة الحسابية لإيجاد أكبر عنصر غير مانع في الرسم البياني ، ولاحظا أنها تنتمي إلى مسألة MaxSNP . ^{[ 2 ]} على الرغم من أن حساب مجموعة مهيمنة ليس قابلاً للحل باستخدام معلمات ثابتة في ظل الافتراضات القياسية، فإن المسألة التكميلية المتمثلة في إيجاد عنصر غير مانع بحجم معين قابلة للحل باستخدام معلمات ثابتة. ^{[ 1 ]}

في الرسوم البيانية التي لا تحتوي على رؤوس معزولة ، فإن كل مجموعة غير مانعة قصوى (أي التي لا يمكن إضافة المزيد من الرؤوس إليها) هي نفسها مجموعة مهيمنة. ^{[ 3 ]}

إحدى طرق بناء خوارزمية قابلة للمعالجة ذات معلمات ثابتة لمسألة عدم الحظر هي استخدام التجزئة ، وهو مبدأ تصميم خوارزمي يُستخدم فيه خوارزمية ذات زمن متعدد الحدود لتقليل حالة مشكلة أكبر إلى حالة مكافئة يكون حجمها محدودًا بدالة للمعلمة. بالنسبة لمسألة عدم الحظر، يتكون مدخل المسألة من رسم بياني.${\displaystyle G}$ومعامل${\displaystyle k}$والهدف هو تحديد ما إذا كان${\displaystyle G}$يحتوي على برنامج غير مانع مع${\displaystyle k}$أو أكثر من الرؤوس. ^{[ 1 ]}

تتميز هذه المسألة بسهولة تحويلها إلى نواة، مما يختزلها إلى مسألة مكافئة ذات حد أقصى.${\displaystyle 2k}$الرؤوس. أولاً، قم بإزالة جميع الرؤوس المعزولة من${\displaystyle G}$لأنها لا يمكن أن تكون جزءًا من أي عقدة غير مانعة. بمجرد القيام بذلك، يجب أن يحتوي الرسم البياني المتبقي على عقدة غير مانعة تشمل نصف رؤوسه على الأقل؛ على سبيل المثال، إذا تم تلوين أي شجرة ممتدة للرسم البياني بلونين ، فإن كل فئة لونية تُعد عقدة غير مانعة، وإحدى فئتي اللون تشمل نصف الرؤوس على الأقل. لذلك، إذا كان الرسم البياني الذي تمت إزالة رؤوسه المعزولة لا يزال يحتوي على${\displaystyle 2k}$إذا كان عدد الرؤوس أكثر من ذلك، يمكن حل المشكلة فورًا. وإلا، فإن الرسم البياني المتبقي هو نواة تحتوي على عدد رؤوس لا يتجاوز${\displaystyle 2k}$الرؤوس. ^{[ 1 ]}

قام ديهن وآخرون بتحسين ذلك إلى نواة بحجم لا يتجاوز${\displaystyle {\tfrac {5}{3}}k+3}$تتضمن طريقتهم دمج أزواج من جيران الرؤوس من الدرجة الأولى حتى يصبح لكل رأس من هذه الرؤوس جار واحد فقط، ثم إزالة جميع الرؤوس من الدرجة الأولى باستثناء رأس واحد، مما يترك حالة مكافئة برأس واحد فقط من الدرجة الأولى. بعد ذلك، يوضحون أنه (باستثناء القيم الصغيرة لـ${\displaystyle k}$(والتي يمكن التعامل معها بشكل منفصل) يجب أن تكون هذه الحالة إما أصغر من الحد الأقصى لحجم النواة أو تحتوي على${\displaystyle k}$-حاجب الرؤوس. ^{[ 1 ]}

بمجرد الحصول على نواة صغيرة، يمكن حل مسألة عدم الحظر في وقت قابل للمعالجة ذي معلمات ثابتة عن طريق تطبيق خوارزمية بحث شاملة على النواة. ويؤدي تطبيق حدود زمنية أسرع (لكنها لا تزال أسية) إلى حد زمني لمسألة عدم الحظر على النحو التالي:${\displaystyle O(2.5154^{k}+n)}$. بل إن الخوارزميات الأسرع ممكنة لبعض الفئات الخاصة من الرسوم البيانية. ^{[ 1 ]}

• مجموعة مهيمنة - مكمل لمجموعة غير مانعة.