ในสาขา วิชา คณิตศาสตร์ทฤษฎีกราฟเซตจุดยอดป้อนกลับ (FVS) ของกราฟคือเซตของจุดยอดที่เมื่อลบออกแล้ว กราฟจะไม่มีวัฏจักร ("การลบ" หมายถึงการลบจุดยอดและขอบทั้งหมดที่อยู่ติดกับจุดยอดนั้น) หรือกล่าวอีกนัยหนึ่งคือ แต่ละ FVS จะมีจุดยอดอย่างน้อยหนึ่งจุดของวัฏจักรใดๆ ในกราฟจำนวนเซตจุดยอดป้อนกลับของกราฟคือขนาดของ FVS ที่เล็กที่สุด การหาว่ามีเซตจุดยอดป้อนกลับที่มีขนาดไม่เกิน k หรือไม่นั้นเป็น ปัญหา NP-completeซึ่งเป็นหนึ่งในปัญหาแรกๆ ที่ถูกพิสูจน์ว่าเป็น NP-complete ปัญหานี้มีการประยุกต์ใช้กันอย่างกว้างขวางในระบบปฏิบัติการระบบฐานข้อมูลและการออกแบบชิป VLSI

ปัญหาการตัดสินใจของ FVS มีดังต่อไปนี้:

ตัวอย่าง: กราฟ (แบบไม่มีทิศทางหรือมีทิศทาง) และจำนวนเต็มบวก${\displaystyle G=(V,E)}$${\displaystyle k}$

คำถาม: มีเซตย่อยใดบ้างที่มีคุณสมบัติว่า เมื่อลบจุดยอดทั้งหมดของ และขอบที่อยู่ติดกันออกจาก แล้วเซตที่เหลือจะไม่มีวัฏจักร ?${\displaystyle X\subseteq V}$${\displaystyle |X|\leq k}$${\displaystyle X}$${\displaystyle G}$

กราฟที่เหลืออยู่หลังจากลบออกจากกราฟจะเป็นป่า เหนี่ยวนำ (หรือกราฟแบบมีทิศทางที่ไม่มีวงจรเหนี่ยวนำในกรณีของกราฟแบบมีทิศทาง ) ดังนั้น การหาค่า FVS ต่ำสุดในกราฟจึงเทียบเท่ากับการหาป่าเหนี่ยวนำสูงสุด (หรือกราฟแบบมีทิศทางที่ไม่มีวงจรเหนี่ยวนำสูงสุดในกรณีของกราฟแบบมีทิศทาง ) ${\displaystyle G[V\setminus X]}$${\displaystyle X}$${\displaystyle G}$

Karp (1972)แสดงให้เห็นว่าการค้นหาเซตจุดยอดป้อนกลับที่มีขนาดในกราฟทิศทางเป็นปัญหา NP-completeปัญหายังคงเป็น NP-complete บนกราฟทิศทางที่มีดีกรีขาเข้าและดีกรีขาออกสูงสุดสอง และบนกราฟระนาบทิศทางที่มีดีกรีขาเข้าและดีกรีขาออกสูงสุดสาม^{[ 1 ]}${\displaystyle \leq k}$

การลดของ Karp ยังบ่งชี้ถึงความสมบูรณ์ของ NP ของปัญหาเซตจุดยอดป้อนกลับบน กราฟ ที่ไม่มีทิศทางซึ่งปัญหายังคงเป็น NP-complete บนกราฟที่มีดีกรีสูงสุดสี่ ปัญหาเซตจุดยอดป้อนกลับสามารถแก้ไขได้ในเวลาพหุนามบนกราฟที่มีดีกรีสูงสุดไม่เกินสาม โดยใช้อัลกอริทึมที่อิงตาม ปัญหาความเท่าเทียมกัน ของเมทริกซ์^{[ 2 ]}

ปัญหาการหาค่าเหมาะสมที่สุด NPที่เกี่ยวข้องกับการหาขนาดของเซตจุดยอดป้อนกลับขั้นต่ำสามารถแก้ไขได้ในเวลา O (1.7347 ⁿ ) โดยที่ nคือจำนวนจุดยอดในกราฟ^{[ 3 ]}อัลกอริทึมนี้คำนวณป่าเหนี่ยวนำสูงสุด และเมื่อได้ป่าดังกล่าวแล้ว ส่วนเติมเต็มของมันคือเซตจุดยอดป้อนกลับขั้นต่ำ จำนวนเซตจุดยอดป้อนกลับขั้นต่ำในกราฟมีขอบเขตจำกัดที่O (1.8638 ⁿ ) ^{[ 4 ]}ปัญหาเซตจุดยอดป้อนกลับแบบมีทิศทางยังคงสามารถแก้ไขได้ในเวลาO* (1.9977 ⁿ ) โดยที่nคือจำนวนจุดยอดในกราฟแบบมีทิศทางที่กำหนด^{[ 5 ]} เวอร์ชันพารามิเตอร์ของปัญหาแบบมีทิศทางและไม่มีทิศทาง สามารถแก้ไขได้ด้วยพารามิเตอร์คงที่ทั้งคู่^{[ 6 ]}

ในกราฟแบบไม่มีทิศทางที่มี ดีกรีสูงสุดสาม ปัญหาเซตจุดยอดป้อนกลับสามารถแก้ไขได้ในเวลาพหุนามโดยการแปลงให้เป็นอินสแตนซ์ของปัญหาความเท่าเทียมกันของเมทริกซ์สำหรับเมทริกซ์เชิงเส้น^{[ 7 ]}

กรณีพิเศษของการค้นหาจุดยอดป้อนกลับทั้งหมดในกราฟทิศทาง (จุดยอดที่อยู่บนวงจรทิศทางทุกวง) สามารถแก้ไขได้ในเวลาเชิงเส้นโดยใช้อัลกอริทึมแบบ DFS โดย Garey และ Tarjan ^{[ 8 ]}

ปัญหาที่ไม่มีทิศทางนี้เป็นปัญหาAPX-completeซึ่งเป็นผลมาจากข้อเท็จจริงดังต่อไปนี้

• ความสมบูรณ์ของ APX ของปัญหาการครอบคลุมจุดยอด ; ^{[ 9 ]}
• การมีอยู่ของการประมาณค่าที่รักษาการลดรูป Lจากปัญหาปกคลุมจุดยอดไปสู่ปัญหานั้น
• อัลกอริทึมการประมาณค่าคงที่ที่มีอยู่^{[ 10 ]}

อัลกอริทึมการประมาณค่าที่เป็นที่รู้จักดีที่สุดบนกราฟแบบไม่มีทิศทางคือด้วยปัจจัยสองเท่า^{[ 11 ]}

ในทางตรงกันข้าม เวอร์ชันที่มีทิศทางของปัญหาดูเหมือนจะยากต่อการประมาณค่ามากยิ่งขึ้น ภายใต้สมมติฐานเกมที่ไม่ซ้ำกัน ซึ่งเป็น สมมติฐานความยากในการคำนวณที่ยังไม่ได้รับการพิสูจน์แต่ใช้กันทั่วไปการประมาณค่าปัญหาให้อยู่ภายในปัจจัยคงที่ใดๆ ในเวลาพหุนามนั้นถือเป็นปัญหา NP-hard ผลลัพธ์ความยากเดียวกันนี้ได้รับการพิสูจน์แล้วสำหรับปัญหาเซตส่วนโค้งป้อนกลับ ที่เกี่ยวข้องอย่างใกล้ชิด ^{[ 12 ]}แต่เนื่องจากปัญหาเซตส่วนโค้งป้อนกลับและปัญหาเซตจุดยอดป้อนกลับในกราฟที่มีทิศทางสามารถลดรูปให้เหลือกันและกันได้ในขณะที่ยังคงรักษาขนาดของคำตอบไว้^{[ 13 ]}จึงใช้ได้กับปัญหาหลังด้วยเช่นกัน

ตามทฤษฎีบท Erdős–Pósaขนาดของเซตจุดยอดป้อนกลับขั้นต่ำจะอยู่ภายในปัจจัยลอการิทึมของจำนวนวงจรที่ไม่ทับซ้อนกันสูงสุดของจุดยอดในกราฟที่กำหนด^{[ 14 ]}

• แทนที่จะพิจารณาจุดยอด เราอาจพิจารณาเซตของขอบป้อนกลับซึ่งเป็นเซตของขอบในกราฟแบบไม่มีทิศทาง ที่การลบขอบเหล่านี้จะทำให้กราฟไม่มีวงจร ขนาดของเซตขอบป้อนกลับที่เล็กที่สุดในกราฟเรียกว่าอันดับวงจรของกราฟ แตกต่างจากจำนวน FVS อันดับวงจรสามารถคำนวณได้ง่าย คือโดยที่ C คือเซตของส่วนประกอบที่เชื่อมต่อกันของกราฟ ปัญหาของการหาเซตขอบป้อนกลับที่เล็กที่สุดเทียบเท่ากับการหาป่าแผ่ขยายซึ่งสามารถทำได้ในเวลาพหุนาม${\displaystyle |E|-|V|+|C|}$
• แนวคิดที่คล้ายคลึงกันในกราฟแบบมีทิศทางคือเซตส่วนโค้งป้อนกลับ (FAS) ซึ่งเป็นเซตของส่วนโค้งแบบมีทิศทางที่การลบออกจะทำให้กราฟไม่มีวงจร การหา FAS ที่เล็กที่สุดเป็นปัญหา NP-hard ^{[ 10 ]}

• ในระบบปฏิบัติการชุดจุดยอดป้อนกลับมีบทบาทสำคัญในการศึกษา การกู้คืน ภาวะติดตายในกราฟรอของระบบปฏิบัติการ วงจรทิศทางแต่ละวงสอดคล้องกับสถานการณ์ติดตาย เพื่อแก้ไขภาวะติดตายทั้งหมด จำเป็นต้องยกเลิกกระบวนการที่ถูกบล็อกบางส่วน ชุดจุดยอดป้อนกลับขั้นต่ำในกราฟนี้สอดคล้องกับจำนวนกระบวนการขั้นต่ำที่ต้องยกเลิก^{[ 15 ]}
• ปัญหาชุดจุดยอดป้อนกลับมีการประยุกต์ใช้ในการออกแบบชิปVLSI ^{[ 16 ]}
• การประยุกต์ใช้อีกประการหนึ่งคือในทฤษฎีความซับซ้อน ปัญหาการคำนวณบางอย่างบนกราฟโดยทั่วไปเป็น NP-hard แต่สามารถแก้ไขได้ในเวลาพหุนามสำหรับกราฟที่มีจำนวน FVS ที่จำกัด ตัวอย่างบางส่วนได้แก่ กราฟไอโซมอร์ฟิซึม^{[ 17 ]}และปัญหาการกำหนดค่าเส้นทางใหม่^{[ 18 ]}