المجموعة المتسقة الدنيا في الأشجار ورسوم الجداول الزمنية

في مشكلة المجموعة المتسقة الدنيا (MCS)، نواجه رسمًا بيانيًا بسيطًا غير موجه متصل G= (V, E)، يتكون من مجموعة رؤوس V بحجم n ومجموعة حواف E. يتم تخصيص لون لكل رأس في V من مجموعة \1, 2, , c\. الهدف هو تحديد مجموعة V' V بأقل عدد ممكن من العناصر، بحيث بالنسبة لكل رأس v V، يجب أن يشارك على الأقل أحد جيرانه الأقرب في V' (مقاسًا بمسافة القفز) نفس اللون مع v. المشكلة القرار، التي تحدد ما إذا كانت هناك مجموعة V' بعدد عناصر لا يزيد عن l لبعض الأعداد الصحيحة الإيجابية l، معروفة بأنها NP-complete حتى للرسوم البيانية المسطحة. في هذه الورقة، نثبت أن مشكلة MCS للأشجار، عندما تعتبر عدد الألوان c كمعامل مدخل، هي NP-complete. نقترح خوارزمية قابلة للحل وفقا لمعامل ثابت (FPT) لمشكلة MCS على الأشجار تعمل في وقت O (2^6cn⁶)، مما يحسن بشكل كبير من الخوارزمية المعروفة حاليًا والتي تعمل في وقت O (2^4cn^2c+3). في محاولة لفهم تعقيد الحساب لمشكلة MCS عبر فئات الرسوم البيانية المختلفة، نوسع تحقيقنا ليشمل الرسوم البيانية الزمنية. نظهر أنها تبقى NP-complete للرسوم البيانية الزمنية، مما يثري فئات الرسوم البيانية التي تبقى فيها MCS غير قابلة للحل.