论文标题
在多项式时间里找到最短的孔
Finding a Shortest Even Hole in Polynomial Time
论文作者
论文摘要
图中的均匀（分别为奇数）孔是一个诱导的循环，其均匀（分别为奇数）长度至少为四个。 Bienstock [DM 1991和1992]证明，检测一个包含给定顶点的均匀（奇数）孔是NP完整的。 Conforti，Chornuéjols，Kappor和Vušković[Focs 1997]给出了第一种已知的多项式时间算法，以确定图是否包含孔。 Chudnovsky，Kawarabayashi和Seymour [JGT 2005]估计，Conforti等人的算法在$ o（n^{40}）$ time上运行，在$ n $ vertex图上，将所需的时间减少到$ o（n^{31}）$。随后，Da〜Silva和Vušković〜 [JCTB 2013]，Chang and Lu [Jctb 2017]以及Lai，Lu和Thorup [Stoc 2020]将时间提高到$ O（N^{19}）$，$ O（N^{11}）$（N^{11}）$（N^{11}）$（N^{11}）$（N^9）$。确定图表是否包含奇数孔的障碍性数十年已经打开了数十年，直到Chudnovsky，Scott，Seymour和Spirkl [Jacm 2020]的算法以$ O（N^9）$时间运行为止。还减少到$ O（n^8）$。通过扩展Chudnovsky等人检测奇数孔的技术，Chudnovsky，Scott和Seymour [Combinatorica 2020分别出现]（分别出现）（分别为[Arxiv 2020]）确保了找到一个长（分别（分别是最短）奇数）奇数孔的障碍。他们还确保了找到一个最长的奇数孔的NP硬度，其还原也用于寻找最长的均匀孔。最近，库克和西摩确保了找到一个漫长的洞的障碍。令人着迷的缺少作品是找到一个最短的均匀孔的障碍，例如Chudnovsky等人至少打开15年。 [JGT 2005]和Johnson [Talg 2005]。我们通过提供第一个已知的多项式时间算法（在$ o（n^{31}）$时间内运行的第一个已知的多项式时间算法来解决这个长期存在的问题，以在包含均匀孔的$ n $ vertex图中找到最短的孔。
An even (respectively, odd) hole in a graph is an induced cycle with even (respectively, odd) length that is at least four. Bienstock [DM 1991 and 1992] proved that detecting an even (respectively, odd) hole containing a given vertex is NP-complete. Conforti, Chornuéjols, Kappor, and Vušković [FOCS 1997] gave the first known polynomial-time algorithm to determine whether a graph contains even holes. Chudnovsky, Kawarabayashi, and Seymour [JGT 2005] estimated that Conforti et al.'s algorithm runs in $O(n^{40})$ time on an $n$-vertex graph and reduced the required time to $O(n^{31})$. Subsequently, da~Silva and Vušković~[JCTB 2013], Chang and Lu [JCTB 2017], and Lai, Lu, and Thorup [STOC 2020] improved the time to $O(n^{19})$, $O(n^{11})$, and $O(n^9)$, 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 [JACM 2020] that runs in $O(n^9)$ time, which Lai et al. also reduced to $O(n^8)$. By extending Chudnovsky et al.'s techniques for detecting odd holes, Chudnovsky, Scott, and Seymour [Combinatorica 2020 to appear] (respectively, [arXiv 2020]) 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 at least 15 years by, e.g., Chudnovsky et al. [JGT 2005] and Johnson [TALG 2005]. We resolve this long-standing open problem by giving the first known polynomial-time algorithm, running in $O(n^{31})$ time, for finding a shortest even hole in an $n$-vertex graph that contains even holes.
