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

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

تعریف

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

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

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

سختی NP

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

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

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

تخمین

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

کران‌ها

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

کاربردها

در سیستم‌های عامل ،مجموعه گره بازخورد نقشی برجسته در مطالعه بازیابی بن بست بازی می‌کند.در به انتظار نشستن برای گراف از یک سیستم عامل،هردور جهت دار متناظر با یک موقعیت بن بست است.به منظور حل کردن همهٔ بن بست ها،بعضی از فرایندهای مسدود شده باید کنارگذاشته شوند.یک مجموعه گره بازخورد در این گراف متناظر است با یک حداقل تعداد از فرایندهایی که احتیاج به کنارگذاشته شدن دارد(Silberschatz & Galvin 2008). علاوه براین،مسئله مجموعه گره بازخورد،کاربردهای فراوانی درطراحی چیپ وی‌ال‌اس‌آی (cf. (Festa، Pardalos و Resende 2000)) و مونتاژژنوم دارد.

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

• [۱]
• Ann Becker, Reuven Bar-Yehuda, Dan Geiger: Randomized Algorithms for the Loop Cutset Problem. J. Artif. Intell. Res. (JAIR) 12: 219-234 (2000)
• Becker, Ann; Geiger, Dan (1996), "Optimization of Pearl's Method of Conditioning and Greedy-Like Approximation Algorithms for the Vertex Feedback Set Problem.", Artif. Intell., 83 (1): 167–188, doi:10.1016/0004-3702(95)00004-6
• Cao, Yixin; Chen, Jianer; Liu, Yang (2010), Kaplan, Haim (ed.), "SWAT 2010", LNCS, 6139: 93–104, doi:10.1007/978-3-642-13731-0 {{citation}}: |contribution= ignored (help)
• 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)
• Dinur, Irit; Safra, Samuel (2005), "On the hardness of approximating minimum vertex cover" (PDF), Annals of Mathematics, 162 (1): 439–485, doi:10.4007/annals.2005.162.439, archived from the original (PDF) on 20 September 2009, retrieved 2010-03-05.
• Fomin, Fedor V.; Gaspers, Serge; Pyatkin, Artem; Razgon, Igor (2008), "On the Minimum Feedback Vertex Set Problem: Exact and Enumeration Algorithms.", Algorithmica, 52 (2): 293–307, doi:10.1007/s00453-007-9152-0
• Fomin, Fedor V.; Villanger, Yngve (2010), "Finding Induced Subgraphs via Minimal Triangulations.", Proc. of STACS 2010, pp. 383–394, doi:10.4230/LIPIcs.STACS.2010.2470
• Michael R. Garey and David S. Johnson (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, ISBN 0-7167-1045-5 A1.1: GT7, pg.191.
• Karp, Richard M. (1972), "Reducibility Among Combinatorial Problems", Complexity of Computer Computations, Proc. Sympos. IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y.. New York: Plenum (PDF), pp. 85–103, archived from the original (PDF) on 29 June 2011, retrieved 12 July 2012
• 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)
• Silberschatz, Abraham; Galvin, Peter Baer; Gagne, Greg (2008), Operating System Concepts (8th ed.), John Wiley & Sons. Inc, ISBN 978-0-470-12872-5