ในทฤษฎีกราฟกลุ่มจุดยอดที่ ประกอบด้วย จุดปลายอย่างน้อยหนึ่งจุดของทุกขอบ ของกราฟ (บางครั้งเรียกว่ากลุ่มจุดเชื่อมต่อ )

ในวิทยาการคอมพิวเตอร์ปัญหาการหาชุดคลุมจุดยอดขั้นต่ำเป็นปัญหาการหาค่าเหมาะสม ที่สุดแบบคลาสสิก มันเป็น ปัญหา NP-hardดังนั้นจึงไม่สามารถแก้ได้ด้วยอัลกอริทึมแบบใช้เวลาพหุนามหากP ≠ NP ยิ่งไปกว่านั้น การประมาณค่าก็ ยาก – ไม่สามารถประมาณค่าได้ถึงปัจจัยที่เล็กกว่า 2 หากสมมติฐานเกมที่ไม่ซ้ำกันเป็นจริง ในทางกลับกัน มันมีการประมาณค่าแบบง่ายๆ หลายวิธีด้วยปัจจัย 2 มันเป็นตัวอย่างทั่วไปของปัญหาการหาค่าเหมาะสมที่สุดแบบ NP-hard ที่มีอัลกอริทึมการประมาณค่า เวอร์ชันการตัดสินใจของมัน ปัญหา ชุดคลุมจุดยอดเป็นหนึ่งใน21 ปัญหา NP-complete ของ Karpและดังนั้นจึงเป็น ปัญหา NP-complete แบบคลาสสิก ในทฤษฎีความซับซ้อนของการคำนวณนอกจากนี้ ปัญหาชุดคลุมจุดยอดสามารถแก้ไขได้ด้วยพารามิเตอร์คงที่และเป็นปัญหาหลักในทฤษฎีความซับซ้อนแบบพารามิเตอร์

ปัญหาการครอบคลุมจุดยอดขั้นต่ำสามารถกำหนดได้เป็นโปรแกรมเชิงเส้นครึ่งปริพันธ์ ซึ่ง โปรแกรมเชิงเส้นคู่ขนานของ มันคือปัญหาการจับคู่สูงสุด

ปัญหาการคลุมจุดยอดได้รับการขยายไปสู่ไฮเปอร์กราฟแล้ว ดูได้ที่การคลุมจุดยอดในไฮเปอร์กราฟ

ในทางทฤษฎีแล้ว กลุ่มจุดยอดที่ปกคลุมกราฟแบบไม่มีทิศทางคือเซตย่อยของโดยที่นั่นคือ เป็นเซตของจุดยอดที่ทุกขอบมีจุดปลายอย่างน้อยหนึ่งจุดอยู่ในกลุ่มจุดยอดที่ปกคลุม นั้น เซตดังกล่าวเรียกว่าเซตที่ปกคลุมขอบของภาพด้านบนแสดงตัวอย่างกลุ่มจุดยอดที่ปกคลุมสองตัวอย่าง โดยบางกลุ่มจุดยอดถูกทำเครื่องหมายด้วยสีแดง ${\displaystyle V'}$${\displaystyle G=(V,E)}$${\displaystyle V}$${\displaystyle (uv\in E)\ลูกศรขวา (u\in V'\lor v\in V')}$${\displaystyle V'}$${\displaystyle V'}$${\displaystyle G}$${\displaystyle V'}$

การปกคลุมจุดยอดขั้นต่ำ (Minimum Vertex Cover)คือการปกคลุมจุดยอดที่มีขนาดเล็กที่สุดเท่าที่จะเป็นไปได้ ตัวเลขการปกคลุมจุดยอดคือขนาดของการปกคลุมจุดยอดขั้นต่ำ นั่นคือรูปด้านล่างแสดงตัวอย่างของการปกคลุมจุดยอดขั้นต่ำในกราฟก่อนหน้านี้ ${\displaystyle \tau }$${\displaystyle \tau =|V'|}$

• เซตของจุดยอดทั้งหมดเรียกว่าเวอร์เท็กซ์คัฟเวอร์ (vertex cover)
• จุดปลายของการจับคู่สูงสุด ใดๆ จะก่อให้เกิดกลุ่มจุดยอด (vertex cover)
• กราฟสองส่วนสมบูรณ์ มีชุดปกคลุมจุดยอดขั้นต่ำที่มีขนาดเท่ากับ${\displaystyle K_{m,n}}$${\displaystyle \tau (K_{m,n})=\min\{\,m,n\,\}}$

• เซตของจุดยอดจะเป็นเซตปกคลุมจุดยอดก็ต่อเมื่อเซตส่วนเติมเต็ม ของเซตนั้น เป็นเซตอิสระ
• ดังนั้น จำนวนจุดยอดของกราฟจึงเท่ากับจำนวนการครอบคลุมจุดยอดขั้นต่ำบวกกับขนาดของเซตอิสระสูงสุด^{[ 1 ]}

ปัญหาการหาชุดจุดยอดปกคลุมขั้นต่ำ (Minimum Vertex Cover Problem)คือปัญหาการหาค่าที่เหมาะสม ที่สุด (optimization problem ) ในการค้นหาชุดจุดยอดปกคลุมที่เล็กที่สุดในกราฟที่กำหนดให้

ตัวอย่าง: กราฟ${\displaystyle G}$

ผลลัพธ์: จำนวนที่เล็กที่สุดที่ทำให้มีกลุ่มจุดยอดปกคลุมที่มีขนาดเท่ากับ${\displaystyle k}$${\displaystyle G}$${\displaystyle k}$

หากระบุปัญหาในรูปแบบของปัญหาการตัดสินใจจะเรียกว่าปัญหาการครอบคลุมจุดยอด (vertex cover problem )

ตัวอย่าง: กราฟและจำนวนเต็มบวก${\displaystyle G}$${\displaystyle k}$

คำถาม: มีเวอร์เท็กซ์คัฟเวอร์ที่มีขนาดไม่เกินหรือไม่?${\displaystyle G}$${\displaystyle k}$

ปัญหา ทั้งสองนี้เทียบเท่ากันภายใต้การลดรูปในเวลาพหุนามโดยใช้การค้นหาแบบไบนารีปัญหาการครอบคลุมจุดยอดเป็น ปัญหา NP-complete : มันเป็นหนึ่งใน21 ปัญหา NP-complete ของคาร์ปมักถูกใช้ในทฤษฎีความซับซ้อนของการคำนวณเป็นจุดเริ่มต้นสำหรับการพิสูจน์ ความยากแบบ NP

สมมติว่าจุดยอดแต่ละจุดมีค่าใช้จ่ายที่เกี่ยวข้องเท่ากับปัญหาการครอบคลุมจุดยอดขั้นต่ำ (แบบถ่วงน้ำหนัก) สามารถกำหนดเป็นโปรแกรมเชิงเส้นจำนวนเต็ม (ILP) ดังต่อไปนี้ ^{[ 2 ]}${\displaystyle c(v)\geq 0}$

ลดให้น้อยที่สุด	${\displaystyle \textstyle \sum _{v\in V}c(v)x_{v}}$			(ลดต้นทุนรวมให้เหลือน้อยที่สุด)
ขึ้นอยู่กับ	${\displaystyle x_{u}+x_{v}\geq 1}$	สำหรับทุกคน${\displaystyle \{u,v\}\in E}$		(ปิดขอบทุกด้านของกราฟ)
	${\displaystyle x_{v}\in \{0,1\}}$	สำหรับทุกคน ${\displaystyle v\in V}$		(จุดยอดทุกจุดจะอยู่ในกลุ่มจุดยอดที่ถูกปกคลุมไว้หรือไม่ก็ได้)

ปัญหาการเขียนโปรแกรมเชิงเส้นจำนวนเต็ม (ILP) นี้จัดอยู่ในกลุ่ม ILP ทั่วไปสำหรับปัญหาการครอบคลุม ช่องว่าง ความสมบูรณ์ของ ILP นี้คือดังนั้นการผ่อนคลาย (โดยอนุญาตให้ตัวแปรแต่ละตัวอยู่ในช่วงตั้งแต่ 0 ถึง 1 แทนที่จะกำหนดให้ตัวแปรต้องเป็น 0 หรือ 1 เท่านั้น) ทำให้ได้อัลกอริทึมการประมาณ ค่าตัวประกอบ สำหรับปัญหาการครอบคลุมจุดยอดขั้นต่ำ ยิ่งไปกว่านั้น การผ่อนคลายการเขียนโปรแกรมเชิงเส้นของ ILP นั้นเป็นแบบครึ่งจำนวนเต็มนั่นคือ มีคำตอบที่เหมาะสมที่สุดซึ่งแต่ละรายการเป็น 0, 1/2 หรือ 1 สามารถหาการครอบคลุมจุดยอดโดยประมาณ 2 เท่าได้จากคำตอบเศษส่วนนี้โดยการเลือกเซตย่อยของจุดยอดที่มีตัวแปรไม่เป็นศูนย์ ${\displaystyle 2}$${\displaystyle 2}$${\displaystyle x_{v}}$

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

สำหรับกราฟสองส่วนความเท่าเทียมกันระหว่างการครอบคลุมจุดยอดและการจับคู่สูงสุดที่อธิบายโดยทฤษฎีบทของ Kőnigทำให้สามารถแก้ปัญหาการครอบคลุมจุดยอดของกราฟสองส่วนได้ในเวลาพหุนาม

สำหรับกราฟต้นไม้อัลกอริทึมจะค้นหาชุดคลุมจุดยอดที่เล็กที่สุดได้ในเวลาพหุนาม โดยการค้นหาใบแรกในต้นไม้และเพิ่มผู้ปกครองของใบนั้นลงในชุดคลุมจุดยอดที่เล็กที่สุด จากนั้นลบใบและผู้ปกครอง รวมถึงขอบทั้งหมดที่เกี่ยวข้อง และทำซ้ำไปเรื่อยๆ จนกว่าจะไม่มีขอบเหลืออยู่ในต้นไม้

อั ลกอริทึม การค้นหาแบบละเอียดสามารถแก้ปัญหาได้ในเวลา 2 ^k n ^{O (1)}โดยที่kคือขนาดของการครอบคลุมจุดยอด ดังนั้นการครอบคลุมจุดยอดจึงสามารถจัดการได้ด้วยพารามิเตอร์คงที่และหากเราสนใจเฉพาะk ขนาดเล็ก เราสามารถแก้ปัญหาได้ในเวลาพหุนามเทคนิคอัลกอริทึมหนึ่งที่ใช้ได้ผลในที่นี้เรียกว่าอัลกอริทึมต้นไม้ค้นหาแบบจำกัดและแนวคิดของมันคือการเลือกจุดยอดบางจุดซ้ำๆ และแยกสาขาแบบเรียกซ้ำ โดยมีสองกรณีในแต่ละขั้นตอน: วางจุดยอดปัจจุบันหรือเพื่อนบ้านทั้งหมดลงในจุดยอดที่ครอบคลุม อัลกอริทึมสำหรับการแก้ปัญหาการครอบคลุมจุดยอดที่บรรลุการพึ่งพาแบบเชิงเส้นกำกับที่ดีที่สุดกับพารามิเตอร์จะทำงานในเวลา[ ^{5 ] ค่า} klam ของขอบเขตเวลานี้ (การประมาณค่าพารามิเตอร์ที่ใหญ่ที่สุดที่สามารถแก้ไขได้ในเวลาที่เหมาะสม) อยู่ที่ประมาณ 190 นั่นคือ เว้นแต่จะพบการปรับปรุงอัลกอริทึมเพิ่มเติม อัลกอริทึมนี้เหมาะสำหรับกรณีที่มีจำนวนจุดยอดที่ครอบคลุม 190 หรือน้อยกว่าเท่านั้น ภายใต้สมมติฐานเชิงทฤษฎีความซับซ้อนที่สมเหตุสมผล กล่าวคือสมมติฐานเวลาแบบเลขชี้กำลังเวลาในการทำงานไม่สามารถปรับปรุงให้เป็น 2 ^{o ( k )} ได้ แม้ว่าจะเป็นก็ตาม ${\displaystyle O(1.2738^{k}+(k\cdot n))}$${\displaystyle n}$${\displaystyle O(k)}$

อย่างไรก็ตาม สำหรับกราฟระนาบและโดยทั่วไปแล้ว สำหรับกราฟที่ไม่รวมกราฟคงที่บางกราฟเป็นไมเนอร์สามารถหา การครอบคลุมจุดยอดที่มีขนาด k ได้ในเวลา นั่นคือ ปัญหาสามารถจัดการได้ในเวลาต่ำกว่าเลขชี้กำลังด้วยพารามิเตอร์คงที่^{[ 6 ]}อัลกอริทึมนี้ถือว่าเหมาะสมที่สุดอีกครั้ง ในแง่ที่ว่า ภายใต้สมมติฐานเวลาเลขชี้กำลังไม่มีอัลกอริทึมใดที่สามารถแก้ปัญหาการครอบคลุมจุดยอดบนกราฟระนาบได้ในเวลา^{[ 7 ]}${\displaystyle 2^{O({\sqrt {k}})}n^{O(1)}}$${\displaystyle 2^{o({\sqrt {k}})}n^{O(1)}}$

เราสามารถหา ค่าประมาณตัวประกอบ 2 ได้ โดยการนำ จุดปลาย ทั้งสองของขอบไปใส่ไว้ในกลุ่มจุดยอดซ้ำๆ แล้วจึงนำจุดปลายเหล่านั้นออกจากกราฟ กล่าวอีกนัยหนึ่งคือ เราหาการจับคู่สูงสุดMด้วยอัลกอริทึมแบบโลภ (greedy algorithm) และสร้างกลุ่มจุดยอดCที่ประกอบด้วยจุดปลายทั้งหมดของขอบในMในรูปต่อไปนี้ การจับคู่สูงสุดMถูกทำเครื่องหมายด้วยสีแดง และกลุ่มจุดยอดCถูกทำเครื่องหมายด้วยสีน้ำเงิน

เซตCที่สร้างขึ้นในลักษณะนี้คือเซตปกคลุมจุดยอด: สมมติว่าขอบeไม่ถูกปกคลุมโดยCดังนั้นM  ∪ { e } คือการจับคู่ และe  ∉  Mซึ่งขัดแย้งกับสมมติฐานที่ว่าMเป็นเซตสูงสุด ยิ่งไปกว่านั้น ถ้าe  = { u ,  v } ∈ Mแล้ว เซตปกคลุมจุดยอดใดๆ – รวมถึงเซตปกคลุมจุดยอดที่เหมาะสมที่สุด – จะต้องมีuหรือv (หรือทั้งสองอย่าง) มิฉะนั้น ขอบeจะไม่ถูกปกคลุม กล่าวคือ เซตปกคลุมที่เหมาะสมที่สุดจะต้องมีจุดปลายอย่างน้อยหนึ่งจุดของแต่ละขอบในMโดยรวมแล้ว เซตCมีขนาดใหญ่กว่าเซตปกคลุมจุดยอดที่เหมาะสมที่สุดไม่เกิน 2 เท่า

อัลกอริทึมง่ายๆ นี้ถูกค้นพบโดยอิสระโดย Fanica Gavril และMihalis Yannakakis ^{[ 8 ]}

เทคนิคที่ซับซ้อนกว่าแสดงให้เห็นว่ามีอัลกอริธึมการประมาณค่าที่มีปัจจัยการประมาณค่าที่ดีกว่าเล็กน้อย ตัวอย่างเช่นทราบ อัลกอริธึมการประมาณค่าที่มีปัจจัยการประมาณค่า ^{[ 9 ]}ปัญหาสามารถประมาณค่าได้ด้วยปัจจัยการประมาณค่าในกราฟหนาแน่น^{[ 10 ]}${\textstyle 2-\Theta \left(1/{\sqrt {\log |V|}}\right)}$${\displaystyle 2/(1+\delta )}$${\displaystyle \delta }$

ไม่มีอัลกอริทึมการประมาณค่าคงที่ ที่ดีกว่าอัลกอริ ทึมข้างต้น ปัญหาการครอบคลุมจุดยอดขั้นต่ำเป็นปัญหาAPX-completeนั่นคือ ไม่สามารถประมาณค่าได้ดีอย่างไม่จำกัด เว้นแต่ P  =  NPโดยใช้เทคนิคจากทฤษฎีบทPCP DinurและSafraพิสูจน์ในปี 2005 ว่าการครอบคลุมจุดยอดขั้นต่ำไม่สามารถประมาณค่าได้ภายในปัจจัย 1.3606 สำหรับระดับจุดยอดที่ใหญ่พอสมควร เว้นแต่P  =  NP ^{[ 11} ] ต่อมา ปัจจัยได้รับการปรับปรุงเป็นสำหรับทุก[ ^{12 ]} ยิ่งไปกว่านั้น หากสมมติฐานเกมที่ไม่ซ้ำกัน เป็นจริง ^การครอบคลุมจุดยอดขั้นต่ำไม่สามารถประมาณค่าได้ภายในปัจจัยคงที่ใด ๆ ที่ดีกว่า^{2 [ 13 ]}${\displaystyle {\sqrt {2}}-\เอปไซลอน }$${\displaystyle \epsilon >0}$

แม้ว่าการหาชุดปกคลุมจุดยอดที่มีขนาดเล็กที่สุดจะเทียบเท่ากับการหาชุดอิสระที่มีขนาดใหญ่ที่สุด ดังที่ได้อธิบายไว้ข้างต้น แต่ปัญหาทั้งสองนี้ไม่เทียบเท่ากันในแง่ของการรักษาค่าประมาณ: ปัญหาชุดอิสระไม่มีการประมาณค่าคงที่เว้นแต่ว่า P  =  NP

อัลกอริทึมการประมาณค่า: ^{[ 14 ] [ 15 ]}

การประมาณค่า- จุดยอด- ครอบคลุม( G ) C = ∅ E ' = G . Eในขณะที่E ' ≠ ∅ : ให้( u , v ) เป็นขอบใดๆของE ' C = C ∪ { u , v } ลบขอบทุกขอบออกจากE ' ที่เชื่อมต่อกับu หรือvส่งคืนC

• ชุดที่โดดเด่น

วิกิมีเดียคอมมอนส์มีสื่อที่เกี่ยวข้องกับปัญหาการปกปิดจุดยอด (Vertex cover problem )

• ไวส์สไตน์, เอริค ดับเบิลยู. "Vertex Cover" . MathWorld .
• ไวส์สไตน์, เอริค ดับเบิลยู. "การครอบคลุมจุดยอดขั้นต่ำ" . MathWorld .
• ไวส์สไตน์, เอริค ดับเบิลยู. "จำนวนปกคลุมจุดยอด" . MathWorld .
• จุดข้ามแม่น้ำ (และเลขอัลคูอิน) – Numberphile