偶数ホールフリーグラフ

グラフ理論の数学の分野では、グラフに頂点の数が偶数個の誘導サイクルが含まれていない場合、そのグラフは偶数ホールフリーである。より正確には、定義により、グラフが長さ 4 の誘導サイクルを持つことが認められる場合もあれば、認められない場合もある。後者は偶数サイクルフリーグラフと呼ばれる。^[1]

Addario-Berryら (2008) は、すべての偶数ホールフリーグラフには双単体頂点 (近傍が2つのクリークの和集合である頂点) が含まれることを実証し、 Reedの予想を解決しました。この証明は後にChudnovsky & Seymour (2023) によって欠陥があることが示され、正しい証明が示されました。

認識

Conforti et al. (2002b) は、時間で実行される、偶数ホールのないグラフの最初の多項式時間認識アルゴリズムを提示しました。 ^[2] da Silva & Vušković (2008) は、後にこれをに改良しました。Chang & Lu (2012) と Chang & Lu (2015) は、これをに改良しました。現在知られている最良のアルゴリズムは、時間で実行される Lai、Lu & Thorup (2020) によって提示されています。 ${\mathcal {O}}(n^{40})$ ${\mathcal {O}}(n^{19})$ ${\mathcal {O}}(n^{11})$ ${\mathcal {O}}(n^{9})$

偶数ホールのないグラフは多項式時間で認識できるが、グラフに特定の頂点を含む偶数ホールが含まれているかどうかを判断するのはNP完全である。 ^[3]

グラフ彩色問題と最大独立集合問題が偶数穴のないグラフ上で多項式時間で解けるかどうか、あるいはNP完全かどうかは不明である。しかし、最大クリークは偶数穴のないグラフ上で多項式時間で見つけることができる。^[4]

注記

^ 「even-cycle--free graphs」、www.graphclasses.org 、 2023年3月12日取得
^ Conforti ら (2002b) は、アルゴリズムを提示し、明示的な分析を行わずに多項式時間で実行されると主張しています。Chudnovsky、Kawarabayashi、Seymour (2004) は、それが「約の時間」で実行されると推定しています。 ${\mathcal {O}}(n^{40})$
^ ビエンストック（1991）
^ ヴシュコビッチ（2010年）。

参考文献

Addario-Berry, Louigi; Chudnovsky, Maria ; Havet, Frédéric; Reed, Bruce ; Seymour, Paul (2008)、「偶数ホールフリーグラフの双単体頂点」、Journal of Combinatorial Theory、シリーズ B、98 (6): 1119–1164、doi :10.1016/j.jctb.2007.12.006
ビエンストック、ダン（1991）「奇数ホールと誘導奇数パスのテストの複雑さについて」、離散数学、90（1）：85–92、doi：10.1016 / 0012-365X（91）90098-M
マリア・チュドノフスキー;河原林健一;シーモア、ポール(2004)、「偶数ホールの検出」、グラフ理論ジャーナル、48 (2): 85–111、doi :10.1002/jgt.20040、S2CID 2945499
Conforti, Michele; Cornuéjols, Gérard ; Kapoor, Ajai; Vušković, Kristina (2002a 年 1 月)、「Even-hole-free graphs part I: Decomposition theorem」(PDF)、Journal of Graph Theory、39 (1): 6–49、doi :10.1002/jgt.10006、S2CID 12947855
Conforti, Michele; Cornuéjols, Gérard ; Kapoor, Ajai; Vušković, Kristina (2002b 年 8 月)、「Even-hole-free graphs part II: Recognition algorithm」(PDF)、Journal of Graph Theory、40 (4): 238–266、doi :10.1002/jgt.10045、S2CID 15044085
da Silva, Murilo VG; Vušković, Kristina (2008)、スターカットセットと2-結合による偶数ホールフリーグラフの分解
Chang, Hsien-Chih、Lu, Hsueh-I (2012 年 1 月)、「偶数ホールフリーグラフを認識するための高速アルゴリズム」、SODA '12: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms : 1286–1297、arXiv : 1311.0358、doi : 10.1137/1.9781611973099.101、ISBN 978-1-61197-210-8
Chang, Hsien-Chih; Lu, Hsueh-I (2015 年 7 月)、「偶数ホールフリーグラフを認識するための高速アルゴリズム」、Journal of Combinatorial Theory、シリーズ B、113 : 141–161、arXiv : 1311.0358、doi :10.1016/j.jctb.2015.02.001、S2CID 1744497
Vušković, Kristina (2010)、「Even-hole-free graphs: a survey」(PDF)、Applicable Analysis and Discrete Mathematics、4 (2): 219–240、doi :10.2298/AADM100812027V、JSTOR 43666110、MR 2724633
Lai, Kai-Yuan; Lu, Hsueh-I; Thorup, Mikkel (2020)、「Three-in-a-tree in near linear time」、Makarychev, Konstantin; Makarychev, Yury; Tulsiani, Madhur; Kamath, Gautam; Chuzhoy, Julia (編)、Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing、STOC 2020、シカゴ、イリノイ州、米国、2020 年 6 月 22 ～ 26 日、Association for Computing Machinery、pp. 1279 ～ 1292、arXiv : 1909.07446、doi :10.1145/3357713.3384235
チュドノフスキー、マリア; シーモア、ポール (2023)、「偶数ホールフリーグラフでも双単体頂点が存在する」、Journal of Combinatorial Theory、シリーズ B、arXiv : 1909.10967、doi :10.1016/j.jctb.2023.02.009

外部リンク

「偶数ホールのないグラフ」、グラフクラスとその包含に関する情報システム

[1] 「even-cycle--free graphs」、www.graphclasses.org 、 2023年3月12日取得

[2] Conforti ら (2002b) は、アルゴリズムを提示し、明示的な分析を行わずに多項式時間で実行されると主張しています。Chudnovsky、Kawarabayashi、Seymour (2004) は、それが「約の時間」で実行されると推定しています。 ${\mathcal {O}}(n^{40})$

[3] ビエンストック（1991）

[FOOTNOTEVušković2010-4] ヴシュコビッチ（2010年）。