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

در نظریه گراف، مجموعه گره‌های بازخورد مجموعه‌ای از گره‌های گرافی است که برداشتنشان گراف را بدون دور می‌کند. به سخنی دیگر، مجموعۀ بازخورد دست‌کم گره‌ای را از هر دور در گراف دارد. از دید نظریه پیچیدگی محاسباتی، مجموعه گره بازخورد ان‌پی کامل است. مجموعه گره بازخورد یکی از ۲۱ پرسشی است که کارپ پیچیدگی رایانشی‌شان را بررسی کرده‌است. مجموعه گره‌های بازخورد کاربردی گسترده در سامانۀ عامل، پایگاه داده و زمینۀ تراشه‌های وی‌ال‌اس‌آی دارد.

تعریف

نمونۀ تصمیمی مجموعه گره‌های بازخورد:

• درون‌داد: گراف$G=(V,E)$ و عدد درست $k>0$.
• برون‌داد: آیا برداشتن $k$ گره از $V$ می‌تواند گراف $G$ را بدون دور کند؟

نمونۀ بهینه‌سازی، مجموعۀ کمینۀ گره‌های بازخورد، کمترین شماری از گره‌ها را می‌جوید که با برداشتنشان گراف بدون دور می‌گردد. گراف برون‌داد جنگل است. می‌توان نشان داد که یافتن جنگل بیشینه دوگانه‌ی‌ یافتن گره‌های بازخورد کمینه است: یافتن جنگل بیشینه هم‌ارز است با یافتن گره‌های بازخورد کمینه.

سختی NP

الگو:Harvtxt نشان دادکه مسئله مجموعه گره بازخورد برای گراف‌های جهت دار، NP-کامل است.مسئله NP-کامل روی گراف‌های جهت دار بادرجهٔ ورودی و خروجی 2، وروی گراف‌های جهت دار دو طرفه با درجه داخلی و خارجی 2 باقی می‌ماند.. کاهش کارپ همچنین کامل بودن NP مسئله مجموعه گره بازخورد را روی گراف‌های بدون جهت ذکر می‌کند،جایی که مسئله روی گراف‌هایی از بیشینه درجه 4 ،NP سخت باقی می‌ماند.مسئله مجموعه گره بازخورد می‌تواند در زمان چندجمله‌ای روی گراف‌هایی از حداکثر درجه 3 حل شود. توجه کنید مسئله پاک کردن یال ها برای ایجاد گراف بدون دور معادل است با پیدا کردن یک درخت پوشای کمینه،که می‌تواند در زمان چندجمله ای انجام شود.در تضاد بااین،مسئله پاک کردن یال‌ها از یک گراف جهت دار برای بدون دور کردنش،مسالع یال‌های بازخورد،NP-کامل است،الگو:Harvtxt را ببینید.

الگوریتم‌های دقیق

مسئله بهینه‌سازی NP متناظر با پیدا کردن یک مجموعه گره بازخورد کمینه می‌تواند در زمانO(1.7347ⁿ), حل شود،جایی که n تعداد گره‌ها گراف است.. این الگوریتم در واقع یک جنگل مشتق شده بیشینه را محاسبه می‌کند،و و قتی که جنگلی به دست آمد، مکمل آن مجموعه گره بازخورد کمینه است.تعداد مجموعه‌های گره بازخورد در یک گراف به وسیلهٔ O(1.8638ⁿ). محدود می‌شود.مسئله گره بازخورد جهت دار هنوز می‌تواند در زمان O*(1.9977ⁿ), حل شود،جایی که  n تعداد گره‌ها در گراف جهت دار داده شده‌است.. نسخه پارامتری شده از مسائل جهت دار و بدون جهت ،هر دو غیر بغرنج باپارامتر ثابت هستند.

تخمین

مسئله APX-کامل است،که مستقیماً به دنبال کامل بودن APX از مسئله پوشش گره می‌آید و وجود یک حفظ تقریبی کاهش L از مسئله پوشش گره که برای آن می‌آید. معروفترین تخمین روی گراف‌های بدون جهت به وسیلهٔ یک عامل دو است.

کران‌ها

مطابق با نظریه Erdős–Pósa اندازه مجموعه گره بازخورد کمینه در داخل یک عامل لگاریتمی از حداکثر تعداد گره‌ها غیرمرتبط دورها در گراف داده شده‌است.

کاربردها

در سیستم‌های عامل ،مجموعه گره بازخورد نقشی برجسته در مطالعه بازیابی بن بست بازی می‌کند.در به انتظار نشستن برای گراف از یک سیستم عامل،هردور جهت دار متناظر با یک موقعیت بن بست است.به منظور حل کردن همهٔ بن بست ها،بعضی از فرایندهای مسدود شده باید کنارگذاشته شوند.یک مجموعه گره بازخورد در این گراف متناظر است با یک حداقل تعداد از فرایندهایی که احتیاج به کنارگذاشته شدن داردالگو:Harv. علاوه براین،مسئله مجموعه گره بازخورد،کاربردهای فراوانی درطراحی چیپ وی‌ال‌اس‌آی (cf. الگو:Harvtxt) و مونتاژژنوم دارد.

مقاله‌های پژوهشی

• [۱]
• Ann Becker, Reuven Bar-Yehuda, Dan Geiger: Randomized Algorithms for the Loop Cutset Problem. J. Artif. Intell. Res. (JAIR) 12: 219-234 (2000)
• الگو:Citation
• الگو:Citationالگو:پیوند مرده
• 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 O'Sullivan, Igor Razgon: A fixed-parameter algorithm for the directed feedback vertex set problem. J. ACM 55(5): (2008)
• الگو:Citation
• الگو:Citation
• الگو:Citation
• الگو:Citation A1.1: GT7, pg.191.
• الگو:Cite
• 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 (author's version (pdf)الگو:پیوند مرده, preliminary full version (pdf)الگو:پیوند مرده).

کتاب‌ها و مقاله‌ها آموزشی

• 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. author's version (pdf)
• الگو:Citation