График без четных дырок - Even-hole-free graph

в математический зона теория графов, график без дырок если он не содержит индуцированный цикл с четным числом вершины.

Addario-Berry et al. (2008) продемонстрировал, что каждый граф без четных дырок содержит бисимплициальная вершина, что разрешило гипотезу Рида.

Признание

Conforti et al. (2002b) дал первый алгоритм распознавания за полиномиальное время для графов без четных отверстий, который работает в ${displaystyle {mathcal {O}}(n^{40})}$ время.^[1]да Силва и Вушкович (2008) позже улучшил это до ${displaystyle {mathcal {O}}(n^{19})}$.Чанг и Лу (2012) и Чанг и Лу (2015) улучшил это до ${displaystyle {mathcal {O}}(n^{11})}$ время. Наиболее известный в настоящее время алгоритм дается Лай, Лу и Торуп (2020) который работает в ${displaystyle {mathcal {O}}(n^{9})}$ время.

Хотя графы без четных дырок можно распознать за полиномиальное время, это НП-complete, чтобы определить, содержит ли граф четное отверстие, которое включает определенную вершину.^[2]

Неизвестно, были ли раскраска графика и максимальный независимый набор Задача может быть решена за полиномиальное время на графах без четных дырок или на том, являются ли они NP-полными. максимальная клика можно найти в графах без четных дырок за полиномиальное время.^[3]

Заметки

1. Conforti et al. (2002b) представляют свой алгоритм и утверждают, что он работает за полиномиальное время, без явного анализа. Чудновский, Каварабаяши и Сеймур (2004) подсчитать, что он работает примерно "вовремя" ${displaystyle {mathcal {O}}(n^{40})}$."
2. Bienstock (1991)
3. Вушкович (2010).

использованная литература

• Аддарио-Берри, Луиджи; Чудновский, Мария; Хаве, Фредерик; Рид, Брюс; Сеймур, Пол (2008), "Бисимплициальные вершины в графах без четных дырок", Журнал комбинаторной теории, серия B, 98 (6): 1119–1164, Дои:10.1016 / j.jctb.2007.12.006
• Бинсток, Дэн (1991), "О сложности тестирования нечетных дыр и индуцированных нечетных путей", Дискретная математика, 90 (1): 85–92, Дои:10.1016 / 0012-365X (91) 90098-М
• Чудновский, Мария; Каварабаяси, Кен-ичи; Сеймур, Пол (2004), «Обнаружение четных отверстий», Журнал теории графов, 48 (2): 85–111, Дои:10.1002 / jgt.20040
• Конфорти, Микеле; Cornuéjols, Жерар; Капур, Аджай; Вушкович, Кристина (январь 2002a), "Графы без четных дырок, часть I: Теорема разложения" (PDF), Журнал теории графов, 39 (1): 6–49, Дои:10.1002 / jgt.10006
• Конфорти, Микеле; Cornuéjols, Жерар; Капур, Аджай; Вушкович, Кристина (август 2002b), «Графы без четных отверстий, часть II: алгоритм распознавания» (PDF), Журнал теории графов, 40 (4): 238–266, Дои:10.1002 / jgt.10045
• да Силва, Мурило В.Г .; Вушкович, Кристина (2008), Разложение графов без четных отверстий с помощью звездных сечений и 2-соединений
• Чанг, Сянь-Чжи; Лу, Сюэ-И (январь 2012 г.), «Более быстрый алгоритм распознавания графиков без четных отверстий», SODA '12: Материалы двадцать третьего ежегодного симпозиума ACM-SIAM по дискретным алгоритмам: 1286–1297
• Чанг, Сянь-Чжи; Лу, Сюэ-I (июль 2015 г.), «Более быстрый алгоритм распознавания графиков без четных отверстий», Журнал комбинаторной теории, серия B, 113: 141–161, arXiv:1311.0358, Дои:10.1016 / j.jctb.2015.02.001, S2CID  1744497
• Вушкович, Кристина (2010), «Графики без четных отверстий: обзор» (PDF), Применимый анализ и дискретная математика, 4 (2): 219–240, Дои:10.2298 / AADM100812027V, JSTOR  43666110, Г-Н  2724633
• Лай, Кай-Юань; Лу, Сюэ-И; Торуп, Миккель (июнь 2020 г.), «Три на дереве в почти линейное время», STOC 2020: Материалы 52-го ежегодного симпозиума ACM SIGACT по теории вычислений: 1279–1292, arXiv:1909.07446, Дои:10.1145/3357713.3384235 (неактивно 29.09.2020)

внешние ссылки

• «Графы без четных дырок», Информационная система по классам графов и их включениям