Косе розбиття

Косе розбиття хордального графа. Верхня та нижня частини ліворуч не пов'язані між собою, а праворуч утворюють граф із незв'язним доповненням.

Косе розбиття́ графа — розбиття вершин графа на дві підмножини у вигляді незв'язного породженого підграфа та доповнення; відіграє важливу роль у теорії досконалих графів.

Визначення

Косе розбиття графа ${\displaystyle G}$ — це розбиття вершин графа на дві підмножини ${\displaystyle X}$ і ${\displaystyle Y}$, для яких породжений підграф ${\displaystyle G[X]}$ незв'язний, а породжений підграф ${\displaystyle G[Y]}$ є доповненням незв'язного графа (далі — «ко-незв'язного»). Еквівалентно косе розбиття графа ${\displaystyle G}$ можна описати як розбиття вершин графа ${\displaystyle G}$ на такі чотири підмножини ${\displaystyle A}$, ${\displaystyle B}$, ${\displaystyle C}$ і ${\displaystyle D}$, в яких відсутні ребра з ${\displaystyle A}$ в ${\displaystyle B}$, але присутні всі можливі ребра з ${\displaystyle C}$ в ${\displaystyle D}$. Для такого розбиття породжені підграфи ${\displaystyle G[A\cup B]}$ і ${\displaystyle G[C\cup D]}$ незв'язні і ко-незв'язні відповідно, тому можна взяти ${\displaystyle X=A\cup B}$ і ${\displaystyle Y=C\cup D}$.

Приклади

Будь-який шлях із чотирма і більше вершинами має косе розбиття, в якому ко-зв'язна множина ${\displaystyle Y}$ є одним зі внутрішніх ребер шляху, а незв'язна множина ${\displaystyle X}$ складається з обох вершин цього ребра. Однак, неможливе косе розбиття для циклів будь-якої довжини — несуттєво, які підмножини циклів вибрано як множину ${\displaystyle X}$, доповнення множини ${\displaystyle Y}$ матиме те саме число зв'язних компонент, так що неможливо і ${\displaystyle X}$ розкласти, і щоб ${\displaystyle Y}$ була ко-незв'язним.

Якщо граф має косе розбиття, то таке розбиття має і його доповнення. Наприклад, доповнення шляхів мають косі розбиття, а доповнення циклів — ні.

Особливі випадки

Якщо граф незв'язний, то, за винятком трьох простих випадків (порожній граф, граф з одним ребром і трьома вершинами або досконале парування на чотирьох вершинах), він має косе розбиття, в якому ко-незв'язний бік розбиття складається з кінцевих точок одного ребра, і незв'язний бік складається з решти вершин. З тієї ж причини, якщо доповнення графа незв'язне, то, за винятком відповідної множини з трьох випадків, він повинен мати косе розбиття[1].

Якщо граф має кліковий сепаратор (кліку, видалення якої робить решту вершин незв'язними) з більш ніж однією вершиною, розбиття на кліку і решту вершин утворює косе розбиття. Кліковий розріз з однією вершиною є шарніром. Якщо така вершина існує, то, за невеликим числом простих винятків, існує косе розбиття, в якому ко-незв'язна сторона складається з цієї вершини й одного з її сусідів[1].

Зірковий розріз у графі ${\displaystyle G}$ — це вершинний сепаратор, у якому одна з вершин суміжна з усіма іншими вершинами сепаратора. Будь-який кліковий сепаратор є зірковим розрізом. Граф із зоряним розрізом (з більш ніж однією вершиною) обов'язково має косе розбиття, в якому ко-незв'язний підграф складається з вершин зіркового розрізу, а незв'язний підграф складається з решти вершин[1].

Модуль (або однорідна множина) є нетривіальною підмножиною ${\displaystyle H}$ вершин графа ${\displaystyle G}$, таким, що для будь-якої вершини ${\displaystyle v}$, що не належить ${\displaystyle H}$, ${\displaystyle v}$ або суміжна всім вершинам у ${\displaystyle H}$, або жодній з них. Якщо граф ${\displaystyle G}$ має модуль ${\displaystyle H}$ і поза ним існують вершини, суміжні всім вершинам ${\displaystyle H}$, а інші вершини поза ним не суміжні жодній вершині з ${\displaystyle H}$, то ${\displaystyle G}$ має зірковий розріз, що складається з однієї вершини в модулі разом із її сусідами поза модулем. З іншого боку, якщо існує модуль, у якому одна з цих двох підмножин порожня, то граф незв'язний або ко-незв'язний, і знову (за винятком трьох простих випадків) він має косе розбиття[1].

Історія

Косі розбиття ввів Хватал[2] у зв'язку з досконалими графами. Хватал довів, що мінімально недосконалий граф не може мати зіркового розрізу. Зрозуміло, що незв'язні графи не можуть бути мінімально недосконалими, і було відомо також, що графи з кліковими сепараторами або модулями не можуть бути мінімально недосконалими[3]. Клод Берже^[en] на початку 1960-х років висловив гіпотезу, що досконалі графи повинні збігатися з графами Бержа, графами без породженого непарного циклу (довжиною п'ять або більше) або його доповнення, і (оскільки цикли та їх доповнення не мають косих розбиттів) ніякий граф, що не є мінімальним графом Бержа, не може мати косого розбиття. Зацікавлений цими результатами, Хватал висловив гіпотезу, що ніякий мінімальний недосконалий граф не може мати косого розбиття. Деякі автори довели окремі випадки цієї гіпотези, але вона залишається невирішеною вже довгий час[4].

Косі розбиття набули особливої важливості, коли Чудновська, Робертсон, Сеймур і Томас[5] використали їх для доведення сильної теореми про досконалі графи, що графи Бержа це те саме, що й досконалі графи. Чудновська та її група не змогли довести гіпотезу Хватала безпосередньо, але довели слабший результат, що мінімальний контрприклад теоремі (якби такий існував) повинен мати збалансоване косе розбиття, в якому кожен породжений шлях з кінцем на одному боці розбиття та внутрішніми вершинами на іншому боці має парну довжину. Цей результат став ключовою лемою в їхньому доведенні, а повна версія леми Хватала випливає з їхньої теореми[6].

У структурній теорії графів

Косі розбиття утворюють ключову компоненту структурного розкладання досконалих графів, яке використали Чудновська, Робертсон, Сеймур і Томас[5] як частину доведення сильної теореми про досконалі графи. Чудновська зі співавторами показала, що будь-який досконалий граф або належить до п'яти базових класів досконалих графів, або має один із чотирьох типів розкладів на простіші графи і одним з цих розкладів є косе розбиття.

Простий приклад структурного розкладу з використанням косих розбиттів дав Сеймур[6]. Він зауважив, що будь-який граф порівнянності є повним, або двочастковим, або має косі розбиття. Дійсно, якщо будь-який елемент частково впорядкованої множини є або мінімальним елементом або максимальним елементом, то відповідний граф порівнянності двочастковий. Якщо впорядкування є повним, то відповідний граф порівнянності повний. Якщо жодна з цих умов не виконується, але будь-який елемент, який не є ні мінімальним, ні максимальним, порівнянний з усіма іншими елементами, то або розбиття на мінімальні і не мінімальні елементи (якщо є більше одного мінімального елемента), або розбиття на максимальні та не максимальні елементи (якщо є більше одного максимального елемента) формує зірковий розріз. У випадку, що залишився, існує елемент ${\displaystyle x}$ часткового порядку, який ні мінімальний, ні максимальний і порівняний не з усіма іншими елементами. У цьому випадку існує косе розбиття (доповнення зіркового розрізу), в якому ко-незв'язний бік складається з елементів, порівнянних з ${\displaystyle x}$ (за винятком самого ${\displaystyle x}$), а незв'язний бік складається з решти елементів.

Хордальні графи мають навіть простіші розклади схожого вигляду — вони або повні, або мають кліковий сепаратор. Гейворд[7] показав аналогічно, що будь-який зв'язний і ко-зв'язний слабкий хордальний граф (граф з породженим циклом довжини більше чотирьох або його доповненням) з чотирма або більше вершинами має зірковий розріз або його доповнення, звідки за лемою Хватала випливає, що будь-який такий граф досконалий.

Алгоритми та складність

Косе розбиття цього графа, якщо воно існує, можна знайти за поліноміальний час. Це спочатку показали Фігейредо, Кляйн, Кохаякава та Рід[8], але з дуже великим часом роботи ${\displaystyle O(n^{101})}$, де ${\displaystyle n}$ — число вершин вхідного графа. Кеннеді та Рід[9] покращили час роботи до ${\displaystyle O(n^{4}m)}$. Тут ${\displaystyle m}$ — число ребер.

Задача перевірки, чи містить граф косе розбиття, в якому одна з частин ко-незв'язного боку незалежна, є NP-повною задачею[10]. Перевірка, чи містить довільний граф збалансоване косе розбиття також є NP-повною задачею, але задача розв'язна за поліноміальний час для досконалих графів[11].

Примітки

1. Reed, 2008.
2. Chvátal, 1985.
3. Reed, (2008). Неіснування модулів у мінімальних недосконалих графах використав Ловас Lovász, (1972) у доведенні слабкої теореми про досконалі графи.
4. Див. статтю Cornuéjols, Reed, (1993) для випадку, в якому ко-незв'язний бік розбиття складається з декількох частин, і Roussel, Rubio, (2001) для випадку, в якому одна з двох частин ко-незв'язного боку є незалежною.
5. Chudnovsky, Robertson, Seymour, Thomas, 2006.
6. Seymour, 2006.
7. Hayward, 1985.
8. de Figueiredo, Klein, Kohayakawa, Reed, 2000.
9. Kennedy, Reed, 2008.
10. Dantas, de Figueiredo, Klein, Gravier, Reed, 2004.
11. Trotignon, 2008.

Література

• Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas. The strong perfect graph theorem // Annals of Mathematics. — 2006. — Т. 164, вип. 1. — С. 51–229. — arXiv:math/0212070. — DOI:10.4007/annals.2006.164.51.
• Chvátal V. Star-cutsets and perfect graphs // Journal of Combinatorial Theory. — 1985. — Т. 39, вип. 3. — С. 189–199. — (Series B). — DOI:10.1016/0095-8956(85)90049-8.
• Gérard Cornuéjols, Bruce Reed. Complete multi-partite cutsets in minimal imperfect graphs // Journal of Combinatorial Theory. — 1993. — Т. 59, вип. 2. — С. 191–198. — (Series B). — DOI:10.1006/jctb.1993.1065.
• Simone Dantas, Celina M. H. de Figueiredo, Sulamita Klein, Sylvain Gravier, Bruce Reed. Stable skew partition problem // Discrete Applied Mathematics. — 2004. — Т. 143, вип. 1-3. — С. 17–22. — DOI:10.1016/j.dam.2004.01.001.
• Celina M. H. de Figueiredo, Sulamita Klein, Yoshiharu Kohayakawa, Bruce Reed. Finding skew partitions efficiently // Journal of Algorithms. — 2000. — Т. 37, вип. 2. — С. 505–521. — DOI:10.1006/jagm.1999.1122.
• Ryan B. Hayward. Weakly triangulated graphs // Journal of Combinatorial Theory. — 1985. — Т. 39, вип. 3. — С. 200–208. — (Series B). — DOI:10.1016/0095-8956(85)90050-4.
• William S. Kennedy, Bruce Reed. Fast skew partition recognition // Computational Geometry and Graph Theory: International Conference, KyotoCGGT 2007, Kyoto, Japan, June 11–15, 2007, Revised Selected Papers. — Berlin : Springer, 2008. — Т. 4535. — С. 101–107. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-540-89550-3_11.
• László Lovász. Normal hypergraphs and the perfect graph conjecture // Discrete Mathematics. — 1972. — Т. 2, вип. 3. — С. 253–267. — DOI:10.1016/0012-365X(72)90006-4.
• Bruce Reed. Skew partitions in perfect graphs // Discrete Applied Mathematics. — 2008. — Т. 156, вип. 7. — С. 1150–1156. — DOI:10.1016/j.dam.2007.05.054. Архівовано з джерела 19 вересня 2015.
• Roussel F., Rubio P. About skew partitions in minimal imperfect graphs // Journal of Combinatorial Theory. — 2001. — Т. 83, вип. 2. — С. 171–190. — (Series B). — DOI:10.1006/jctb.2001.2044.
• Paul Seymour. How the proof of the strong perfect graph conjecture was found // Gazette des Mathématiciens. — 2006. — Вип. 109. — С. 69–83.
• Nicolas Trotignon. Decomposing Berge graphs and detecting balanced skew partitions // Journal of Combinatorial Theory. — 2008. — Т. 98, вип. 1. — С. 173–225. — (Series B). — DOI:10.1016/j.jctb.2007.07.004..