คราวนี้จะได้เห็น 4-OPT กันจริงๆ สมมติให้ $S$ เป็นเซตของ string และ $G_(S)$ เป็นกราฟแสดงระยะห่าง เราจะแบ่งขั้นตอนเป็นสองส่วนหลักๆ ขั้นแรกคือเราจะหา minimum cycle cover ของ $G_(S)$ เมื่อหาได้แล้ว เราจะแตกแต่ละ cycle ออกเป็น string และนำ string เหล่านี้มาเชื่อมต่อกันซึ่งสามารถรับประกันได้ว่า ความยาวของ string ที่ได้จะไม่มากไปกว่าความยาวของ shortest super string ของเซต $S$

ในขั้นแรก เราจะแสดงวิธีหา minimum cycle cover บนกราฟ $G_(S)$ ก่อน ( จะขอเรียกอัลกอริทึมนี้ว่า MGREEDY ตามใน paper )

Algorithm MGREEDY

1. Let $S$ be the input set of strings and $T$ be empty.

2. while ( $S$ is non-empty )
{
Choose $s,t in S$ (not necessarity distinct) such that $ov(s,t)$ is maximized
if ( $s!=t$ ) then
remove $s$ and $t$ from $S$ and replace them with the merged string $<<s,t>>$
else ( $s=t$ )
remove $s$ from $S$ and add it to $T$
}

3. When $S$ is empty, output the cycle of strings in $T$

เราจะพิสูจน์กันก่อนว่าอัลกอริทึมนี้ให้ผลเป็น minimum cycle cover บน $G_(S)$ จริง

Theorem: MGREEDY ให้ผลลัพธ์เป็น minimum cycle cover บน $G_(S)$
Proof: ก่อนอื่นขอให้เห็นว่าระยะ $d(,)$ และ $ov(,)$ นั้นรวมกันเป็นความยาวของ string เสมอ ดังนั้น ผลลัพธ์จะเป็น minimum cycle cover บนกราฟระยะห่าง ก็ต่อเมื่อเป็น maximum cycle cover บนกราฟ overlap ให้ cycle cover ที่ได้จากอัลกอริทึมแทนด้วย $M$ และให้ $N$ เป็น maximum cycle cover บนกราฟ overlap ที่มี edge ซ้ำกับ $M$ มากที่สุด เราจะแสดงว่า $M=N$

เราจะพิสูจน์ด้วย contradiction โดยสมมติให้ $M!=N$ ดังนั้น จะต้องมี edge $e$ ที่อยู่ใน $M$ แต่ไม่อยู่ใน $N$ สมมติให้ $e=k->j$ ใน $N$ จะต้องมี edge $i->j$ และ $k->l$ ที่ไม่อยู่ใน $M$ จากอัลกอริทึม การที่ $M$ เลือก edge $e$ นั้นแสดงว่า $ov(k,j)>=max{ov(i,j),ov(k,l)}$ ซึ่งสามารถพิสูจน์ได้ไม่ยากนักว่าเงื่อนไขดังกล่าวจะทำให้ $ov(i,j)+ov(k,l)<=ov(k,j)+ov(i,l)$ จากตรงนี้ หากเราแทน edge ทั้งสองใน $N$ ด้วย $e=k->j$ และ $i->l$ จะได้ cycle cover $N'$ ซึ่งมี edge ซ้ำกับ $M$ มากขึ้นและมีน้ำหนักไม่น้อยกว่า $N$ ดังนั้นจึงเกิด contradiction$square$

ขั้นตอนต่อไปไว้คราวหน้าละกัน