譚冠蘭，孫龍志，馮啟龍，鄭瑩，譚培強

?

2-Club簇圖頂點刪除問題改進參數算法

譚冠蘭1，孫龍志1，馮啟龍1，鄭瑩2，譚培強1

(1. 中南大學 信息科學與工程學院，湖南 長沙，410083；2. 長沙理工大學 計算機與通信與工程學院，湖南 長沙，410083)

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

2-club；2-club簇圖頂點刪除；固定參數算法

-club 簇圖頂點刪除

輸入：無向圖=(，)，非負整數。

1 相關術語

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

2 簡化規(guī)則

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

引理1 圖的每個連通分量都是1個2-Club當且僅當圖的每個導出子圖中都不含有嚴格4。

證明：假設stuv為圖中任意1條長度為3的路徑，則stuv肯定被包含在圖的某個連通分量中，因為路徑stuv是連通的。由于圖中的每1個連通分量是1個2-Club，所以，中任意2點之間或者有邊相連或者有公共鄰居，則路徑stuv的邊界頂點和之間或者有邊相連或者有公共鄰居。根據嚴格4的定義，路徑stuv并不是1條嚴格4。因為路徑stuv是中長度為3的任意路徑，且是圖的任意1個連通分量，所以，圖中每個連通分量中都不含有嚴格4作為其導出子圖，即圖的每個導出子圖中都不含有嚴格4。

假設為圖的任意1個連通分量，且和為中的任意2個頂點。假設和之間的最短路徑d(，)≥3，因為和之間是連通的，則和之間肯定存在1條長度為3的路徑，設為staw(和以及和都有可能為1個頂點，且d(s,w)=3。由于d(s,w)=3，故和之間沒有公共頂點。根據嚴格4的定義，staw為1條嚴格4，這與圖的導出子圖中不含有嚴格4相矛盾，所以，中任意2個頂點之間的最短距離小于等于2。根據2-Club的定義，是1個2-Club。又因為是圖中的任意1個連通分量，故圖的每個連通分量都是1個2-Club。所以，圖是1個2-Club簇圖。

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

定義1 令和是圖中的任意2個頂點。若和同時滿足以下2個條件，則稱支配：

1) 刪除不會產生新的嚴格4。

2) 包含的嚴格4同時也包含。

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

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

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

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

引理3 令(，)是2-Club簇圖頂點刪除問題的1個實例，是實例(，)的1個解。若圖中存在1條嚴格4，且中只剩下1個頂點沒有被染為黑色，則頂點肯定在解中。

證明：由于除了頂點沒被染為黑色，中其他3個點都被染為黑色，這意味著其他3個點都不可能在解中。為了破壞，必須將頂點放在解集中。

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

規(guī)則2 假設為圖中的一條嚴格4，且中只剩下1個頂點沒有被染為黑色，則將頂點放入解集中，并將頂點從圖中刪除，同時將減1。

引理4 假設，為中的2條嚴格4，且中的白色頂點集合是中白色頂點集合的子集，則將標記為已刪除。

證明：假設是集合中的白色頂點，因為是子集，所以，也是中的頂點。當刪除頂點時，會被破壞。同時，也會被破壞。這表明破壞的同時會自動破壞所以，可以將標記為已刪除。

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

規(guī)則3 假設，為圖的2條嚴格4，且中的白色頂點集合是中白色頂點集合的子集，則將標記為已刪除。

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

3 參數算法設計和分析

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

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

證明：設stuv為圖中的1條嚴格4。由于圖中不存在{1，2，3，4}結構，故stuv屬于5結構，并且符合以下情況中的一種情況。

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

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

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

在分支時，本文總是優(yōu)先選擇較小嚴格4中的頂點進行分支。在刪除5結構的嚴格4時，算法根據不同的情況選擇不同的頂點進行分支，一般選取某個頂點子集中優(yōu)先級最大的白色頂點進行分支(具體選擇哪個頂點進行分支，會在算法的時間復雜度分析過程中體現)，并稱此類頂點為關鍵點。

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

算法：B2CVD(G, S, k)輸入：圖G=(V，E)，集合S和非負整數k。輸出：若圖G中存在大小不超過k的集合，使得G[VS]的每個連通分量是2-Club，則輸出S，否則輸出 “NO”。1. 若當前圖G中存在{Γ1，Γ2，Γ3，Γ4}結構的嚴格P4，對其進行分支，將相應的分支頂點放入解集S中，k減去相應分支節(jié)點的個數，直到當前圖G中不存在{Γ1，Γ2，Γ3，Γ4}結構的嚴格P4為止；2. 對圖G應用規(guī)則1~規(guī)則3；3. 找到圖G中所有沒有被標記且結構為Γ5的嚴格P4，放入集合P；4. if k＞0 then4.1. if then return S;4.2 找到圖G中的關鍵點x；4.3 ；4.4 S′=B2CVD (G[V {x}], S{x}, k?1);4.5 if S′=“NO” then 將頂點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條嚴格4。若stuv屬于{1，2，3，4}中的任意一種結構，則算法B2CVD可以在*(3.24)時間內將stuv破壞。

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

情況1：當stuv為1結構時，為了破壞stuv，可以分別對{{}，{}}進行分支，則分支向量為(1，1)，分支數≤2。

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

2-Club簇圖頂點刪除問題的固定參數可解算法見圖2。

引理8

引理9

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

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

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

引理10 若圖中不存在{1，2，3，4}結構，則可以在*(3.24)時間內將圖中5結構的嚴格4破壞。

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

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

由引理6和引理10可知，刪除嚴格4的最壞時間復雜度都為*(3.24)，因此，整個算法的時間復雜度為*(3.24)。

4 結論

1) 對2-Club簇圖頂點刪除問題采用分支搜索技術進行分支，并提出相應的簡化規(guī)則，得出時間復雜度為*(3.24)的固定參數可解算法。

2) 2-club簇圖修改問題的3個問題仍然沒有給出多項式核或證明沒有多項式核。這3個問題是否具有多項式核仍有待研究。

[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

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

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