برداشت کلی شما از مقاله‌ی داده‌شده چیست؟

مقاله: نمونۀ تصمیمی مجموعه گره‌های بازخورد: درون‌داد: گراف و عدد درست. برون‌داد: آیا برداشتن گره از می‌تواند گراف را بدون دور کند؟ نمونۀ بهینه‌سازی، مجموعۀ کمینۀ گره‌های بازخورد، کمترین شماری از گره‌ها را می‌جوید که با برداشتنشان گراف بدون دور می‌گردد. گراف برون‌داد جنگل است. می‌توان نشان داد که یافتن جنگل بیشینه دوگانه‌ی یافتن گره‌های بازخورد کمینه است: یافتن جنگل بیشینه هم‌ارز است با یافتن گره‌های بازخورد کمینه. karp (۱۹۷۲) نشان دادکه مسئله مجموعه گره بازخورد برای گراف‌های جهت‌دار، np-کامل است. مسئله np-کامل روی گراف‌های جهت‌دار بادرجه ورودی و خروجی ۲، وروی گراف‌های جهت‌دار دو طرفه با درجه داخلی و خارجی ۲ باقی می‌ماند.. کاهش کارپ همچنین کامل بودن np مسئله مجموعه گره بازخورد را روی گراف‌های بدون جهت ذکر می‌کند، جایی که مسئله روی گراف‌هایی از بیشینه درجه ۴، np سخت باقی می‌ماند. مسئله مجموعه گره بازخورد می‌تواند در زمان چندجمله‌ای روی گراف‌هایی از حداکثر درجه ۳ حل شود. توجه کنید مسئله پاک کردن یال‌ها برای ایجاد گراف بدون دور معادل است با پیدا کردن یک درخت پوشای کمینه، که می‌تواند در زمان چندجمله‌ای انجام شود. در تضاد بااین، مسئله پاک کردن یال‌ها از یک گراف جهت‌دار برای بدون دور کردنش، مسالع یال‌های بازخورد، np-کامل است، karp (۱۹۷۲) را ببینید. مسئله بهینه‌سازی np متناظر با پیدا کردن یک مجموعه گره بازخورد کمینه می‌تواند در زمانo (۱ ٫ ۷۳۴۷ n) , حل شود، جایی که n تعداد گره‌ها گراف است.. این الگوریتم در واقع یک جنگل مشتق شده بیشینه را محاسبه می‌کند، و و قتی که جنگلی به دست آمد، مکمل آن مجموعه گره بازخورد کمینه است. تعداد مجموعه‌های گره بازخورد در یک گراف به وسیله o (۱ ٫ ۸۶۳۸ n). محدود می‌شود. مسئله گره بازخورد جهت‌دار هنوز می‌تواند در زمان o* (۱ ٫ ۹۹۷۷ n) , حل شود، جایی که n تعداد گره‌ها در گراف جهت‌دار داده شده‌است.. نسخه پارامتری شده از مسائل جهت‌دار و بدون جهت، هر دو غیر بغرنج باپارامتر ثابت هستند. مسئله apx-کامل است، که مستقیما به دنبال کامل بودن apx از مسئله پوشش گره می‌آید و وجود یک حفظ تقریبی کاهش l از مسئله پوشش گره که برای آن می‌آید. معروفترین تخمین روی گراف‌های بدون جهت به وسیله یک عامل دو است. مطابق با نظریه erdős–pósa اندازه مجموعه گره بازخورد کمینه در داخل یک عامل …
برداشت:
در نظریه گراف ، مجموعه گره‌های بازخورد مجموعه‌ای از گره‌های گرافی است که برداشتنشان گراف را بدون دور می‌کند . به سخنی دیگر ، مجموعۀ بازخورد دست‌کم گره‌ای را از هر دور در گراف دارد . از دید نظریه پیچیدگی محاسباتی ، مجموعه گره بازخورد ان‌پی کامل است . مجموعه گره بازخورد یکی از ۲۱ پرسشی است که کارپ پیچیدگی رایانشی‌شان را بررسی کرده‌است . مجموعه گره‌های بازخورد کاربردی گسترده در سامانۀ عامل ، پایگاه داده و زمینۀ تراشه‌های وی‌ال‌اس‌آی دارد .