پوشش گره‌ای
پوشش گره‌ای برای یک گراف زیرمجموعه‌ای از گره‌هاست که همهٔ یال‌های این گراف را می‌پوشاند. در این جا پوشش یک یال یعنی آن که دست کم یکی از گره‌های دو سر یال در این زیرمجموعه باشد. اندازهٔ پوششی گره‌ای برابر است با شمار گره‌های درون این مجموعه. برای نمونه، در شکل ۱ formula_1 دارای پوشش گره formula_2 به اندازهٔ ۲ است.
پرسمان پوشش گره‌ای کمینه به یافتن پوششی گره‌ای می‌پردازد که کم‌ترین شمار گره‌ها را دربرداشته باشد. این پرسمان ان‌پی کامل است، از این روی رایانش چنین زیرمجموعه‌ای دشوار است.
برای گرافی بی‌سو مانند formula_3، زیرمجموعه‌ای formula_4 پوشش گره‌ای است اگر برای هر یال formula_5 یا گره formula_6 یا گرهٔ formula_7 یا formula_8 باشد. دو پوشش گره‌ای با رنگ قرمز در شکل‌های زیر نمایانیده شده‌اند.
اندازهٔ پوششی گره‌ای مانند formula_9 برابر است با شمار گره‌های این زیرمجموعه که با formula_10 نمایش داده می‌شود. پوشش گره‌ای کمینه پوششی است که دارای کم‌ترین گره‌ها باشد. گره‌های سرخ در در دو شکل زیر پوشش گره‌ای کمینه را برای نمونه‌های بالا می‌نمایانند.پرسمان پوشش گره‌ای کمینه پرسمانی بهینه‌سازی است که به یافتن پوششی گره با کمترین اندازه برای یک گراف می‌پردازد. اگر گره‌ها وزن‌دار باشند، پوشش گره‌ای وزن‌دار کمینه زیرمجموعه‌ای از گره‌هاست که کمترین وزن را روی-هم-رفته داشته باشند.
پرسمان پوشش گره‌ای پرسمانی تصمیم‌گیری است: آیا پوشش گره‌ای با اندازه‌ای دست بالا formula_13 در گرافی هست.
پرسمان پوشش گرهٔ ان‌پی کامل و یکی از پرسمان‌های ۲۱ پرسمان ان‌پی-کامل کارپ است.
برای برنامه‌نویسی درست، اگر هر گرهٔ formula_14 در گراف formula_15 وزن formula_16 دربرداشته باشد، پرسمان پوشش گره‌ای مانند برنامهٔ درست (integer program) زیر نوشته می‌شود:
formula_17
بنداشت‌ها:
formula_18
formula_19
گافِ دُرُست (integral gap) برای این برنامه، ۲ است؛ بنابراین، واهلش این برنامه تقریبی با کروند (فاکتور)-۲ برای پرسمان پوشش گره‌ای کمینه به دست خواهد داد. هم‌چنین، واهلش برنامهٔ درست بالا نیم-دُرُست (half integral) است؛ از این روی، در یک پاسخ بهین، هر درآیهٔ formula_20 ارزش formula_21 یا formula_22 یا formula_23 (optimal) خواهد داشت.
پرسمان پوشش گره‌ای ان‌پی کامل است. از این روی، الگوریتمی دقیق با زمانی بهینه برای این پرسمان نخواهیم داشت. ریچارد کارپ ان‌پی کامل بودن این پرسمان را با کاهش از پرسمان گروهک نشان داده است. پرسمان پوشش گره‌ای حتی برای گراف مکعبی و گراف مسطح با درجهٔ کم‌تر از ۳ ان‌پی کامل می‌ماند.
کونیگ نشان داده است که پوشش گره‌ای کمینه و جورسازی بیشینه در گرافی دوبخشی هم‌ارز هستند. از این روی می‌توان پاسخ بهین را در زمانی چندجمله‌ای به دست آورد.
هم‌چنین، پاسخ بهین را برای درخت‌ها می‌توان در زمانی چندجمله‌ای یافت.
البته در ادامه الگوریتم تقریب زیر را برای این مسئله بیان می‌داریم. الگوریتم، گراف بدون جهت formula_24 را به عنوان ورودی می‌گیرد و یک پوشش گرهٔ را برمی‌گرداند که تضمین می‌شود اندازه آن بیش از دو برابر پوشش گرهٔ بهینه نیست:
formula_25
formula_26
formula_27
formula_28
formula_29
formula_30
formula_31
formula_32
شکل ۲ عملکرد- formula_25 را تشریح می‌کند. متغیر formula_34 حاوی پوشش گرهٔ در حال ساخت است. خط ۱، formula_34 را برابر با مجموعه تهی قرار می‌دهد. خط ۲ ، formula_36 را برابر با کپی مجموعه یال formula_37 گراف قرار می‌دهد. حلقه در خطوط ۳ تا ۶ مکرراً یالformula_38 را از formula_36 انتخاب می‌کند، نقاط انتهای آن formula_40 و formula_41 را به formula_34 اضافه می‌کند، و تمام یال‌هایی را از formula_36 حذف می‌کند که توسط formula_40 یا formula_41 پوشش می‌شود. زمان اجرای الگوریتم formula_46 است که از لیست همجواری برای نمایش formula_36 استفاده می‌شود.