關(guān)于二部圖上的顏色最多獨立集問題

周 圓，陳光亭，陳 永，張 安

(1.杭州電子科技大學(xué)理學(xué)院，浙江 杭州 310018；2.臺州學(xué)院電子與信息工程學(xué)院，浙江 臺州 318000)

0 引 言

頂點著色圖在多個學(xué)科領(lǐng)域有著十分重要的作用，文獻(xiàn)[1]介紹了其在生物信息學(xué)中的應(yīng)用。文獻(xiàn)[2]給出了在一般圖中找最大獨立集問題是NP-hard。文獻(xiàn)[3]提出限制奇偶度時的有界度圖上的近似算法，對于一些特殊的圖，文獻(xiàn)[4-6]分別提出在無爪圖(claw-free graph)、無P5路的圖(P5-free graph)和完美圖(perfect graph)中，尋找最大獨立及問題(Maximum Independent Problem，MIP)是多項式時間內(nèi)可解的，文獻(xiàn)[7]提出，對于余圖(cograph)和弦圖(chordal graph)，可在線性時間內(nèi)解出MIP問題。當(dāng)前對顏色數(shù)最多的獨立集問題(Maximum Colorful Independent Set Problem，MCISP)的研究中，文獻(xiàn)[8]提出聚類圖(cluster grpah)和樹(tree)中的MCISP問題是多項式時間內(nèi)可解并給出相關(guān)算法，而在無P5路(P5-free graph)圖和余圖(cogrpah)中，求解MCISP問題是NP-hard。

1 一般二部圖上的MCISP問題

定義1給定任意圖G=(V,E)，將圖G中的頂點集V分為兩部分，分別是V1和V2且V1和V2都是獨立集，圖G中的邊集E由V1中的頂點到V2中的頂點的連線組成的圖稱為二部圖[10],記作G=(V1,V2,E)。

定義2給定任意二部圖G=(V1,V2,E)，V1中的每一個頂點與V2中的每一個頂點之間都有邊的圖稱為完全二部圖[10]，記作KV1,V2。

定義3給定任意二部圖G=(V1,V2,E)和顏色集C，使得G中每個頂點都著有C中至少一種顏色的圖為頂點著色圖[8]，其中C中的顏色由自然數(shù)N表示，不同的自然數(shù)i表示不同的顏色，i∈N。|C(Vi)|表示不同集合的不同顏色數(shù)，i∈{1,2}，記作Gc=(V1,V2,E)。

對于任意給定的頂點著色二部圖Gc=(V1,V2,E)，在圖G上找到一個包含G中頂點顏色數(shù)最多的獨立集S，其中集合S記作算法解得到的不同顏色頂點組成的集合，S*表示最優(yōu)解中顏色不同的頂點組成的集合，這一問題叫做二部圖上的MCISP問題。

下面給出求解MCISP問題的一個多項式時間近似算法。

算法1:一般二部圖上的近似算法輸入:1個簡單二部圖Gc=(V1,V2,E)輸出:Gc中包含顏色最多的獨立集S步驟:令S=?,比較集合V1與V2中的顏色種類,若C(V1)≥C(V2),則令S=V1,否則令S=V2,結(jié)束算法。

定理1算法1的最差情況界為2且是緊的。

證明不妨假設(shè)C(V1)≥C(V2)，即S=C(V1)，則由二部圖的性質(zhì)知，C(V1)+C(V2)≥S*，從而2C(V1)≥S*，故2S≥S*。證畢。

圖1 算法1的緊例

2 完全二部圖塊上的MCISP問題

給定任意的完全二部圖塊Gc=(U,V,E)和顏色集C，i∈{1,2,…,n}。G中恰有3個頂點著有相同顏色且每一個Gi中的頂點顏色都不同，此時在G中找到一個獨立集S并使得其中所包含的顏色種類最多。這一問題是完全二部圖塊上的MCISP問題。

下面給出求解MCISP問題的多項式時間近似算法。

算法2:完全二部圖塊上的近似算法 輸入:1個簡單完全二部圖塊Gc=(U,V,E)輸出:G中包含顏色最多的獨立集S步驟1:令S=?,從任意的完全二部子圖Gcii=(U,V,E)開始,其中i∈{1,2,…,n}。比較Gcii中的頂點集Ui和Vi,當(dāng)C(Ui)≥C(Vi)時,令S=Ui,反之令S=Vi;步驟2:對每個Gcrr,比較Gcrr中Ur和Vr可在當(dāng)前S中增加的顏色類,當(dāng)C(Ur∪S)≥C(Vr∪S)時,令S=Ur∪S。反之令S=Vr∪S。其中r≠i,r=1,2,…,n。結(jié)束算法。

當(dāng)A=?時，S=S*，結(jié)論成立；

當(dāng)A≠?時，假設(shè)A中至少存在一個頂點αmp，使得αmp至多對應(yīng)于S中2個顏色不同的頂點。其中m,t,p,q∈{1,2,…,n}，m,t表示顏色不同的頂點，p,q表示其所在二部圖分支被選入集合S中的順序。

若αmp對應(yīng)于S中0個頂點，但αmp與A中至少一個頂點αtq所對應(yīng)的顏色在同一個二部圖分支中但p≤q，此時顏色是C(αmp)的頂點所在的原二部圖分支中，除C(αmp)之外只包含C(S)中的顏色，即這些顏色在這一二部圖分支之前已被選入C(S)中，則由算法2可知，C(αmp)∈C(S)與A的定義矛盾。若顏色是C(αmp)的頂點與C(S)中的顏色所在頂點均不在同一二部圖分支上，則顏色是C(αmp)的頂點與顏色是C(S)的頂點在不同的二部圖分支上，此時可向S中添加包含新顏色的點或者C(αmp)∈C(S)，與S是算法2的解矛盾。

若αmp對應(yīng)于S中1個頂點，當(dāng)αmp與A中某些頂點對應(yīng)于相同顏色的頂點，同理可得，則至少有一個與αmp顏色相同的頂點所在的二部圖分支，使得這個二部圖分支中其它頂點的顏色已對應(yīng)于A中某些頂點，即這些頂點所著顏色已被選入S。故由算法2得出C(αmp)∈(S)，與S是算法2的解矛盾。若αmp與A中所有頂點所對應(yīng)顏色都不同，而C(αmp)這一顏色恰在原圖中出現(xiàn)3次，則此時必至少有一個C(αmp)所在的二部圖分支中所包含顏色均不在其中，與S是算法2的解矛盾。

若αmp對應(yīng)于S中2個頂點，則C(αmp)所在原二部圖分支中，要么恰有一個顏色是C(αmp)的頂點所在二部圖分支，使得算法2運行到這一個二部圖分支時，包含了此時C(S)中兩種尚無對應(yīng)的不同顏色的頂點。要么只有兩種顏色是C(αmp)的頂點所在的二部圖分支在當(dāng)前算法2運行到這兩個二部圖分支時，各對應(yīng)了此時C(S)中不同顏色所在的頂點。若αmp與A中某些頂點所對應(yīng)的顏色相同，同理可得，則必至少有一個αmp或與αmp顏色相同的頂點所在的二部圖分支中只有已選入S中的點，與S是算法2的解矛盾。當(dāng)αmp與A中其它任意一個頂點所對應(yīng)頂點顏色都不相同時，同理可得，與S是算法2的解矛盾。即f:A→S且A中每個頂點在對應(yīng)關(guān)系f下至少映S中3個頂點，3|A|≤|S|≤|S*|。

圖2 算法2的緊例

3 結(jié)束語