عدّ الحد الأدنى من التقاطعات في هيبرغرافس ذات أبعاد VC محدودة

ننظر في مشكلة عدّ جميع التقاطعات الدنيا (المعروفة أيضاً باسم مجموعات الضرب الدنيا) في هيبرغراف H. يُعتبر صياغة مكافئة لهذه المشكلة، المعروفة بمشكلة هيبرغراف التقاطع (أو مشكلة ازدواج الهيبرغراف)، هي تحديد، عند إعطاء هيبرغرا في هيبرغرافين، ما إذا كان أحدهما يتوافق مع مجموعة التقاطعات الدنيا للآخر. وجود خوارزمية زمن كثير الحدود لحل هذه المشكلة هو سؤال مفتوح منذ زمن طويل. في fredmancomplexity₁996، يقدم المؤلفون أول خوارزمية دون أسية لحل مشكلة هيبرغراف التقاطع، والتي تعمل في زمن شبه كثير الحدود، مما يجعل من غير المحتمل أن تكون المشكلة NP-complete أو (co) NP-complete. في هذه الورقة، نظهر أنه عندما يكون أحد الهيبرغرافين ذا بعد VC محدود، يمكن حل مشكلة هيبرغراف التقاطع في زمن كثير الحدود، أو بمعنى آخر، إذا كان H هيبرغراف ذا بعد VC محدود، فإن هناك خوارزمية زمن كثير الحدود لعدّ تقاطعاته الدنيا. تعمق هذه النتيجة معظم الحالات المعروفة سابقًا في الأدبيات، حيث إن معظمها يعتبر فئات من الهيبرغرافات ذات بعد VC محدود. ونتيجة لذلك، فإن مشكلة تقاطع الهيبرغراف قابلة للحل في زمن كثير الحدود لأي فئة من الهيبرغرافات مغلقة تحت الهيبرغرافات الفرعية الجزئية. كما نظهر أن الخوارزمية المقترحة تعمل في زمن شبه كثير الحدود في الهيبرغرافات العامة وتعمل في زمن كثير الحدود إذا كانت توافقية الهيبرغراف محدودة، وهو واحد من الحالات المعروفة القليلة حيث يكون بعد VC غير محدود.