ในสาขาคณิตศาสตร์เชิงการจัดเรียงและวิทยาศาสตร์คอมพิวเตอร์ปัญหาการครอบคลุม (covering problems)คือปัญหาการคำนวณที่ถามว่าโครงสร้างเชิงการจัดเรียงแบบหนึ่งสามารถ "ครอบคลุม" โครงสร้างอื่นได้หรือไม่ หรือโครงสร้างนั้นต้องมีขนาดใหญ่แค่ไหนจึงจะสามารถครอบคลุมได้ ปัญหาการครอบคลุมเป็นปัญหาการหาค่าต่ำสุดและโดยทั่วไปเป็นโปรแกรมเชิงเส้นจำนวนเต็ม ซึ่ง ปัญหาคู่ขนานของ ปัญหาเหล่านี้ เรียกว่าปัญหาการบรรจุ (packing problems )

ตัวอย่างที่โดดเด่นที่สุดของปัญหาการครอบคลุม ได้แก่ปัญหาการครอบคลุมเซตซึ่งเทียบเท่ากับปัญหาเซตกระทบและกรณีพิเศษของปัญหาดังกล่าว ได้แก่ปัญหา การครอบคลุมจุดยอดและปัญหาการครอบคลุมขอบ

ปัญหาการครอบคลุมอนุญาตให้รูปทรงพื้นฐานที่ใช้ในการครอบคลุมนั้นทับซ้อนกันได้ กระบวนการครอบคลุมสิ่งใดสิ่งหนึ่งด้วยรูปทรงพื้นฐานที่ไม่ทับซ้อนกันเรียกว่าการแยกส่วน

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

ลดให้น้อยที่สุด	${\displaystyle \sum _{i=1}^{n}c_{i}x_{i}}$
ขึ้นอยู่กับ	${\displaystyle \sum _{i=1}^{n}a_{ji}x_{i}\geq b_{j}{\text{ สำหรับ }}j=1,\dots ,m}$
	${\displaystyle x_{i}\in \left\{0,1,2,\ldots \right\}{\text{ สำหรับ }}i=1,\dots ,n}$.

โปรแกรมเชิงเส้นจำนวนเต็มดังกล่าวเรียกว่าปัญหาการครอบคลุม (covering problem)ถ้า สำหรับทุกและ${\displaystyle a_{ji},b_{j},c_{i}\geq 0}$${\displaystyle i=1,\dots ,n}$${\displaystyle j=1,\dots ,m}$

แนวคิดเบื้องต้น:สมมติว่ามีวัตถุอยู่ 2 ประเภท และวัตถุแต่ละประเภทมีราคาn ตัวเลข n บ่งบอกจำนวนวัตถุประเภทที่เราซื้อ หากเงื่อนไขเป็นไปตามที่กำหนด จะกล่าวได้ว่าเป็นการครอบคลุม (โครงสร้างที่ถูกครอบคลุมขึ้นอยู่กับบริบทเชิงการจัดเรียง) สุดท้ายแล้ว คำตอบที่เหมาะสมที่สุดสำหรับโปรแกรมเชิงเส้นจำนวนเต็มข้างต้นคือการครอบคลุมที่มีต้นทุนต่ำที่สุด ${\displaystyle n}$${\displaystyle i}$${\displaystyle c_{i}}$${\displaystyle x_{i}}$${\displaystyle i}$${\displaystyle A\mathbf {x} \geq \mathbf {b} }$${\displaystyle \mathbf {x} }$

มีปัญหาการครอบคลุมหลายประเภทในทฤษฎีกราฟเรขาคณิตเชิงคำนวณและอื่นๆ ดูหมวดหมู่: ปัญหาการครอบคลุมปัญหาเวอร์ชันอื่นๆ ที่เกี่ยวข้องกับสโตแคสติกสามารถพบได้^{[ 2 ]}

สำหรับโครงข่ายเพทรีปัญหาการครอบคลุมถูกกำหนดให้เป็นคำถามว่า สำหรับค่าที่กำหนด จะมีลำดับของโครงข่ายอยู่หรือไม่ ที่สามารถเข้าถึงค่าที่ใหญ่กว่า (หรือเท่ากัน) ได้ คำว่า " ใหญ่กว่า"ในที่นี้หมายความว่า ส่วนประกอบทั้งหมดต้องมีขนาดอย่างน้อยเท่ากับส่วนประกอบของค่าที่กำหนด และอย่างน้อยหนึ่งส่วนต้องมีขนาดใหญ่กว่าอย่างเหมาะสม

ในปัญหาการครอบคลุมบางปัญหา การครอบคลุมควรเป็นไปตามข้อกำหนดเพิ่มเติมบางประการ โดยเฉพาะอย่างยิ่งใน ปัญหา การครอบคลุมสีรุ้งวัตถุเดิมแต่ละชิ้นมี "สี" และจำเป็นต้องมีการครอบคลุมโดยมีวัตถุแต่ละสีเพียงหนึ่งชิ้น (หรืออย่างมากที่สุดหนึ่งชิ้น) การครอบคลุมสีรุ้งได้รับการศึกษา เช่น สำหรับการครอบคลุมจุดด้วยช่วงเวลา : ^{[ 5 ]}

• มีเซตJของ ช่วงสี nช่วงบนเส้นจำนวนจริงและเซตPของจุดบนเส้นจำนวนจริง
• เซตย่อยQของJเรียกว่าเซตสีรุ้งถ้าเซตย่อยนั้นประกอบด้วยช่วงสีแต่ละสีอย่างมากที่สุดเพียงช่วงเดียว
• เซตของช่วงJเรียกว่าการครอบคลุมของPถ้าแต่ละจุดในPอยู่ในอย่างน้อยหนึ่งช่วงของQ
• ปัญหาการปกคลุมแบบสายรุ้งคือปัญหาการหาเซตสายรุ้งQที่เป็นการปกคลุมของP

ปัญหาดังกล่าวเป็นปัญหาNP-hard (จากการลดรูปมาจากปัญหา SAT เชิงเส้น )

แนวคิดทั่วไปมากกว่าคือ การครอบคลุม ที่ปราศจากความขัดแย้ง^{[ 6 ]}ในปัญหานี้:

• มีเซตOที่ประกอบด้วย วัตถุ mชิ้น และกราฟความขัดแย้งG _OบนO
• เซตย่อยQของOเรียกว่าเซตที่ปราศจากความขัดแย้งถ้าเป็นเซตอิสระในG _Oกล่าวคือ ไม่มีวัตถุสองชิ้นใดในQที่เชื่อมต่อกันด้วยขอบในG _O
• เซตสีรุ้งเป็นเซตที่ปราศจากความขัดแย้งในกรณีพิเศษที่G _Oประกอบด้วยคลิกที่ไม่ซ้ำกัน โดยแต่ละคลิกแทนสีหนึ่งสี

ปัญหา การครอบคลุมเซตที่ปราศจากความขัดแย้งคือปัญหาของการค้นหาเซตย่อยที่ปราศจากความขัดแย้งของOที่เป็นการครอบคลุมของP Banik, Panolan, Raman, Sahlot และ Saurabh ^{[ 7 ]}พิสูจน์สิ่งต่อไปนี้สำหรับกรณีพิเศษที่กราฟความขัดแย้งมีขอบเขตของความเป็นต้นไม้ :

• ถ้าปัญหาการปกคลุมทางเรขาคณิต สามารถแก้ไขได้ด้วย พารามิเตอร์คงที่ (FPT) แล้ว ปัญหาการปกคลุมทางเรขาคณิตที่ปราศจากความขัดแย้งก็จะเป็น FPT เช่นกัน
• หากปัญหาการปกคลุมทางเรขาคณิตยอมรับอัลกอริทึมการประมาณค่าแบบ r แล้ว ปัญหาการปกคลุมทางเรขาคณิตที่ปราศจากความขัดแย้งก็จะยอมรับอัลกอริทึมการประมาณค่าที่คล้ายกันในเวลา FPT เช่นกัน