最大配對導出子圖的正確解演算法

An Exact Algorithm for the Maximum Induced Matching Problem

繆朝安(Chau-An Miau)

指導教授 ： 張貿翔

國立中正大學/工學院/資訊工程學系/碩士(2012年)

摘要

在一個無向圖 G=(V,E) 中，最大r規則導出子圖問題(Maximum r-regular Induced Subgraph Problem)是在點集合V中找出一個最大的子集合R，使得R所形成的導出子圖(G[R])為一個r規則圖，而配對導出子圖(Induced Matching)則是圖G的一個導出子圖，並且滿足每個導出子圖中的點度數(degree)都為1，最大配對導出子圖問題(Maximum Induced Matching Problem)就是需要找出最大的配對導出子圖。根據定義，最大配對導出子圖問題相同於最大1規則導出子圖問題。 Gupta等人提出了時間複雜度為o(2^n)的演算法來解最大r規則導出子圖問題。此演算法可以在O^*(1.6957^n)下解最大配對導出子圖問題，時間複雜度中的n為點的個數。在論文中，我們展示了最大配對導出子圖問題可以轉換到最大獨立集合問題上，並提出更有效率的演算法可以在O^*(14786^n)的時間複雜度下解決最大配對導出子圖問題。

關鍵字

正確解演算法 ； r規則圖 ； 配對導出子圖

並列摘要

Given a graph G = (V,E) the MAXIMUM r-REGULAR INDUCED SUBGRAPH problem is to find a vertex set R ⊆ V of maximum cardinality such that G[R] is r-regular. An induced matching M ⊆ E in a graph G = (V,E) is a matching such that no two edges in M are joined by any third edge of the graph. The MAXIMUM INDUCED MATCHING problem is to find an induced matching of maximum cardinality. By definition the maximum induced matching problem is the maximum 1-regular induced subgraph problem. Gupta et al. gave an o(2^n) time algorithm for solving the MAXIMUM r-REGULAR INDUCED SUBGRAPH problem. This algorithm solves the MAXIMUM INDUCED MATCHING problem in O^∗(1.6957^n) where n is the number of vertices in the input graph. In this thesis, we show that the maximum induced matching problem can be reduced to the maximum independent set problem and we give a more efficient algorithm for the MAXIMUM INDUCED MATCHING problem running in time O^∗(1.4786^n).

並列關鍵字

r-regular Induced subgraph ； Maximum Induced Matching ； exact algorithm

參考文獻

[2] K. Cameron, Induced matching, Discrete Applied Mathematics, 24 (1989), pp. 97–102.

[3] M.C. Golumbic, R.C. Laskar, Irredundancy in circular arc graphs, Discrete Appl. Math., 44 (1993), pp. 79–89.

[4] C. W. Ko and F. B. Shepherd, Bipartite domination and simultaneous matroid cover, SIAM Journal on Discrete Mathematics, 16 (2003), pp. 327–346.

[5] K. Cameron, R. Sritharan, and Y. Tang, Finding a maximum induced matching in weakly chordal graphs, Discrete Mathematics, 266 (2003), pp. 133–142.

[6] L. J. Stockmeyer and V. V. Vazirani, NP-completeness of some generalizations of the maximum matching problem, Information Processing Letters, 15 (1982), pp. 4–19.