สำหรับ string $s$ และ $t$ ใดๆที่ไม่จำเป็นต้องต่างกันก็ได้ ให้ $v$ เป็น string ที่ยาวที่สุดที่ทำให้ $s=uv$ และ $t=vw$ โดย string $u$ และ $w$ ไม่เป็น empty string เราจะเรียก $|v|$ ว่า overlap ระหว่าง $s$ และ $t$ แทนได้ด้วย $ov(s,t)$ เราจะเรียก $u$ ว่าเป็น prefix ของ $s$ เทียบกับ $t$ แทนได้ด้วย $pref(s,t)$ และจะเรียก $|pref(s,t)|=|u|$ ว่าเป็น distance จาก $s$ ไปยัง $t$ แทนด้วย $d(s,t)$

หากเรามี string $s_(1),s_(2),...,s_(r)$ เราจะให้นิยาม string $s=<s_(1),...,s_(r)>$ ว่าเป็น string $pref(s_(1),s_(2))pref(s_(2),s_(3))* * *pref(s_(r-1),s_(r))s_(r)$ ซึ่งก็คือ string ที่สั้นที่สุดที่มี $s_(1),s_(2),...,s_(r)$ ปรากฏในนั้นตามลำดับ เราจะให้ $first(s)=s_(1)$ และ $last(s)=s_(r)$ จะเห็นว่าเราสามารถมองปัญหาในรูปของการสับเปลี่ยนลำดับของ string โดยจะมีอย่างน้อยหนึ่งลำดับที่ทำให้ได้ superstring ที่มีความยาวน้อยที่สุด

หากเปรียบเทียบปัญหาของเรากับปัญหาอื่นที่รู้จักกันดี คือ TSP ( Traveling Salesman Problem ) เราสามารถเชื่อมโยง SSP กับ TSP ในกรณีที่กราฟมีทิศทางได้ เราสามารถสร้างกราฟมีทิศทางและน้ำหนัก $G_(S)$ จาก $S$ โดยให้ $G_(S)=(V,E,d)$ มีจุดยอด $m$ จุด $V={1,...,m}$ และมีเส้นเชื่อม $m^(2)$ เส้น $E={(i,j):1<=i,j<=m}$ และให้เส้นเชื่อม $(i,j)$ มีน้ำหนักเท่ากับ $d(i,j)=d(s_(i),s_(j))$

หากให้ $TSP(G_(S))$ เป็นน้ำหนักรวมของ Hamiltonian cycle ที่มีน้ำหนักน้อยที่สุดของ $G_(S)$ จะได้ว่า $TSP(G_(S))<=OPT(S)$ เนื่องจากการวน superstring ใดๆให้ได้ Hamiltonian cycle อาจจะมีการซ้อนทับระหว่าง string ตัวแรกและตัวสุดท้ายซึ่งจะทำให้น้ำหนักของ Hamiltonian cycle น้อยลงกว่าความยาวเต็มๆของ superstring นั้น

แต่เนื่องจาก TSP ก็เป็นปัญหาที่ยากอยู่เช่นเดียวกัน เราจึงคิดเชื่อมโยงกับปัญหาอื่นที่ง่ายกว่า สามารถแก้ได้ใน Polynomial time ซึ่งก็คือ CCP ( Cycle Cover Problem ) ซึ่งต้องการจะแบ่งกราฟเป็น cycle ย่อยๆ โดยที่ทุกๆจุดยอดจะอยู่ในหนึ่ง cycle เสมอ และให้ผมรวมของน้ำหนักของทุกๆ cycle น้อยที่สุด หากให้ $CYC(G_(S))$ เป็นน้ำหนักของ minimum cycle cover ของกราฟ $G_(S)$ เราจะได้ว่า $CYC(G_(S))<=TSP(G_(S))<=OPT(S)

คราวหน้าเราจะใช้ความรู้ตรงนี้ เพื่อที่จะแสดงและพิสูจน์ $4*OPT(S)$ Approximation Algorithm ให้เห็นกัน