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

Algorithm Concat-Cycles

1. For each cycle $c_(i)=i_(1)->...->i_(r)->i_(1)$ , let $bar(s_(i))=<<s_(i_(1)),...,s_(i_(r))>>$ be the string obtained by opening $c_(i)$ , where $i_(1)$ is chosen. The string $bar(s_(i))$ has length at most $w(c_(i))+|s_(i_(1))|$ .

2. Concatenate together the strings $bar(s_(i))$ and produce the resulting string $bar(s)$ as output.

ก่อนที่จะพิสูจน์ว่าได้ 4-OPT(S) จะขอพิสูจน์ lemma อันหนึ่งก่อน ซึ่งจะนำมาใช้เพื่อพิสูจน์ theorem อีกที

Lemma: ถ้า $c$ และ $c'$ เป็น cycle ใน minimum cycle cover $C$โดยมี string$s in c$ และ $s' in c'$ จะได้ว่า overlap ระหว่าง $s$ และ $s'$ จะน้อยกว่า $w(c)+w(c')$

Proof: ให้ $x=string(c)$ และ $x'=string(c')$ เรารู้ว่า $x!=x'$ เพราะไม่เช่นนั้นแล้ว จาก claim1 และ claim 2 เราจะสามารถหา cycle ที่น้ำหนักน้อยกว่าที่ครอบคลุม string ทั้งใน $c$ และ $c'$ ได้ นอกจากนี้ จาก claim 3 จะได้ว่า $w(c)<=card(x)$

สมมติให้ $u$ เป็น string ส่วนที่ overlap กันระหว่าง $s$ และ $s'$ โดยให้ $|u|>=w(c)+w(c')$ (เราจะแทน substring ของ $u$ ตั้งแต่ตัวที่ $i$ ถึงตัวที่ $j$ ว่า $u_(i,j)$ ) จาก claim 2 จะได้ว่า $s = t^(k)$ สำหรับบางค่า $t in x$ และค่า $k$ ที่ใหญ่มากพอ และ $s'=t'^(k')$ สำหรับบางค่า $t' in x'$ และ $k'$ ที่มากพอ แต่เราทราบว่า $x=[u_(1,w(c))]$ และ $x'=[u_(1,w(c'))]$ และ $x!=x'$ ดังนั้น $w(c)!=w(c')$ เราสามารถสมมติให้ $w(c)>w(c')$ ซึ่งจะได้

$u_(1,w(c))$ $=$ $u_(1+w(c'),w(c)+w(c'))$ $=$ $u_(1+w(c'),w(c))u_(w(c)+1,w(c)+w(c'))$ $=$ $u_(1+w(c'),w(c))u_(1,w(c'))$

ซึ่งแสดงว่า $x$ มี periodicity $w(c')<w(c)<=card(x)$ เกิดข้อขัดแย้งที่ว่า $card(x)$ เป็น minimum periodicity $square$

ทีนี้เราก็สามารถพิสูจน์ Theorem ที่รอมานาน

Theorem: Algorithm Concat-Cycle ให้ string ที่มีความยาวไม่เกิน 4-OPT(S)

Proof: เนื่องจาก $C={c_(1),...,c(p)}$ เป็น minimum cycle cover ดังนั้น $CYC(G_(S))=sum_(i=1)^(p)w(c_(i))<=OPT(S)$ และพิจารณาสำหรับแต่ละ cycle $c_(i)$ ให้ $l_(i)$ แทนความยาวของ string ที่ยาวที่สุดใน $c_(i)$ จาก lemma ด้านบน หากเราสนใจการเชื่อมระหว่าง string ที่ยาวที่สุดเข้าด้วยกัน overlap ทั้งหมดก็จะไม่เกิน $2sum_(i=1)^(p)w(c_(i))$ และความยาวของ string ที่ได้ก็จะต้องไม่น้อยกว่า $sum_(i=1)^(p)l_(i)-2sum_(i=1)^(p)w(c_(i))$ ดังนั้นเราจึงได้อีกว่า $OPT(S)>=sum_(i=1)^(p)l_(i)-2sum_(i=1)^(p)w(c_(i))$

เนื่องจาก string ที่ได้จากอัลกอริทึมของเราจะมีความยาวไม่เกิน $sum_(i=1)^(p)l_(i)+sum_(i=1)^(p)w(c_(i))$ ดังนั้นจึงได้

$|bar(s)|<=sum_(i=1)^(p)l_(i)+sum_(i=1)^(p)w(c_(i))$ $=$ $sum_(i=1)^(p)l_(i)-2sum_(i=1)^(p)w(c_(i))+3sum_(i=1)^(p)w(c_(i))$ $<=$ $OPT(S)+3OPT(S)$ $=$ $4OPT(S)$ $square$