إيجاد أكثر الرسوم الفرعية كثافة مع قيود على ألوان الحواف

ننظر في نوع من مشكلة الرسم الفرعي الأكثر كثافة في الشبكات ذات سمات الحواف الفردية أو المتعددة. على سبيل المثال، في شبكة اجتماعية، قد تصف سمات الحواف نوع العلاقة بين المستخدمين، مثل الأصدقاء أو العائلة أو المعارف، أو أنواع مختلفة من التواصل. من أجل البساطة المفاهيمية، نعتبر السمات كألوان الحواف. المشكلة الجديدة التي نتناولها هي إيجاد رسم فرعي كثيف متنوع يحقق المتطلبات المعطاة بشأن أعداد الحواف من ألوان معينة. عند البحث عن مجتمع كثيف في الشبكة الاجتماعية، ستفرض مشكلتنا المتطلب أن المجتمع متنوع وفقاً لمعايير محددة من خلال سمات الحواف. نوضح أن النسخ القرارية لإيجاد عدد دقيق، أو كحد أقصى، أو كحد أدنى من h حواف ملونة في الرسم الفرعي الأكثر كثافة، حيث h هو متجه لمتطلبات اللون، هي NP-complete، حتى مع لونين فقط. بالنسبة لمشكلة إيجاد رسم فرعي كثيف يحتوي على ما لا يقل عن h حواف ملونة، نقدم خوارزمية تقريبية من حيث العامل الثابت في زمن خطي عندما يكون الرسم المدخل Sparse. في الطريق، نقدم مشكلة الرسم الفرعي الأكثر كثافة التي تحتوي على على الأقل h حواف (غير ملونة)، ونوضح صعوبتها، ونقدم أيضاً تقريباً زمنياً خطياً مع عامل ثابت. في تجاربنا، نوضح كفاءة وفاعلية خوارزمياتنا الجديدة.