مجموعه راس پس خورد

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

تعریف

مساله تصمیم گیری به این صورت است:

نمونه:یک گراف(جهت دار یا بدون جهت)$G = (V, E)$ و یک عدد صحیح مثبت $k$.

سوال: آیا یک زیرمجموعه $X \subseteq V$ با $|X| \leq k$ وجوددارد چنان چه $G$ بارئوس پاک شده ای از $X$بدون دور باشد؟

گراف $G[V \setminus X]$ که بعد از برداشتن $X$از $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), On Feedback Vertex Set: New Measure and New Structures, in Kaplan, Haim, "SWAT 2010", LNCS 6139: 93–104, DOI:10.1007/978-3-642-13731-0, http://www.springerlink.com/content/f3726432823626n7/ 
• 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", Annals of Mathematics 162 (1): 439–485, DOI:10.4007/annals.2005.162.439, http://www.cs.huji.ac.il/~dinuri/mypapers/vc.pdf, 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, pp. 85–103, http://www.cs.berkeley.edu/~luca/cs172/karp.pdf 
• 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