Ожина (теорія графів)

Укриттям порядку k в графі G називається функція β, яка переводить кожну множину X з числом вершин менше k в зв'язний компонент G − X таким чином, що будь-які дві підмножини β(X) і β(Y) дотикаються між собою. Тобто, образи β утворюють ожину з порядком k в G. І навпаки, будь-яку ожину можна використати для створення укриття — для кожної множини X з розміром, меншим від порядку ожини, є єдиний зв'язний компонент β(X), що містить всі підграфи в ожині, не зв'язані з X.

Як показали Сеймур і Томас, порядок ожини (або, що еквівалентно, укриття) описує деревну ширину — граф має ожину порядку k в тому і тільки в тому випадку, коли деревна ширина не менша від k − 1[1].

Як помітили Грох і Маркс (Marx), експандери з обмеженим степенем мають деревну ширину, пропорційну числу вершин, і щоб включити всі підграфи, які не мають спільних вершин з кожною підмножиною такого розміру, ожина для таких графів повинна містити експоненціально багато різних підграфів. Точніше, для цих графів навіть ті ожини, порядок яких трохи більший від квадратного кореня з деревної ширини, повинні мати експоненціальний розмір. Однак Грох і Маркс також показали, що будь-який граф з деревною шириною k має ожину поліноміального розміру і порядок ${\displaystyle \Omega (k^{1/2}/\log ^{2}k)}$[2].

Оскільки ожини можуть мати експоненціальний розмір, не завжди можливо побудувати їх за поліноміальний час для графів з необмеженою деревною шириною. Однак якщо деревна ширина обмежена, поліноміальний час побудови можливий — є можливість знайти ожину порядку k, якщо така існує, за час ${\displaystyle O(n^{k+2})}$, де n — число вершин у графі. Можливі навіть швидші алгоритми для графів з малим числом мінімальних сепараторів[3].

Бодлендер, Григор'єв і Костер[4] вивчали евристичні алгоритми пошуку ожин високого порядку. Їхні методи не завжди давали ожини з порядком, близьким до деревної ширини, але для планарних графів вони дають постійний апроксимаційний коефіцієнт. Крейцер і Тазарі[5] пропонують імовірнісні алгоритми пошуку з поліноміальним часом роботи на графах з деревною шириною k ожин поліноміального розміру і порядку ${\displaystyle \Omega (k^{1/2}/\log ^{3}k)}$, що відповідає логарифмічному множнику порядку, виведеного Грохом і Марксом (Grohe, Marx, 2009) для існування ожин поліноміального розміру.