ขั้นตอนวิธีของคาร์เกอร์
ในวิทยาการคอมพิวเตอร์และทฤษฎีกราฟ ขั้นตอนวิธีของคาร์เกอร์ () เป็น เพื่อคำนวณหา การตัดน้อยสุด (minimun cut) ของกราฟต่อเนื่อง ซึ่งถูกพัฒนาขึ้นโดย
โดยการตัดน้อยสุด คือ จำนวนเส้นเชื่อมน้อยสุดที่ต้องลบออกเพื่อให้กราฟแยกเป็น 2 ส่วน(component)
หลักการของขั้นตอนวิธีนี้ใช้แนวคิดในการย่อเส้นเชื่อม formula_1 ในกราฟ หรือกล่าวได้ว่าเป็นการย่อเส้นเชื่อมทำให้ปม 2 ปมที่ต่อกับ e ซ้อนกัน ทำให้ลดจำนวนปมทั้งหมดของกราฟลงไปหนึ่งปม ขั้นตอนวิธีนี้จะดำเนินการย่อไปเรื่อยๆ จนกว่าจะเหลือปมในกราฟเพียง 2 ปมเท่านั้น ซึ่งการกระทำนี้มีความเป็นไปได้สูงที่ขั้นตอนวิธีนี้จะคืนการตัดน้อยสุด โดยจะคืนเซตของเส้นเชื่อมที่ต่อกับปมที่เหลือทั้งสอง
การกระทำนี้เอาเส้นเชื่อม formula_1 ที่มีปลาย formula_3 และ formula_4 และย่อมันลงในปมใหม่ formula_5 ซึ่งจะกลายเป็นเส้นประชิด(adjacent)ของปมเก่าทั้งหมดที่ต่อกับformula_3 และ formula_4 โดยสามารถเขียนแนวคิดนี้ให้อยู่ให้รูปคณิตศาสตร์ได้
ให้กราฟ formula_8 และ formula_9, การย่อของ formula_10 ไปเป็น formula_1 (เขียนเป็น formula_12) เป็น มัลติกราฟ เมื่อ:
เป็นไปได้ที่จะพิสูจน์ว่าการกระทำนี้ไม่ได้ลดภาวะเชิงการนับของการตัดน้อยสุด แต่อาจเป็นการเพิ่มให้มากขึ้น
รหัสเทียมนี้สามารถสร้างขึ้นโดยใช้ 2 ฟังก์ชัน
ฟังก์ชัน Full_contraction ทำการย่อเส้นเชื่อมตามขั้นตอนวิธีที่ได้ระบุไว้ จากนั้นทำซ้ำไปเรื่อยๆ จนกว่าจะเหลือปมในกราฟเพียงสองปม จากนั้นจึงคืนค่าจำนวนเส้นเชื่อมระหว่างสองปมนั้น ซึ่งจะเท่ากับจำนวนตัดน้อยสุด
แต่มันไม่สามารถประกันได้ว่าขั้นตอนวิธีนี้จะคืนการตัดที่น้อยที่สุดจริงๆ เพราะฉะนั้นการ excution Full_contraction K ครั้งโดยฟังก์ชัน Karger จะส่ง parameter K เพื่อให้ทำการคำนวณค่าน้อยสุดเป็นจำนวน K ครั้ง และเก็บคำตอบครั้งที่น้อยที่สุด ซึ่งวิธีนี้จะช่วยลดโอกาสที่จะคืนค่าการตัดน้อยสุดผิด
ฟังก์ชัน Full_contraction ใช้เวลาในการทำงานในรูปสัญกรณ์โอใหญ่ได้เป็น O("e") เมื่อ"e" คือ จำนวนเชิงเชื่อม เนื่องจากต้องทำการลบเส้นเชื่อมทุกเส้นเชื่อมจนกว่าจะเหลือปมเพียง 2 ปม และการทำฟังก์ชัน Karger เป็นการทำ Full_contraction ซ้ำเป็นจำนวน K รอบ แต่เนื่องจาก K เป็นค่าคงที่ ดังนั้นประสิทธิภาพเชิงเวลาจึงยังคงเป็น O("e") หรือ O("V ") สำหรับกราฟหนาแน่น