ปัญหาต้นไม้แผ่คลุมขั้นต่ำk ตัว (k -minimum spanning tree problem ) ซึ่งศึกษาในสาขาวิทยาการคอมพิวเตอร์เชิงทฤษฎีต้องการหาต้นไม้ที่มีต้นทุนต่ำที่สุด มีจุดยอดk จุดพอดี และเป็นกราฟย่อยของกราฟที่ใหญ่กว่า เรียกอีกอย่างว่าk -MSTหรือ ต้นไม้ที่มีน้ำหนักขอบ k จำนวนสมาชิก (edge-weighted k -cardinality tree ) การหาต้นไม้นี้เป็นปัญหา NP-hardแต่สามารถประมาณค่าได้ภายในอัตราส่วนการประมาณค่า คงที่ ในเวลาพหุนาม

อินพุตของปัญหาประกอบด้วยกราฟแบบไม่มีทิศทางที่มีน้ำหนักบนขอบ และจำนวนkเอาต์พุตคือต้นไม้ที่มีk จุดยอดและk − 1 ขอบ โดยที่ขอบทั้งหมดของต้นไม้เอาต์พุตเป็นส่วน หนึ่งของกราฟอินพุต ต้นทุนของเอาต์พุตคือผลรวมของน้ำหนักของขอบ และเป้าหมายคือการหาต้นไม้ที่มีต้นทุนต่ำที่สุด ปัญหานี้ได้รับการกำหนดโดยLozovanu & Zelikovsky (1993) ^{[ 1 ]}และโดยRavi et al. (1996 )

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

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

การลดรูปนี้รับอินพุตเป็นตัวอย่างของปัญหาต้นไม้สไตเนอร์: กราฟที่มีน้ำหนัก โดยมีเซตย่อยของจุดยอดที่เลือกไว้เป็นจุดปลาย เป้าหมายของปัญหาต้นไม้สไตเนอร์คือการเชื่อมต่อจุดปลายเหล่านี้ด้วยต้นไม้ที่มีน้ำหนักน้อยที่สุดเท่าที่จะเป็นไปได้ ในการแปลงปัญหานี้ให้เป็นตัวอย่างของปัญหาต้นไม้แผ่คลุมขั้นต่ำk จุด Ravi et al. (1996)ได้แนบต้นไม้ของขอบที่มีน้ำหนักเป็นศูนย์เข้ากับจุดปลายแต่ละจุด โดยมีจำนวน จุดยอด t จำนวนมาก ต่อต้นไม้ (สำหรับกราฟที่มี จุดยอด nจุดและ จุดปลาย rจุด พวกเขาใช้t = n − r − 1จุดยอดที่เพิ่มเข้ามาต่อต้นไม้) จากนั้น พวกเขาขอ ต้นไม้แผ่คลุมขั้นต่ำ kจุดในกราฟที่เพิ่มเข้ามานี้ โดยที่k = rtวิธีเดียวที่จะรวมจุดยอดจำนวนมากนี้ใน ต้นไม้แผ่คลุม kจุดได้คือการใช้จุดยอดอย่างน้อยหนึ่งจุดจากแต่ละต้นไม้ที่เพิ่มเข้ามา เนื่องจากจะมีจุดยอดไม่เพียงพอหากขาดต้นไม้ที่เพิ่มเข้ามาแม้แต่ต้นเดียว อย่างไรก็ตาม สำหรับการเลือก k นี้ เป็นไปได้ที่ ต้นไม้ครอบคลุม kจะมีขอบของกราฟเดิมเพียงจำนวนน้อยเท่าที่จำเป็นในการเชื่อมต่อเทอร์มินัลทั้งหมด ดังนั้น ต้นไม้ครอบคลุมขั้นต่ำ kจะต้องถูกสร้างขึ้นโดยการรวมต้นไม้สไตเนอร์ที่เหมาะสมที่สุดเข้ากับขอบที่มีน้ำหนักเป็นศูนย์ของต้นไม้ที่เพิ่มเข้ามาให้มากพอที่จะทำให้ขนาดต้นไม้ทั้งหมดมีขนาดใหญ่พอ^{[ 2 ]}

แม้แต่สำหรับกราฟที่มีน้ำหนักขอบอยู่ในเซต{1, 2, 3 } การทดสอบว่าค่าคำตอบที่เหมาะสมที่สุดน้อยกว่าเกณฑ์ที่กำหนดหรือไม่นั้นยังคงเป็นNP-completeและยังคงเป็น NP-complete สำหรับกราฟระนาบเวอร์ชันเรขาคณิตของปัญหานี้ก็เป็น NP-hard เช่นกัน แต่ไม่เป็นที่ทราบกันว่าอยู่ใน NP เนื่องจากความยากลำบากในการเปรียบเทียบผลรวมของรากที่สอง แต่กลับอยู่ในกลุ่มของปัญหาที่สามารถลดรูปได้เป็นทฤษฎีการมีอยู่ของจำนวนจริง^{[ 2 ]}

ต้นไม้ แผ่ขยายขั้นต่ำ kสามารถค้นหาได้ในเวลาพหุนามสำหรับกราฟที่มีtreewidth จำกัด และสำหรับกราฟที่มีน้ำหนักขอบที่แตกต่างกันเพียงสองค่า^{[ 2 ]}

เนื่องจากความซับซ้อนในการคำนวณสูงของการค้นหาคำตอบที่เหมาะสมที่สุดสำหรับปัญหา ต้นไม้แผ่ขยายขั้นต่ำ kตัว งานวิจัยส่วนใหญ่เกี่ยวกับปัญหานี้จึงมุ่งเน้นไปที่อัลกอริธึมการประมาณค่าแทน เป้าหมายของอัลกอริธึมดังกล่าวคือการหาคำตอบโดยประมาณในเวลาพหุนามด้วยอัตราส่วนการประมาณค่า ที่น้อย อัตราส่วนการประมาณค่าถูกกำหนดให้เป็นอัตราส่วนของความยาวคำตอบที่คำนวณได้ต่อความยาวที่เหมาะสมที่สุดสำหรับกรณีที่เลวร้ายที่สุด ซึ่งเป็นกรณีที่ทำให้อัตราส่วนนี้สูงสุด เนื่องจากการลดความยากแบบ NP สำหรับ ปัญหาต้นไม้แผ่ขยายขั้นต่ำ kตัวจะรักษาน้ำหนักของคำตอบทั้งหมดไว้ จึงรักษาความยากของการประมาณค่าของปัญหาไว้ด้วย โดยเฉพาะอย่างยิ่ง เนื่องจากปัญหาต้นไม้สไตเนอร์นั้นยากแบบ NP ที่จะประมาณค่าด้วยอัตราส่วนการประมาณค่าที่ดีกว่า 96/95 ^{[ 3 ]}ดังนั้นจึงเป็นเช่นเดียวกันสำหรับปัญหาต้นไม้แผ่ขยายขั้นต่ำ k ตัว

การประมาณค่าที่ดีที่สุดที่ทราบสำหรับปัญหาทั่วไปบรรลุอัตราส่วนการประมาณค่าที่ 2 และได้มาจากGarg (2005) [ ^{4 ] การ}ประมาณค่านี้อาศัยแบบแผนคู่หลัก-คู่ของGoemans & Williamson (1992)เป็น อย่างมาก ^{[ 5 ]} เมื่ออินพุตประกอบด้วยจุดในระนาบยุคลิด (ซึ่งสามารถเชื่อมต่อจุดสองจุดใดๆ ในต้นไม้ได้โดยมีต้นทุนเท่ากับระยะทาง) จะมีแบบแผนการประมาณค่าแบบพหุนามที่คิดค้นโดยArora (1998 ) ^{[ 6 ]}

• ต้นไม้ k-spanning ขั้นต่ำใน "คู่มือรวมปัญหาการหาค่าเหมาะสมที่สุดแบบ NP"
• KCTLIB , KCTLIB -- ไลบรารีสำหรับปัญหาต้นไม้ที่มีน้ำหนักขอบ K-Cardinality