https://scholars.lib.ntu.edu.tw/handle/123456789/607413
標題: | Finding a shortest even hole in polynomial time | 作者: | Cheong H.-T Lu H.-I. HSUEH-I LU |
關鍵字: | Graph algorithms;Graph theory;Even holes;Induced cycle;Induced subgraphs;NP Complete;Odd length;Polynomial-time;Required time;S-algorithms;Short even hole;Vertex graphs;Polynomial approximation | 公開日期: | 2022 | 卷: | 99 | 期: | 3 | 起(迄)頁: | 425-434 | 來源出版物: | Journal of Graph Theory | 摘要: | An even (respectively, odd) hole in a graph is an induced cycle with even (respectively, odd) length that is at least four. Bienstock proved that detecting an even (respectively, odd) hole containing a given vertex is NP-complete. Conforti, Cornu?jols, Kapoor, and Vu?kovi? gave the first known polynomial-time algorithm to determine whether a graph contains even holes. Chudnovsky, Kawarabayashi, and Seymour estimated that Conforti et al.'s algorithm runs in (Formula presented.) time on an (Formula presented.) -vertex graph and reduced the required time to (Formula presented.). Subsequently, da Silva and Vu?kovi?, Chang and Lu, and Lai, Lu, and Thorup?improved the time to (Formula presented.), (Formula presented.), and (Formula presented.), respectively. The tractability of determining whether a graph contains odd holes has been open for decades until the algorithm of Chudnovsky, Scott, Seymour, and Spirkl that runs in (Formula presented.) time, which Lai et al. also reduced to (Formula presented.). By extending Chudnovsky et al.'s techniques for detecting odd holes, Chudnovsky, Scott, and Seymour?(respectively) ensured the tractability of finding a long (respectively, shortest) odd hole. They also ensured the NP-hardness of finding a longest odd hole, whose reduction also works for finding a longest even hole. Recently, Cook and Seymour ensured the tractability of finding a long even hole. An intriguing missing piece is the tractability of finding a shortest even hole, left open for 16 years by, for example, Chudnovsky et al. and Johnson. We resolve this open problem by augmenting Chudnovsky et al.'s even-hole detection algorithm into the first known polynomial-time algorithm, running in (Formula presented.) time, for finding a shortest even hole in an (Formula presented.) -vertex graph that contains even holes. ? 2021 Wiley Periodicals LLC |
URI: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-85115418230&doi=10.1002%2fjgt.22748&partnerID=40&md5=a6afddb46dca305003e5489ebe911f49 https://scholars.lib.ntu.edu.tw/handle/123456789/607413 |
ISSN: | 03649024 | DOI: | 10.1002/jgt.22748 |
顯示於: | 資訊工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。