ในทฤษฎีกราฟตัวบล็อกที่ไม่ใช่จุดยอด (nonblocker)คือเซตย่อยของจุดยอดในกราฟแบบไม่มีทิศทางซึ่งจุดยอดทั้งหมดอยู่ติดกับจุดยอดที่อยู่นอกเซตย่อยนั้น เทียบเท่ากับตัวบล็อกที่ไม่ใช่จุดยอด (nonblocker) คือส่วนเติมเต็มของเซตที่ครอบคลุม^{[ 1 ]}

ปัญหาการคำนวณของการค้นหาตัวบล็อกที่ไม่ใช่บล็อกที่ใหญ่ที่สุดในกราฟได้รับการกำหนดโดยPapadimitriou & Yannakakis (1991)ซึ่งสังเกตว่ามันอยู่ในกลุ่มMaxSNP ^{[ 2 ]} แม้ว่าการคำนวณเซตที่ครอบคลุมจะไม่สามารถจัดการได้ด้วยพารามิเตอร์คงที่ภายใต้สมมติฐานมาตรฐาน แต่ปัญหาเสริมของการค้นหาตัวบล็อกที่ไม่ใช่บล็อกที่มีขนาดที่กำหนดนั้นสามารถจัดการได้ด้วยพารามิเตอร์คงที่^{[ 1 ]}

ในกราฟที่ไม่มีจุดยอดโดดเดี่ยวจุดยอดที่ไม่ปิดกั้นสูงสุดทุกจุด (จุดยอดที่ไม่สามารถเพิ่มจุดยอดเข้าไปได้อีก) ถือเป็นเซตที่ครอบคลุม^{[ 3 ]}

วิธีหนึ่งในการสร้างอัลกอริทึมที่จัดการได้สำหรับปัญหา nonblocker ที่มีพารามิเตอร์คงที่คือการใช้kernelizationซึ่งเป็นหลักการออกแบบอัลกอริทึมที่ใช้อัลกอริทึมแบบ polynomial-time เพื่อลดอินสแตนซ์ปัญหาขนาดใหญ่ให้เป็นอินสแตนซ์ที่เทียบเท่ากันซึ่งมีขนาดจำกัดโดยฟังก์ชันของพารามิเตอร์ สำหรับปัญหา nonblocker อินพุตของปัญหาประกอบด้วยกราฟและพารามิเตอร์และเป้าหมายคือการพิจารณาว่ามี nonblocker ที่มีจุดยอดตั้งแต่ 1 ขึ้นไปหรือไม่^{[ 1 ]}${\displaystyle G}$${\displaystyle k}$${\displaystyle G}$${\displaystyle k}$

ปัญหานี้มีเคอร์เนลไลเซชันที่ง่ายซึ่งลดทอนให้เป็นปัญหาที่เทียบเท่ากันโดยมีจุดยอดอย่างมากที่สุด ขั้นแรก ให้ลบจุดยอดที่แยกเดี่ยวทั้งหมดออกจากเนื่องจากจุดยอดเหล่านั้นไม่สามารถเป็นส่วนหนึ่งของ nonblocker ใดๆ ได้ เมื่อทำเช่นนี้แล้ว กราฟที่เหลือจะต้องมี nonblocker ที่รวมจุดยอดอย่างน้อยครึ่งหนึ่ง ตัวอย่างเช่น หากระบายสีต้นไม้แผ่ขยายของ กราฟด้วย 2 สีแต่ละคลาสสีจะเป็น nonblocker และหนึ่งในสองคลาสสีจะรวมจุดยอดอย่างน้อยครึ่งหนึ่ง ดังนั้น หากกราฟที่ลบจุดยอดที่แยกเดี่ยวออกแล้วยังคงมีจุดยอดตั้งแต่ หรือมากกว่า ปัญหาจะสามารถแก้ไขได้ทันที มิฉะนั้น กราฟที่เหลือจะเป็นเคอร์เนลที่มีจุดยอด อย่างมากที่สุด ^{[ 1 ]}${\displaystyle 2k}$${\displaystyle G}$${\displaystyle 2k}$${\displaystyle 2k}$

Dehne และคณะได้ปรับปรุงสิ่งนี้ให้เป็นเคอร์เนลที่มีขนาดไม่เกินวิธีการของพวกเขาเกี่ยวข้องกับการรวมคู่ของเพื่อนบ้านของจุดยอดที่มีดีกรีหนึ่งจนกว่าจุดยอดดังกล่าวทั้งหมดจะมีเพื่อนบ้านเพียงจุดเดียว และลบจุดยอดที่มีดีกรีหนึ่งทั้งหมดออกเหลือไว้เพียงจุดเดียว ทำให้เหลืออินสแตนซ์ที่เทียบเท่ากันซึ่งมีจุดยอดที่มีดีกรีหนึ่งเพียงจุดเดียว จากนั้น พวกเขาแสดงให้เห็นว่า (ยกเว้นค่าเล็กๆ ของซึ่งสามารถจัดการแยกต่างหากได้) อินสแตนซ์นี้จะต้องมีขนาดเล็กกว่าขอบเขตขนาดของเคอร์เนลหรือมีตัวบล็อกจุดยอด^{[ 1 ]}${\displaystyle {\tfrac {5}{3}}k+3}$${\displaystyle k}$${\displaystyle k}$

เมื่อได้เคอร์เนลขนาดเล็กแล้ว ปัญหาของ nonblocker สามารถแก้ไขได้ในเวลาที่จัดการได้ด้วยพารามิเตอร์คงที่โดยการใช้ อัลกอริธึม การค้นหาแบบ brute-forceกับเคอร์เนล การใช้ขอบเขตเวลาที่เร็วกว่า (แต่ยังคงเป็นเลขชี้กำลัง) นำไปสู่ขอบเขตเวลาสำหรับปัญหา nonblocker ในรูปแบบแม้แต่อัลกอริธึมที่เร็วกว่าก็เป็นไปได้สำหรับกราฟบางประเภทพิเศษ^{[ 1 ]}${\displaystyle O(2.5154^{k}+n)}$

• เซ็ตที่โดดเด่น - ส่วนเติมเต็มของเซ็ตที่ไม่เน้นการบล็อก