أقصى قطع

بما أن مشكلة القطع الأقصى هي مشكلة صعبة من نوع NP ، فلا توجد خوارزميات ذات وقت متعدد الحدود معروفة لمشكلة القطع الأقصى في الرسوم البيانية العامة.

مع ذلك، في الرسوم البيانية المستوية ، تُعدّ مسألة القطع الأقصى ثنائية لمسألة فحص المسار (مسألة إيجاد أقصر مسار يمر بكل حافة من حواف الرسم البياني مرة واحدة على الأقل)، بمعنى أن الحواف التي لا تنتمي إلى مجموعة القطع الأقصى للرسم البياني G هي الحواف الثنائية للحواف التي تتكرر في مسار فحص أمثل للرسم البياني الثنائي لـ G. يشكل مسار الفحص الأمثل منحنى متقاطعًا ذاتيًا يقسم المستوى إلى مجموعتين فرعيتين: مجموعة النقاط التي يكون فيها عدد لفات المنحنى زوجيًا، ومجموعة النقاط التي يكون فيها عدد اللفات فرديًا؛ تشكل هاتان المجموعتان الفرعيتان قطعًا يشمل جميع الحواف التي تظهر حوافها الثنائية عددًا فرديًا من المرات في المسار. يمكن حل مسألة فحص المسار في وقت متعدد الحدود، وتسمح هذه الثنائية بحل مسألة القطع الأقصى أيضًا في وقت متعدد الحدود للرسوم البيانية المستوية. ^{[ 9 ]} مع ذلك، من المعروف أن مسألة التقسيم الثنائي الأقصى هي مسألة صعبة الحل من فئة NP. ^{[ 10 ]}

بشكلٍ أعم، عندما يُمكن إيجاد القطع القصوى في وقتٍ متعدد الحدود لفئاتٍ مُعينة من الرسوم البيانية، يُمكن توسيع خوارزميات هذه المسألة لتشمل مجموع الزمر الثنائية والثلاثية للرسوم البيانية في هذه الفئات. وهذا يسمح بتوسيع خوارزمية الرسم البياني المستوي لتشمل عائلاتٍ أوسع من الرسوم البيانية المُغلقة تحت مُحددات الرسوم البيانية ، والتي لها بنية مجموع الزمر للرسوم البيانية المستوية والرسوم البيانية ذات الحجم المحدود. ^{[ 11 ]} تتمتع عائلة الرسوم البيانية المُغلقة تحت مُحدداتها ببنية مجموع الزمر هذه تحديدًا عندما تتضمن مُحدداتها الممنوعة رسمًا بيانيًا بعدد تقاطعات لا يتجاوز واحدًا. ^{[ 12 ]}

تُعدّ مسألة القطع الأقصى مسألة صعبة من نوع APX ، ^{[ 13 ]} مما يعني أنه لا يوجد مخطط تقريبي ذو زمن متعدد الحدود (PTAS) قريب بشكل تعسفي من الحل الأمثل لها، إلا إذا كانت P = NP. وبالتالي، فإن كل خوارزمية تقريبية معروفة ذات زمن متعدد الحدود تحقق نسبة تقريب أقل من واحد.

توجد خوارزمية تقريبية عشوائية بسيطة بنسبة 0.5 : لكل رأس، يتم قلب قطعة نقدية لتحديد أي نصف من التقسيم يُخصص له. ^{[ 14 ]} في المتوسط، نصف الحواف هي حواف مقطوعة. يمكن إزالة العشوائية من هذه الخوارزمية باستخدام طريقة الاحتمالات الشرطية ؛ وبالتالي توجد خوارزمية تقريبية حتمية بسيطة بنسبة 0.5 تعمل في زمن متعدد الحدود. ^{[ 15 ]} تبدأ إحدى هذه الخوارزميات بتقسيم عشوائي لرؤوس الرسم البياني المعطى.${\displaystyle G=(V,E)}$ويقوم بنقل رأس واحد في كل مرة من جانب واحد من التقسيم إلى الجانب الآخر، مما يحسن الحل في كل خطوة، حتى لا يمكن إجراء المزيد من التحسينات من هذا النوع. عدد التكرارات هو على الأكثر${\displaystyle |E|}$لأن الخوارزمية تُحسّن القطع بمقدار حافة واحدة على الأقل في كل خطوة. عند انتهاء الخوارزمية، يكون نصف الحواف المتصلة بكل رأس على الأقل جزءًا من القطع، وإلا فإن تحريك الرأس سيُحسّن القطع. لذلك، يشمل القطع على الأقل${\displaystyle |E|/2}$الحواف.

تُعدّ خوارزمية التقريب متعددة الحدود لمسألة القطع الأقصى، والتي تتميز بأفضل نسبة تقريب معروفة، طريقةً ابتكرها غومانز وويليامسون باستخدام برنامج شبه محدد (يمكن اشتقاقه من المستوى الأول من التسلسل الهرمي لمجموع المربعات ) والتقريب العشوائي . وهي تحقق نسبة تقريب${\displaystyle \alpha \approx 0.878,}$أين

${\displaystyle \displaystyle \alpha ={\frac {2}{\pi }}\min _{0\leq \theta \leq \pi }{\frac {\theta }{1-\cos \theta }}.}$^{[ 16 ]}

إذا كانت فرضية الألعاب الفريدة صحيحة، فإن هذه هي أفضل نسبة تقريب ممكنة للقطع الأقصى. ^{[ 17 ]} وبدون هذه الافتراضات غير المثبتة، فقد ثبت أن تقريب قيمة القطع الأقصى بنسبة تقريب أفضل من NP-hard هو مسألة صعبة من نوع NP.${\displaystyle {\tfrac {16}{17}}\approx 0.941}$[ ^{18 ]​}

يقدم دانينغ وآخرون تحليلاً موسعاً لعشرة أساليب استدلالية لهذه المشكلة، بما في ذلك تطبيق مفتوح المصدر. ^{[ 19 ]}

بينما يُعدّ إثبات أن مسألة إيجاد قطع بحجم لا يقل عن (المعامل) k قابلة للحل باستخدام المعاملات الثابتة (FPT) أمرًا بسيطًا، إلا أنه من الأصعب بكثير إثبات قابلية حل مسألة تحديد ما إذا كان للرسم البياني G قطع بحجم لا يقل عن الحد الأدنى لإدواردز-إردوش (انظر الحدود الدنيا أعلاه) زائد (المعامل) k باستخدام المعاملات الثابتة . وقد أثبت كروستون وآخرون أنه يمكن حل هذه المسألة في وقت${\displaystyle 8^{k}O(n^{4})}$ويقبل نواة بحجم${\displaystyle O(k^{5})}$كما قاموا بتوسيع نتيجة قابلية المعالجة ذات المعلمات الثابتة لتشمل مسألة الرسم البياني الفرعي المتوازن (BSP، انظر الحدود الدنيا أعلاه) وحسّنوا حجم النواة إلى${\displaystyle O(k^{3})}$(ينطبق هذا أيضًا على BSP). ^{[ 20 ]} قام إتشيد ومنيش بتحسين نتيجة قابلية المعالجة ذات المعلمات الثابتة لـ BSP إلى${\displaystyle 8^{k}O(m)}$ونتيجة حجم النواة إلى${\displaystyle O(k)}$الرؤوس. ^{[ 21 ]}

يمكن إيجاد القطع القصوى الموزونة في وقت متعدد الحدود في الرسوم البيانية ذات عرض الشجرة المحدود . أي أنه عند تحديد التعقيد باستخدام عرض الشجرة بدلاً من حجم القطع، تصبح مسألة القطع القصوى الموزونة قابلة للحل باستخدام معلمات ثابتة. وتبقى قابلة للحل باستخدام معلمات ثابتة لعرض الرسم البياني الصغير (sm-width)، وهو معلمة أخرى لعرض الرسم البياني تقع بين عرض الشجرة وعرض الزمرة (clique-width ). ومع ذلك، في ظل الافتراضات القياسية في التعقيد المُعامل، لا تكون قابلة للحل باستخدام معلمات ثابتة لعرض الزمرة (clique-width). ^{[ 22 ]}

باعتبار العقد بمثابة خصائص والحواف بمثابة مسافات، تقسم خوارزمية القطع الأقصى الرسم البياني إلى مجموعتين فرعيتين منفصلتين جيدًا. بعبارة أخرى، يمكن تطبيقها بسهولة لإجراء التصنيف الثنائي . مقارنةً بخوارزميات التصنيف الأكثر شيوعًا، لا تتطلب هذه الخوارزمية فضاء خصائص، بل المسافات بين العناصر داخله فقط. ^{[ 23 ]}

في الفيزياء الإحصائية والأنظمة غير المنتظمة ، تُعادل مسألة القطع الأقصى تقليل دالة هاميلتون لنموذج زجاج الدوران ، أو ببساطة نموذج إيزينغ . ^{[ 24 ]} بالنسبة لنموذج إيزينغ على الرسم البياني G وتفاعلات الجوار الأقرب فقط، تكون دالة هاميلتون هي $${\displaystyle H[s]=-\sum _{ij\in E(G)}J_{ij}s_{i}s_{j}.}$$

هنا، كل رأس i من الرسم البياني هو موقع دوران يمكن أن يأخذ قيمة دوران${\displaystyle s_{i}=\pm 1.}$تقسيم تكوين الدوران${\displaystyle V(G)}$إلى مجموعتين، تلك التي تحتوي على دوران لأعلى${\displaystyle V^{+}}$وتلك التي تخضع لعملية التخفيض التدريجي${\displaystyle V^{-}.}$نرمز بـ${\displaystyle \delta (V^{+})}$مجموعة الحواف التي تربط المجموعتين. يمكننا بعد ذلك إعادة كتابة الهاميلتوني على النحو التالي: $${\displaystyle {\begin{aligned}H[s]&=-\sum _{ij\in E(V^{+})}J_{ij}-\sum _{ij\in E(V^{-})}J_{ij}+\sum _{ij\in \delta (V^{+})}J_{ij}\\&=-\sum _{ij\in E(G)}J_{ij}+2\sum _{ij\in \delta (V^{+})}J_{ij}\\&=C+2\sum _{ij\in \delta (V^{+})}J_{ij}.\end{aligned}}}$$

إن تقليل هذه الطاقة يعادل مسألة القطع الأدنى أو عن طريق تحديد أوزان الرسم البياني على النحو التالي${\displaystyle w_{ij}=-J_{ij},}$مشكلة القطع الأقصى. ^{[ 24 ]}

تُستخدم مشكلة القطع الأقصى في تصميم الدوائر المتكاملة واسعة النطاق (VLSI) . ^{[ 24 ]}