مجموعه گره‌های بازخورد

در نظریه گراف، مجموعه گره‌های بازخورد مجموعه‌ای از گره‌های گرافی است که برداشتنشان گراف را بدون دور می‌کند. به سخنی دیگر، مجموعه بازخورد دست‌کم گره‌ای را از هر دور در گراف دارد. از دید نظریه پیچیدگی محاسباتی، مجموعه گره بازخورد ان‌پی کامل است. مجموعه گره بازخورد یکی از ۲۱ پرسشی است که کارپ پیچیدگی رایانشی‌شان را بررسی کرده‌است. مجموعه گره‌های بازخورد کاربردی گسترده در سامانه عامل، پایگاه داده و زمینه تراشه‌های وی‌ال‌اس‌آی دارد.
تعریف
نمونه تصمیمی مجموعه گره‌های بازخورد:
درون‌داد: گراف و عدد درست .
برون‌داد: آیا برداشتن گره از می‌تواند گراف را بدون دور کند؟
نمونه بهینه‌سازی، مجموعه کمینه گره‌های بازخورد، کمترین شماری از گره‌ها را می‌جوید که با برداشتنشان گراف بدون دور می‌گردد. گراف برون‌داد جنگل است. می‌توان نشان داد که یافتن جنگل بیشینه دوگانه‌ی  یافتن گره‌های بازخورد کمینه است: یافتن جنگل بیشینه هم‌ارز است با یافتن گره‌های بازخورد کمینه.
سختی NP
نشان دادکه مسئله مجموعه گره بازخورد برای گراف‌های جهت دار، NP-کامل است.مسئله NP-کامل روی گراف‌های جهت دار بادرجه‌ی ورودی و خروجی 2، وروی گراف‌های جهت دار دو طرفه با درجه داخلی و خارجی 2 باقی می‌ماند..
کاهش کارپ همچنین کامل بودن NP مسئله مجموعه گره بازخورد را روی گراف‌های بدون جهت ذکر می‌کند،جایی که مسئله روی گراف‌هایی از بیشینه درجه 4 ،NP سخت باقی می‌ماند.مسئله مجموعه گره بازخورد می‌تواند در زمان چندجمله‌ای روی گراف‌هایی از حداکثر درجه 3 حل شود.
توجه کنید مسئله پاک کردن یال‌ها برای ایجاد گراف بدون دور معادل است با پیدا کردن یک درخت پوشای کمینه،که می‌تواند در زمان چندجمله‌ای انجام شود.در تضاد بااین،مسئله پاک کردن یال‌ها از یک گراف جهت دار برای بدون دور کردنش،مسالع یال‌های بازخورد،NP-کامل است، را ببینید.
الگوریتم‌های دقیق
مسئله بهینه‌سازی NP متناظر با پیداکردن یک مجموعه گره بازخورد کمینه می‌تواند در زمانO(1.7347 n ), حل شود،جایی که n تعداد گره‌ها گراف است.. این الگوریتم در واقع یک جنگل مشتق شده بیشینه را محاسبه می‌کند،و و قتی که جنگلی به دست آمد، مکمل آن مجموعه گره بازخورد کمینه است.تعداد مجموعه‌های گره بازخورد در یک گراف به وسیله‌ی O(1.8638 n ). محدود می‌شود.مسئله گره بازخورد جهت دار هنوز می‌تواند در زمان O*(1.9977 n ), حل شود،جایی که n تعداد گره‌ها در گراف جهت دار داده شده‌است.. نسخه پارامتری شده از مسائل جهت دار و بدون جهت ،هر دو غیر بغرنج باپارامتر ثابت هستند.
تخمین
مسئله APX-کامل است،که مستقیما به دنبال کامل بودن APX از مسئله پوشش گره می‌آید و وجود یک حفظ تقریبی کاهش L از مسئله پوشش گره که برای آن می‌آید. معروفترین تخمین روی گراف‌های بدون جهت به وسیله‌ی یک عامل دو است.
کران‌ها
مطابق با نظریه Erdős–Pósa اندازه مجموعه گره بازخورد کمینه در داخل یک عامل لگاریتمی از حداکثر تعداد گره‌ها غیرمرتبط دورها در گراف داده شده‌است.
کاربردها
در سیستم‌های عامل ،مجموعه گره بازخورد نقشی برجسته در مطالعه بازیابی بن بست بازی می‌کند.در به انتظار نشستن برای گراف از یک سیستم عامل،هردور جهت دار متناظر با یک موقعیت بن بست است.به منظور حل کردن همه بن بست‌ها،بعضی از فرایندهای مسدود شده باید کنارگذاشته شوند.یک مجموعه گره بازخورد در این گراف متناظر است با یک حداقل تعداد از فرایندهایی که احتیاج به کنارگذاشته شدن دارد.
علاوه براین،مسئله مجموعه گره بازخورد،کاربردهای فراوانی درطراحی چیپ وی‌ال‌اس‌آی (cf. ) و مونتاژژنوم دارد.
منبع‌ها
مقاله‌های پژوهشی
Ann Becker, Reuven Bar-Yehuda, Dan Geiger: Randomized Algorithms for the Loop Cutset Problem. J. Artif. Intell. Res. (JAIR) 12: 219-234 (2000)
Optimization of Pearls Method of Conditioning and Greedy-Like Approximation Algorithms for the Vertex Feedback Set Problem.
SWAT 2010
Jianer Chen, Fedor V. Fomin, Yang Liu, Songjian Lu, Yngve Villanger: Improved algorithms for feedback vertex set problems. J. Comput. Syst. Sci. 74(7): 1188-1198 (2008)
Jianer Chen, Yang Liu, Songjian Lu, Barry OSullivan, Igor Razgon: A fixed-parameter algorithm for the directed feedback vertex set problem. J. ACM 55(5): (2008)
On the hardness of approximating minimum vertex cover
On the Minimum Feedback Vertex Set Problem: Exact and Enumeration Algorithms.
Proc. of STACS 2010
A1.1: GT7, pg.191.
Complexity of Computer Computations, Proc. Sympos. IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y.. New York: Plenum
I. Razgon : Computing Minimum Directed Feedback Vertex Set in O*(1.9977n). In: Giuseppe F. Italiano, Eugenio Moggi, Luigi Laura (Eds.), Proceedings of the 10th Italian Conference on Theoretical Computer Science 2007, World Scientific, pp. 70–81 ( , ).
کتاب‌ها و مقاله‌ها آموزشی
P. Festa, P.M. Pardalos, and M.G.C. Resende, Feedback set problems, Handbook of Combinatorial Optimization, D.-Z. Du and P.M. Pardalos, Eds., Kluwer Academic Publishers, Supplement vol. A, pp. 209–259, 2000.
Operating System Concepts