請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/86005
標題: | 三個導出子圖演算法——完美圖、最短奇洞、非最短路徑 Improved Algorithms for Recognizing Perfect Graphs and Finding Shortest Odd Holes and Non-shortest Induced Paths |
作者: | Yung-Chung Chiu 邱允中 |
指導教授: | 呂學一(Hsueh-I Lu) |
關鍵字: | 完美圖,導出子圖,奇洞,導出路徑,非最短路徑,動態資料結構, Perfect graph,Induced subgraph,Odd hole,Induced path,Non-shortest path,Dynamic data structure, |
出版年 : | 2022 |
學位: | 碩士 |
摘要: | 判斷一張圖中是否包含某種導出子圖,在圖論以及演算法領域的許多重要成果都扮演了重要角色。其中一個具有高度代表性的例子是「完美圖的辨識問題」,也就是判定一張圖是否符合「每個導出子圖中,最大團的頂點數都等於該導出子圖的著色數。」2006 年 Chudnovsky、Robertson、Seymour 以及 Thomas 明了「完美圖定理」這個獲得 2009 年 Fulkerson Prize 殊榮的成果,解決 Berge 在 1960 年留下的猜想,確認「一張圖是完美圖若且唯若它和它的補圖都不包含任何奇洞」,其中一張圖的奇洞是該圖的一個長度至少五且為奇數的導出環。根據這個定理,Chudnovsky、Cornuéjols、Liu、Seymour 以及 Vušković提出了一個時間複雜度為 O(n^9) 演算法來辨認完美圖,其中 n 表示圖的節點數。在此篇論文中,我們改進了三個偵測/找一張有 n 節點的圖 G 的導出子圖的演算法。分別說明如下: 1. 是否存在一個多項式時間演算法來偵測「G 否包含奇洞」在長達數十年期間一直是無人能解的懸案。Chudnovsky、Scott、Seymour 以及 Spirkl 終於在 Journal of the ACM 2020年提出了第一個多項式時間偵測 G 的奇洞的演算法,時間複雜度為 O(n^9)。Lai、Lu以及 Thorup 之後在 ACM STOC 2020 進到 O(n^8),我們則進一步改進到 O(n^7),從而也把辨識完美圖的的時間複雜度改進到 O(n^7)。 2. Chudnovsky、Scott 以及 Seymour 在 ACM Transactions on Algorithms 2021 年提出了第一個多項式時間尋找 G 最短奇洞的演算法,時間複雜度為 O(n^14)。我們將其改進到O(n^13)。 3. Berger、Seymour 以及 Spirkl 在 Discrete Mathematics 2021 年提出了第一個尋找 G 給 定兩點之間非最短導出路徑的演算法,時間複雜度為 O(n^18)。我們將其大幅度改進 到 O(n^4.75)。這第三個成果已經發表在 Proceedings of the 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)。 An induced subgraph of an n-vertex graph G is a graph that can be obtained by deleting a set of vertices together with its incident edges from G. A hole of G is an induced cycle of G with length at least four. A hole is odd (respectively, even) if its number of edges is odd (respectively, even). Various classes of induced subgraphs are involved in the deepest results of graph theory and graph algorithms. A prominent example concerns the perfection of G that the chromatic number of each induced subgraph H of G equals the clique number of H. The seminal Strong Perfect Graph Theorem proved in 2006 by Chudnovsky, Robertson, Seymour, and Thomas, conjectured by Berge in 1960, confirms that the perfection of G can be determined by detecting odd holes in G and its complement. Based on the theorem, Chudnovsky, Cornuéjols, Liu, Seymour, and Vušković show in 2005 an O(n^9)-time algorithm for recognizing perfect graphs, which can be implemented to run in O(n^(6+ω)) time for the exponent ω < 2.373 of square-matrixmultiplication. We show the following improved algorithms for detecting or finding induced subgraphs in G. 1. The tractability of detecting odd holes in G was open for decades until the major breakthrough of Chudnovsky, Scott, Seymour, and Spirkl in 2020. Their O(n^9)-time algorithm is later implemented by Lai, Lu, and Thorup to run in O(n^8) time, leading to the best formerly known algorithm for recognizing perfect graphs. Our first result is an O(n^7)-time algorithm for detecting odd holes, immediately implying a state-of-the-art O(n^7)-time algorithm for recognizing perfect graphs. Finding an odd hole based on Lai et al.’s O(n^8)-time algorithm for detecting odd holes takes O(n^9) time. 2. Chudnovsky, Scott, and Seymour extend in 2021 the O(n^9)-time algorithms for detecting odd holes (2020) and recognizing perfect graphs (2005) into the first polynomial-time algorithm for obtaining a shortest odd hole in G, which runs in O(n^14) time. Our second result is an O(n^13)-time algorithm for finding a shortest odd hole in G. 3. For vertices u and v of an n-vertex graph G, a uv-trail of G is an induced uv-path of G that is not a shortest uv-path of G. In 2021, Berger, Seymour, and Spirkl gave the previously only known polynomial-time algorithm, running in O(n^18) time, to find a uv-trail. We reduce the complexity to O˜(n^(2ω)) time, where the O˜ notation hides poly-logarithmic factors, leading to a largely improved O(n^4.75)-time algorithm. This third result has appeared in Proceedings of the 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/86005 |
DOI: | 10.6342/NTU202203481 |
全文授權: | 同意授權(全球公開) |
電子全文公開日期: | 2022-09-23 |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
U0001-1609202216453500.pdf | 698.81 kB | Adobe PDF | 檢視/開啟 |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。