2-Club簇圖頂點(diǎn)刪除問(wèn)題改進(jìn)參數(shù)算法

譚冠蘭，孫龍志，馮啟龍，鄭瑩，譚培強(qiáng)

?

2-Club簇圖頂點(diǎn)刪除問(wèn)題改進(jìn)參數(shù)算法

譚冠蘭1，孫龍志1，馮啟龍1，鄭瑩2，譚培強(qiáng)1

(1. 中南大學(xué) 信息科學(xué)與工程學(xué)院，湖南 長(zhǎng)沙，410083；2. 長(zhǎng)沙理工大學(xué) 計(jì)算機(jī)與通信與工程學(xué)院，湖南 長(zhǎng)沙，410083)

2-club簇圖修改問(wèn)題是經(jīng)典的NP難問(wèn)題。對(duì)通過(guò)對(duì)2-club簇圖修改問(wèn)題的參數(shù)算法進(jìn)行研究，提出簡(jiǎn)化問(wèn)題實(shí)例的若干規(guī)則?；趯?duì)2-club簇圖結(jié)構(gòu)的分析和提出的簡(jiǎn)化規(guī)則，并采用自頂向下的分支方法，提出時(shí)間復(fù)雜度為*(3.24)的固定參數(shù)算法，降低了目前求解該問(wèn)題的時(shí)間復(fù)雜度。

2-club；2-club簇圖頂點(diǎn)刪除；固定參數(shù)算法

-club 簇圖頂點(diǎn)刪除

輸入：無(wú)向圖=(，)，非負(fù)整數(shù)。

1 相關(guān)術(shù)語(yǔ)

參數(shù)計(jì)算不僅成為理論計(jì)算機(jī)科學(xué)的一個(gè)重要分支，而且在實(shí)際中也得到了廣泛應(yīng)用[16?19]。分支搜索樹(shù)在參數(shù)算法設(shè)計(jì)中有著廣泛應(yīng)用[15,20]。若參數(shù)為實(shí)例的求解是通過(guò)遞歸求解參數(shù)分別為?1，?2…，?d的子實(shí)例完成，則稱(1，2，…，d)為遞歸式的分支向量。分支搜索樹(shù)的大小是通過(guò)求解遞歸式()=(?1)+(?2)+…+(?d)得到的。設(shè)為此遞歸式的最大解，則稱為分支向量(1，…，d)的分支數(shù)，并用*()表示分支搜索樹(shù)的大小。

2 簡(jiǎn)化規(guī)則

下面主要介紹2-club 簇圖頂點(diǎn)刪除算法中用到的一些簡(jiǎn)化規(guī)則。

引理1 圖的每個(gè)連通分量都是1個(gè)2-Club當(dāng)且僅當(dāng)圖的每個(gè)導(dǎo)出子圖中都不含有嚴(yán)格4。

證明：假設(shè)stuv為圖中任意1條長(zhǎng)度為3的路徑，則stuv肯定被包含在圖的某個(gè)連通分量中，因?yàn)槁窂絪tuv是連通的。由于圖中的每1個(gè)連通分量是1個(gè)2-Club，所以，中任意2點(diǎn)之間或者有邊相連或者有公共鄰居，則路徑stuv的邊界頂點(diǎn)和之間或者有邊相連或者有公共鄰居。根據(jù)嚴(yán)格4的定義，路徑stuv并不是1條嚴(yán)格4。因?yàn)槁窂絪tuv是中長(zhǎng)度為3的任意路徑，且是圖的任意1個(gè)連通分量，所以，圖中每個(gè)連通分量中都不含有嚴(yán)格4作為其導(dǎo)出子圖，即圖的每個(gè)導(dǎo)出子圖中都不含有嚴(yán)格4。

假設(shè)為圖的任意1個(gè)連通分量，且和為中的任意2個(gè)頂點(diǎn)。假設(shè)和之間的最短路徑d(，)≥3，因?yàn)楹椭g是連通的，則和之間肯定存在1條長(zhǎng)度為3的路徑，設(shè)為staw(和以及和都有可能為1個(gè)頂點(diǎn)，且d(s,w)=3。由于d(s,w)=3，故和之間沒(méi)有公共頂點(diǎn)。根據(jù)嚴(yán)格4的定義，staw為1條嚴(yán)格4，這與圖的導(dǎo)出子圖中不含有嚴(yán)格4相矛盾，所以，中任意2個(gè)頂點(diǎn)之間的最短距離小于等于2。根據(jù)2-Club的定義，是1個(gè)2-Club。又因?yàn)槭菆D中的任意1個(gè)連通分量，故圖的每個(gè)連通分量都是1個(gè)2-Club。所以，圖是1個(gè)2-Club簇圖。

根據(jù)引理1，只要將圖中所有的嚴(yán)格4破壞，則圖中的每個(gè)連通分量都是1個(gè)2-Club。由于2-Club不具有遺傳性質(zhì)(具有遺傳性質(zhì)的圖定義為假設(shè)圖具有某種性質(zhì)，若圖的任意導(dǎo)出子圖也滿足性質(zhì)Π，則認(rèn)為圖具有遺傳性質(zhì))，所以，當(dāng)刪除一條嚴(yán)格4中的某個(gè)頂點(diǎn)時(shí)，原始圖有可能會(huì)產(chǎn)生新的嚴(yán)格4。為了得到時(shí)間復(fù)雜度更低的固定參數(shù)可解算法，將圖中的頂點(diǎn)染為白色頂點(diǎn)和黑色頂點(diǎn)。起初將圖中所有的頂點(diǎn)染為白色頂點(diǎn)，若能確定某個(gè)頂點(diǎn)肯定不會(huì)被放入解集中，則將該頂點(diǎn)染為黑色。因此，白色頂點(diǎn)意味著不能確定是否放入解集中的頂點(diǎn)，黑色頂點(diǎn)意味著肯定不會(huì)被放入解集中的頂點(diǎn)。

定義1 令和是圖中的任意2個(gè)頂點(diǎn)。若和同時(shí)滿足以下2個(gè)條件，則稱支配：

1) 刪除不會(huì)產(chǎn)生新的嚴(yán)格4。

2) 包含的嚴(yán)格4同時(shí)也包含。

引理2 令(，)是2-Club簇圖頂點(diǎn)刪除問(wèn)題的1個(gè)實(shí)例，若頂點(diǎn)和都是圖中某條嚴(yán)格4的白色頂點(diǎn)并且支配，則存在1個(gè)最優(yōu)解不含頂點(diǎn)。

證明：由于支配，故刪除點(diǎn)破壞的嚴(yán)格4的數(shù)目不會(huì)少于刪除點(diǎn)破壞的嚴(yán)格4的數(shù)目，包含的解都可以用來(lái)代替來(lái)形成1個(gè)更優(yōu)的解，所以，頂點(diǎn)不會(huì)在解中。

基于引理2，可得出以下規(guī)則。

規(guī)則1 若頂點(diǎn)和都是圖某條嚴(yán)格4中的白色頂點(diǎn)并且支配，則將頂點(diǎn)染為黑色。

引理3 令(，)是2-Club簇圖頂點(diǎn)刪除問(wèn)題的1個(gè)實(shí)例，是實(shí)例(，)的1個(gè)解。若圖中存在1條嚴(yán)格4，且中只剩下1個(gè)頂點(diǎn)沒(méi)有被染為黑色，則頂點(diǎn)肯定在解中。

證明：由于除了頂點(diǎn)沒(méi)被染為黑色，中其他3個(gè)點(diǎn)都被染為黑色，這意味著其他3個(gè)點(diǎn)都不可能在解中。為了破壞，必須將頂點(diǎn)放在解集中。

基于引理3，可得出以下規(guī)則。

規(guī)則2 假設(shè)為圖中的一條嚴(yán)格4，且中只剩下1個(gè)頂點(diǎn)沒(méi)有被染為黑色，則將頂點(diǎn)放入解集中，并將頂點(diǎn)從圖中刪除，同時(shí)將減1。

引理4 假設(shè)，為中的2條嚴(yán)格4，且中的白色頂點(diǎn)集合是中白色頂點(diǎn)集合的子集，則將標(biāo)記為已刪除。

證明：假設(shè)是集合中的白色頂點(diǎn)，因?yàn)槭亲蛹?，所以，也是中的頂點(diǎn)。當(dāng)刪除頂點(diǎn)時(shí)，會(huì)被破壞。同時(shí)，也會(huì)被破壞。這表明破壞的同時(shí)會(huì)自動(dòng)破壞所以，可以將標(biāo)記為已刪除。

基于引理4，可得出以下規(guī)則。

規(guī)則3 假設(shè)，為圖的2條嚴(yán)格4，且中的白色頂點(diǎn)集合是中白色頂點(diǎn)集合的子集，則將標(biāo)記為已刪除。

當(dāng)圖應(yīng)用這3條規(guī)則后，原實(shí)例(，)中所有的嚴(yán)格4中的頂點(diǎn)有的已經(jīng)被染為黑色。所以，在應(yīng)用分支搜索技術(shù)時(shí)，可以不考慮這些已經(jīng)被染為黑色的頂點(diǎn)，而只考慮那些白色的頂點(diǎn)。將嚴(yán)格4中白色頂點(diǎn)的個(gè)數(shù)定義為這條嚴(yán)格4的大小。

3 參數(shù)算法設(shè)計(jì)和分析

3) 若stuv不屬于{1，2，3，4}結(jié)構(gòu)中的任何一種，則稱stuv為5結(jié)構(gòu)。

引理5 若圖中不存在{1，2，3，4}結(jié)構(gòu)，則圖中每條嚴(yán)格4中至少存在3個(gè)頂點(diǎn)的并且這三個(gè)頂點(diǎn)的優(yōu)先級(jí)都至少為2。

證明：設(shè)stuv為圖中的1條嚴(yán)格4。由于圖中不存在{1，2，3，4}結(jié)構(gòu)，故stuv屬于5結(jié)構(gòu)，并且符合以下情況中的一種情況。

(C1) 若與之間沒(méi)有公共鄰居且與相鄰，則{，，}被stuv和stwv這2條嚴(yán)格4包含。

(C2) 若與之間沒(méi)有公共鄰居，與不相鄰且與相鄰，則{，，}被stuv和stuw這2條嚴(yán)格4包含。

(C3) 若{，}與不相鄰且{，}與沒(méi)有公共鄰居，則{，，}被stwv和tuwv這2條嚴(yán)格4包含。

在分支時(shí)，本文總是優(yōu)先選擇較小嚴(yán)格4中的頂點(diǎn)進(jìn)行分支。在刪除5結(jié)構(gòu)的嚴(yán)格4時(shí)，算法根據(jù)不同的情況選擇不同的頂點(diǎn)進(jìn)行分支，一般選取某個(gè)頂點(diǎn)子集中優(yōu)先級(jí)最大的白色頂點(diǎn)進(jìn)行分支(具體選擇哪個(gè)頂點(diǎn)進(jìn)行分支，會(huì)在算法的時(shí)間復(fù)雜度分析過(guò)程中體現(xiàn))，并稱此類頂點(diǎn)為關(guān)鍵點(diǎn)。

若當(dāng)前圖中存在{1，2，3，4}結(jié)構(gòu)，利用常規(guī)的自底向上的分支搜索技術(shù)將其破壞，直到圖中不存在{1，2，3，4}結(jié)構(gòu)為止，則當(dāng)前圖中剩下的所有嚴(yán)格4都不屬于{1，2，3，4}中的某種結(jié)構(gòu)。然后，對(duì)圖應(yīng)用規(guī)則1~規(guī)則3，則圖中有的嚴(yán)格4中的頂點(diǎn)被染為黑色，然后遞歸的刪除5結(jié)構(gòu)。在刪除5結(jié)構(gòu)時(shí)，若圖中產(chǎn)生屬于{1，2，3，4}結(jié)構(gòu)的嚴(yán)格4，則首先將其刪除。算法的具體過(guò)程如圖2所示。

算法：B2CVD(G, S, k)輸入：圖G=(V，E)，集合S和非負(fù)整數(shù)k。輸出：若圖G中存在大小不超過(guò)k的集合，使得G[VS]的每個(gè)連通分量是2-Club，則輸出S，否則輸出 “NO”。1. 若當(dāng)前圖G中存在{Γ1，Γ2，Γ3，Γ4}結(jié)構(gòu)的嚴(yán)格P4，對(duì)其進(jìn)行分支，將相應(yīng)的分支頂點(diǎn)放入解集S中，k減去相應(yīng)分支節(jié)點(diǎn)的個(gè)數(shù)，直到當(dāng)前圖G中不存在{Γ1，Γ2，Γ3，Γ4}結(jié)構(gòu)的嚴(yán)格P4為止；2. 對(duì)圖G應(yīng)用規(guī)則1~規(guī)則3；3. 找到圖G中所有沒(méi)有被標(biāo)記且結(jié)構(gòu)為Γ5的嚴(yán)格P4，放入集合P；4. if k＞0 then4.1. if then return S;4.2 找到圖G中的關(guān)鍵點(diǎn)x；4.3 ；4.4 S′=B2CVD (G[V {x}], S{x}, k?1);4.5 if S′=“NO” then 將頂點(diǎn)x著為黑色; S′ = B2CVD (G[V], S, k);4.6 return S′;5. else5.1 if or k＜0 then return “NO”;5.2 else return S;

引理6 令stuv為圖中的1條嚴(yán)格4。若stuv屬于{1，2，3，4}中的任意一種結(jié)構(gòu)，則算法B2CVD可以在*(3.24)時(shí)間內(nèi)將stuv破壞。

證明：根據(jù)定義2，可以得到以下4種情況。

情況1：當(dāng)stuv為1結(jié)構(gòu)時(shí)，為了破壞stuv，可以分別對(duì){{}，{}}進(jìn)行分支，則分支向量為(1，1)，分支數(shù)≤2。

綜合以上4種情況，算法B2CVD可以在*(3.24)時(shí)間內(nèi)將stuv破壞。

2-Club簇圖頂點(diǎn)刪除問(wèn)題的固定參數(shù)可解算法見(jiàn)圖2。

引理8

引理9

證明：對(duì)2()分以下3種情況進(jìn)行分析。

1()和2()取不同的值，共可以得到10個(gè)不等式方程組。下面就其中1個(gè)不等式方程組進(jìn)行求解：

將2()用0()?0(?1)代替，則以下式子成立：

引理10 若圖中不存在{1，2，3，4}結(jié)構(gòu)，則可以在*(3.24)時(shí)間內(nèi)將圖中5結(jié)構(gòu)的嚴(yán)格4破壞。

定理給定2-Club簇圖頂點(diǎn)刪除問(wèn)題的1個(gè)實(shí)例(，，)，若存在大小不超過(guò)的解集，則算法B2CVD(，，)必定在*(3. 24)時(shí)間內(nèi)返回解集，否則返回“NO”。

證明：假設(shè)給定2-Club簇圖頂點(diǎn)刪除問(wèn)題的1個(gè)實(shí)例(，，)，為了將圖轉(zhuǎn)化為2-Club 簇圖，根據(jù)引理1，算法必須破壞圖中所有的嚴(yán)格4。算法首先將圖中的嚴(yán)格4分為2種：屬于{1，2，3，4}結(jié)構(gòu)的嚴(yán)格4和5結(jié)構(gòu)的嚴(yán)格4。針對(duì)不同結(jié)構(gòu)的嚴(yán)格4，算法采用不同的分支搜索技術(shù)將其破壞。算法執(zhí)行第1步時(shí)，若圖中存在{1，2，3，4}結(jié)構(gòu)的嚴(yán)格4，則可以利用引理6的分支方法將其破壞掉并且此步操作是正確的。算法執(zhí)行完第1步，圖中只存在5結(jié)構(gòu)的嚴(yán)格4，則算法下一步就是將圖中5結(jié)構(gòu)的嚴(yán)格4破壞。算法執(zhí)行第2步，則對(duì)圖應(yīng)用規(guī)則1~規(guī)則3，并且根據(jù)引理2~引理4，這步操作也是正確的。算法第3步將圖中所有沒(méi)有被標(biāo)記為刪除的嚴(yán)格4放入集合中。算法執(zhí)行第4.1步時(shí)，若集合為空且＞0，則說(shuō)明算法可以通過(guò)刪除少于個(gè)頂點(diǎn)將圖中所有的嚴(yán)格4刪除，因此，可以返回解集。若集合不為空且＞0，則圖中仍然存在5結(jié)構(gòu)的嚴(yán)格4，根據(jù)啟發(fā)式規(guī)則，找出當(dāng)前的關(guān)鍵頂點(diǎn)進(jìn)行分支。算法第4.4步和4.5步分別對(duì)頂點(diǎn)是否放在解集中進(jìn)行分支，遞歸調(diào)用B2CVD()算法，直到求出解集或者不存在解集為止。由引理10可知對(duì)的分支是正確的。算法第5.1步表示，若=0且圖中仍然存在嚴(yán)格4或者＜0，則算法不可能通過(guò)刪除個(gè)點(diǎn)將圖中的所有嚴(yán)格4刪除，所以返回“NO”。算法第5.2步表示，=0且圖中沒(méi)有嚴(yán)格4，則算法恰好通過(guò)刪除個(gè)點(diǎn)將圖中所有嚴(yán)格4破壞，因此，圖2所示的算法是正確的。

由引理6和引理10可知，刪除嚴(yán)格4的最壞時(shí)間復(fù)雜度都為*(3.24)，因此，整個(gè)算法的時(shí)間復(fù)雜度為*(3.24)。

4 結(jié)論

1) 對(duì)2-Club簇圖頂點(diǎn)刪除問(wèn)題采用分支搜索技術(shù)進(jìn)行分支，并提出相應(yīng)的簡(jiǎn)化規(guī)則，得出時(shí)間復(fù)雜度為*(3.24)的固定參數(shù)可解算法。

2) 2-club簇圖修改問(wèn)題的3個(gè)問(wèn)題仍然沒(méi)有給出多項(xiàng)式核或證明沒(méi)有多項(xiàng)式核。這3個(gè)問(wèn)題是否具有多項(xiàng)式核仍有待研究。

[1] XU R, WUNSCH D. Survey of clustering algorithms[J]. IEEE Transactions on Neural Networks, 2005, 16(3): 645?678.

[2] BANSAL N, BLUM A, CHAWLA S. Correlation clustering[J]. Machine Learning, 2004, 56(1): 89?113.

[3] SHAMIR R, SHARAN R, TSUR D. Cluster graph modification problems[J]. Discrete Applied Mathematics, 2004, 144(1): 173?182.

[4] LUCE R D. Connectivity and generalized cliques in sociometric group structure[J]. Psychometrika, 1950, 15(2): 169?190.

[5] LIU H, ZHANG P, ZHU D. On editing graphs into 2-club clusters[C]//Proc Frontiers in Algorithmics and Algorithmic Aspects in Information and Management, FAW-AAIM 2012, LNCS 7285. Beijing, 2012: 235?246.

[6] GUO J, KANJ I A, KOMUSIEWICZ C, et al. Editing graphs into disjoint unions of dense clusters[J]. Algorithmica, 2011, 61(4): 949?970.

[7] GUO J, KOMUSIEWICZ C, NIEDERMEIER R, et al. A more relaxed model for graph-based data clustering:s-plex cluster editing[J]. SIAM Journal on Discrete Mathematics, 2010, 24(4): 1662?1683.

[8] SHAHINPOUR S, BUTENKO S. Algorithms for the maximum k-club problem in graphs[J]. Journal of Combinatorial Optimization, 2012, 26(3): 1?35.

[9] MAHDAVI PAJOUH F, BALASUNDARAM B. On inclusionwise maximal and maximum cardinality k-clubs in graphs[J]. Discrete Optimization, 2012, 9(2): 84?97.

[10] BOURJOLLY J M, LAPORTE G, PESANT G. An exact algorithm for the maximum k-club problem in an undirected graph[J]. European Journal of Operational Research, 2002, 138(1): 21?28.

[11] SCH?FER A, KOMUSIEWICZ C, MOSER H, et al. Parameterized computational complexity of finding small-diameter subgraphs[J]. Optimization Letters, 2012, 6(5): 883?891.

[12] HARTUNG S, KOMUSIEWICZ C, NICHTERLEIN A. parameterized algorithmics and computational experiments for finding 2-Clubs[C]//Proceeding 7th International Symposium on Parameterized and Exact Computation, IPEC 2012, LNCS 7535, Ljubljana, Springer, 2012: 231?241.

[13] HARTUNG S, KOMUSIEWICZ C, NICHTERLEIN A. On structural parameterizations for the 2-Club problem[C]// Proceeding 39th International Conference on Current Trends in Theory and Practice of Computer Science. Spindleruv: Springer, 2013: 233?243.

[14] FERNAU H. Parameterized algorithms for hitting set: the weighted case[J]. Theoretical Computer Science, 2010, 411(16): 1698-1713.

[15] CYGAN M. Deterministic parameterized connected vertex cover[C]//Proceeding 13th International Scandinavian Symposium and Workshops on Algorithm Theory. Helsinki: Springer, 2012: 95?106.

[16] COHEN D, CRAMPTON J, GAGARIN A, et al. Iterative plan construction for the workflow satisfiability problem[J]. Journal of Artificial Intelligence Research, 2014, 51(3): 555?577.

[17] GUTIN G, KRATSCH S, WAHLSTR?M M. Polynomial kernels and user reductions for the workflow satisfiability problem[C]//Proceeding 9th International Symposium on Parameterized and Exact Computation. Wroclaw: Springer, 208?220.

[18] ABU-KHZAM F N, EGAN J, FELLOWS M R, et al. On the parameterized complexity of dynamic problems[J]. Theoretical Computer Science, 2015, 607(3): 426?434.

[19] JANSEN B M P, KRATSCH S. A structural approach to kernels for ILPs: treewidth and total unimodularity[C]//Proceeding 23rd European Symposium on Algorithm. Patras: Springer, 2015: 779?791.

[20] NIEDERMEIER R. Invitation to fixed-parameter algorithms[M]. Habilitationschrift: University of Tübingen, 2002: 1?30.

(編輯 陳燦華)

Improved algorithm for 2-club cluster vertex deletion

TAN Guanlan1, SUN Longzhi1, FENG Qilong1, ZHENG Ying2, TAN Peiqiang1

(1. School of Information Science and Engineering, Central South University, Changsha 410083, China;2. School of Computer and Communication Engineering,Changsha University of Science & Technology, Changsha 410083, China)

2-club cluster graph modification problems are classical NP-hard problems. The parameterized algorithms were studied for the 2-club cluster graph modification problems, and several reduction rules were presented to reduce the size of input instance. Based on the structure analysis of the 2-club cluster graph and the reduction rules presented, by applying a top-down approach, a fixed-parameterized algorithm with running time(3.24) was presented, which improves the current algorithm solving the 2-club cluster graph modification problems.

2-club; 2-club cluster vertex deletion; fixed-parameterized algorithm

10.11817/j.issn.1672?7207.2018.02.015

TP301

A

1672?7207(2018)02?0371?07

2017?02?10；

2017?04?15

國(guó)家自然科學(xué)基金資助項(xiàng)目(61472449, 61370172, 61402054)(Projects (61472449, 61370172, 61402054) supported by the National Natural Science Foundation of China)

馮啟龍，博士，副教授，從事計(jì)算機(jī)算法研究；E-mail：csufeng@csu.edu.cn