Refining the complexity of the sports elimination problem

مشکل حذف ورزش این است که آیا تیمی که در یک رقابت شرکت می کنند، همچنان فرصتی برای برنده شدن دارد، با توجه به شرایط کنونی و مسابقات باقیمانده در میان تیم ها. این مشکل را می توان به عنوان یک مسئله نشانه گذاری گراف مشاهده کرد که در آن کمان ها برچسب هایی را به دست می دهند که به امتیاز هر دو نقطه قوس کمک می کنند و هدف این است که قوس ها را به عنوان یک قاعده بدست آورند که هر رأس نمره را از ظرفیت خود بالاتر می برد. ما پیچیدگی این مشکل را با جزئیات با استفاده از یک رویکرد چند متغیره برای بررسی اینکه چگونه پارامترهای مختلف گراف ورودی (مانند حداکثر درجه، تعداد رأس / لبه بازخورد و پارامترهای عرض) بازتابی محاسباتی را بررسی می کنیم، بررسی می کنیم. ما چند الگوریتم کارآمد و همچنین نتایج سختی خاصی را به دست می آوریم.