Косое разбиение

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

Косое разбиение графа — разбиение его вершин на два подмножества в виде несвязного порождённого подграфа и дополнения; играет важную роль в теории совершенных графов.

Определение

Косое разбиение графа ${\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]. Клауди Берж высказал гипотезу в начале 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) harvtxt error: якоря не существует: CITEREFReed2008 (помощь). Несуществование модулей в минимальных несовершенных графах использовал Ловас Lovász (1972) harvtxt error: якоря не существует: CITEREFLovász1972 (помощь) в доказательстве слабой теоремы о совершенных графах.
4. См. статью Cornuéjols, Reed (1993) harvtxt error: якоря не существует: CITEREFCornuéjols,_Reed1993 (помощь) для случая, в котором ко-несвязная сторона разбиения состоит из нескольких частей, и Roussel, Rubio (2001) harvtxt error: якоря не существует: CITEREFRoussel,_Rubio2001 (помощь) для случая, в котором одна из двух частей ко-несвязной стороны является независимой.
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. — doi:10.4007/annals.2006.164.51. — arXiv:math/0212070.
• Chvátal V. Star-cutsets and perfect graphs // Journal of Combinatorial Theory. — 1985. — Т. 39, вып. 3. — С. 189–199. — 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. — 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. — 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. — 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. — doi:10.1016/j.jctb.2007.07.004..