ต่อจากคราวที่แล้ว หลังจากที่เราได้ 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$

คราวนี้จะได้เห็น 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$

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

คราวนี้เราจะมาวิเคราะห์เกี่ยวกับ cycle ในกราฟ $G_(S)$ ดู
เราจะกล่าวว่า string $s$ และ $t$ สมมูลกัน ($s-=t$) ถ้าเราสามารถ shift วนไปมาระหว่างกันได้ หรือกล่าวได้ว่าจะสมมูลกันเมื่อมี string $u$,$v$ ที่ $s=uv$ และ $t=vu$ ถ้าให้ $c$ เป็น directed cycle ในกราฟ $G_(S)$ ตามลำดับจุดยอด $i_(0),i_(1),...,i_(r-1)$ เราจะให้นิยาม $stri ng(c)$ เป็นคลาสสมมูล $[pref(i_(0),i_(1))pref(i_(1),i_(2))* * *pref(i_(r-1),i_(0))]$ และให้ $stri ng(c,i_(k))$ เป็นกรณีที่เริ่มต้นด้วย $pref(i_(k),i_(k+1))$ เราจะบอกว่า คลาสสมมูล $[s]$ มีคาบ $k (k>0)$ ถ้า $s$ shift ไป $k$ character แล้วเท่ากับ $s$ เหมือนเดิม จะเห็นว่า $[s]$ มีคาบ $|s|$ แน่นอน เราสามารถพิสูจน์ได้ว่าคาบที่น้อยที่สุดของ $[s]$ จะเท่ากับขนาดของคลาส และจะแทนด้วย $card([s])$

นอกจากนี้ เราอาจแทน cycle $c$ ด้วยลำดับจุดยอดโดยแสดงเป็น $i_(1)->* * *->i_(r)->i_(1)$ และให้ $w(c)$ เป็นน้ำหนักของ $c$ ซึ่งจะเท่ากับ $|s|$ สำหรับ $s in stri ng(c)$ และเราจะกล่าวว่า string $s_(j) in c$ ถ้า $j$ เป็นจุดยอดใน $c$

Claim 1: แต่ละ string $s_(i_(j)) in c$ เป็น substring ของ $s^(k)$ สำหรับทุกๆ $s in stri ng(c)$ และค่า $k$ ที่ใหญ่มากพอ
Proof: หากเราให้ $m=ceil(|s_(i_(j))|//(w(c)))$ เราจะได้ว่า $s_(i_(j))$ เป็น prefix ของ $pref(s_(i_(j)),s_(i_(j+1)))* * *pref(s_(i_(j+mr-1)),s_(i_(j+mr)))=stri ng(c,i_(j))^(m)$ ซึ่งเป็น substring ของ $s^(k)$ สำหรับทุกๆ $s in stri ng(c)$ และ $k>m$ $square$

Claim 2: ถ้าแต่ละ $s_(j_(1)),...,s_(j_(r))$ เป็น substring ของ $s^(k)$ สำหรับบาง $s in stri ng(c)$ และค่า $k$ ที่ใหญ่มากพอ จะมี cycle ที่มีน้ำหนัก $w(c)=|s|$ ที่ครอบคลุม string เหล่านี้ทั้งหมด
Proof: หากเรานำ $s$ มาต่อกันเองให้ยาวไม่มีที่สิ้นสุด ทุกๆ string $s_(i)$ จะปรากฏเป็น substring ของ $s$ ทุกๆ $|s|$ character ซึ่งเราสามารถสร้าง cycle ตามลำดับที่ string ปรากฏ โดยจะได้ $w(c)$ เท่ากับ $|s|$ $square$

Claim 3: จะมี cycle $bar(c)$ ที่มีน้ำหนัก $card(stri ng(c))$ ที่ครอบคลุมทุกๆจุดยอดใน $c$
Proof: ให้ $u$ เป็น prefix ความยาว $card(stri ng(c))$ ของ string $s in stri ng(c)$ จากความรู้เรื่องคาบ เราจะได้ว่า $|u|$ หาร $|s|$ ลงตัว และ $s=u^(j)$ ซึ่งจะได้ต่อมาว่า ทุกๆ string ใน $stri ng(c)=[s]$ จะเป็น substring ของ $u^(j+1)$ และจาก Cliam 2 ก็จะพิสูจน์ได้ $square$