Четвёртое определение древесной глубины и кратчайшие расстояния через дерево исключений

Мы продолжаем разговор про наши замечательные параметры, и сегодня я хотел бы обсудить оставшиеся аспекты древесной глубины — из тех важных и очевидных, что у нас есть на данный момент. Пока видимость у нас очень ограниченная: мы не видим всех параметров сразу, и я стараюсь выдавать порциями то, что можно сказать про параметр прямо сейчас, локально. Постепенно будем всё усложнять, добавлять параметры и рассказывать про связи между ними. Когда-то у нас даже должен начать появляться обещанный граф параметров: для него была отсрочка из-за домашнего задания, где надо было восстанавливать связи между параметрами, и мы решили, что показывать его будет нехорошо. Теперь руки развязаны, так что потихоньку его подготовим.

Особенно хотелось уделить внимание древесной глубине как параметру в плане её полиномиальных применений. Не так много есть параметров, вокруг которых развили теорию, реально использующуюся на практике. Как оценивать, насколько параметр реально используется, насколько он релевантен и важен, не очень понятно — но тем не менее параметр заслуживает внимания к такому вопросу.

Давайте придумаем ещё какое-нибудь альтернативное определение древесной глубины. Это будет уже четвёртое определение: до этого было три — первое совсем обычное рекурсивное, второе через дерево исключений (elimination tree), третье про игру полицейских и грабителя. Четвёртое определение такое. Назовём раскраску вершин графа в kk цветов подходящей, если у любого связного подграфа вершина максимального ранга единственна. Цвета здесь важны именно как числа из множества {1,2,…,k}\{1,2,\dots,k\}, и по смыслу цвета — это ранги.

Тогда td(G)td(G) можно определить как минимальное число kk, при котором существует подходящая раскраска. Обратите внимание: такая раскраска напрямую не определялась как правильная, но на самом деле она обязана быть правильной. Несложно доказать это утверждение в качестве упражнения. По сути выбор вершины максимального ранга — это и есть выбор корня в дереве исключений для текущего подграфа: по такой раскраске легко строится elimination tree, а по elimination tree так же легко строится раскраска. Доказывать тут нужно только то, что в связном подграфе не бывает двух вершин одного максимального ранга, но это доказывается. Вопросы по такому определению есть? Размялись — отлично.

Давайте тогда попробуем ускорять алгоритмы поиска кратчайшего пути на заданном графе. Постановка такая: дан граф GG, и приходят запросы. Запросы простые: чему равно dist(x,y)\mathrm{dist}(x,y) — длина кратчайшего (x,y)(x,y)-пути. Для простоты граф у нас неориентированный — ориентированных графов у нас пока особо и не было. Можно иметь неотрицательные веса на рёбрах. Тут можно задавать много вопросов про то, что происходит с отрицательными весами, но это мы зададим потом; давайте сначала поймём, как конструкция работает для неотрицательных весов. Для отрицательных многие алгоритмы на самом деле тоже работают, вопрос только в том, как именно.

Задача понятная: если вы по каким-то причинам разрабатываете альтернативный сервис поиска маршрутов на карте, вам, может быть, понадобится быстро отвечать на такие запросы. И оказывается, что дерево исключений даёт здесь суперпростую конструкцию. Сначала я расскажу очень простую конструкцию, которая мало что позволяет, а потом мы перейдём к конструкции более известной и поймём, от чего же мы стремились избавиться в первой.

Предложение. Возьмём некоторое дерево исключений TT высоты hh нашего графа GG — то же самое, что подходящая раскраска. Раскраска нам сейчас немножко поможет понять интуицию, что на самом деле происходит. У нас есть совершенно естественная иерархия на графе: вспоминаем, что в elimination tree при удалении вершины граф распадался на компоненты связности, и так далее. Я предложу сначала конструкцию, а потом мы поймём, почему она работает.

Конструкция будет такая: я буду насчитывать кратчайшие пути от вершины до всех её потомков в некотором графе. Если я взял elimination tree, то для вершины vv у меня определено не подмножество, а поддерево TvT_v — поддерево elimination tree для вершины vv. Скажем, для корня мы знаем, что V(Troot)=V(G)V(T_{root}) = V(G). Понятно, что такое TvT_v. И теперь я предлагаю просто делать какой-то подсчёт внутри таких поддеревьев.

Во-первых, замечу, что в нормальном elimination tree множество V(Tv)V(T_v) связно в GG, то есть подграф G[V(Tv)]G[V(T_v)] связен. Единственный случай, когда мы не можем этого добиться, — когда исходный граф был несвязным, но тогда граф, понятно, можно разделить на независимые части. Откуда это понятно? У разумного elimination tree всегда так, потому что иначе я могу разбить его на две части и подвесить одну из них просто сюда.

Тогда определим граф, соответствующий вершинке vv в elimination tree: это как раз подграф, порождённый на этих вершинах, Gv=G[V(Tv)]G_v = G[V(T_v)]. То есть я взял, вырезал поддерево и посмотрел, что это была за штука в графе. И теперь внутри GvG_v я насчитаю кратчайшие расстояния distGv(v,x)\mathrm{dist}_{G_v}(v,x) от вершины vv до вершины xx — и делать это я буду для всех x∈V(Tv)x \in V(T_v). Я прямо беру свой подграф — вот как это всё выглядело в графе на картинке: вот был корень, при его удалении получилась вот такая история, и здесь тоже есть свой корень, вершинка vv. Внутри этого подграфа я считаю все кратчайшие расстояния. Если вы когда-нибудь работали с центроидной декомпозицией, для деревьев такое точно делалось и происходит очень часто; а теперь мы то же самое делаем внутри графа.

Понятна конструкция? За сколько я её считаю, товарищи? Давайте внутри одного графа. Понятно, что это просто задача single source shortest paths — путь от одной вершины до всех остальных внутри конкретного графа GvG_v. Мы привыкли, что это работает за O(∣V(Gv)∣log⁡∣V(Gv)∣)O\bigl(|V(G_v)|\log|V(G_v)|\bigr). Конечно, современными технологиями и прорывами эту штуку уже умеют делать как-то быстрее — правда, всё это получилось ещё до LLM. Но вообще мы больше привыкли к тому, что здесь стоит ещё и EE, количество рёбер внутри этой компоненты: O(∣E(Gv)∣+∣V(Gv)∣log⁡∣V(Gv)∣)O\bigl(|E(G_v)| + |V(G_v)|\log|V(G_v)|\bigr). Это не так важно: каким-то алгоритмом мы это считаем, обычным алгоритмом Дейкстры.

Теперь я утверждаю, что с помощью этих величин я очень быстро могу считать кратчайшие расстояния между вершинами. К тому, что сказал Саша — сколько это в сумме по всему графу, — мы потом перейдём. А считать я теперь могу за O(td)O(td); точнее, не за O(td)O(td), а за высоту этого дерева: высота у меня hh, так что считать я могу за O(h)O(h).

Давайте посмотрим, как это выглядит на elimination tree. Если я возьму вот эти две вершины и рассмотрю между ними кратчайший путь в графе GG, то через какую вершину он обязательно будет проходить, как вы считаете? Через какую вершину мы точно знаем, что он пройдёт?

— Через наименьшего общего предка.

— Не факт, на самом деле. В дереве это действительно было бы так: если бы граф был настолько простым, что он дерево, то эту вершину конкретно определял бы наименьший общий предок. Но когда у нас уже более общая штука, у меня могли быть рёбра — ребро идти сюда и ребро идти вот сюда, мне никто этого не запрещал. И тогда кратчайший путь между ними выглядит вот так. То есть кратчайший путь обязательно содержит вершину большего ранга, чем они сами, и это будет обязательно одна из вот этих вершин.

Давайте вернёмся к нашей раскраске и напишем утверждение: любой путь от xx до yy проходит через одного из общих предков xx и yy. Утверждение формулируется для любого пути, не только для кратчайшего. Понятно? Отлично, давайте докажем.

Рассмотрим этот путь от xx до yy. Мы знаем, что на нём есть вершина наибольшего ранга, и, согласно нашему определению, эта вершина единственна. Пусть pp — вершина наибольшего ранга на пути. Это значит, что она самая высокая в дереве — это очевидно. Теперь нам хочется сказать, что pp — предок xx и, соответственно, предок yy. Есть ли у кого-то понимание, почему это так работает? Доказать это можно разными способами, и картинка тут скорее даёт больше интуиции, чем формальный аргумент. Прямого ребра из xx в pp нет, и прямого ребра из pp в yy тоже нет — в этом и суть.

Формальный аргумент всё-таки нужно провести, хотя по существу всё просто: множество предков xx и yy — это разрез между xx и yy, вот и всё. Рассмотрим xx и yy: вот будет их наименьший общий предок в дереве, какой-то наименьший общий предок, а вот будет корень. Фишка в том, что если я все эти вершины из графа удалю, то от xx до yy дойти никак нельзя вообще. Поэтому утверждение совершенно понятно.

Вырожденность и contraction hierarchies

Множество общих предков отрезает xx от yy. Мы с вами знаем, что на момент этого удаления xx и yy лежат в разных компонентах связности. Понятно, что при удалении от графа отвалятся и ещё какие-то компоненты, но они нам не интересны. Поскольку pp — вершина максимального ранга, по построению получается, что путь целиком содержится в GpG_p. Отсюда всё и следует: нам нужно просто сложить dist(x,p)+dist(p,y)\mathrm{dist}(x,p) + \mathrm{dist}(p,y).

Итак, мы построили очень простой предподсчёт, который позволяет искать расстояние за O(h)O(h) — всё-таки общего предка перебрать придётся, мы ведь не знаем заранее, какой из них подойдёт лучше всего. Но возникает вопрос: за сколько всё это работает в сумме? Понятно, что суммарный размер графов предподсчёта не будет очень большим. Просуммируем количество вершин внутри всех этих подграфов. Каждая вершина участвует только в подграфах своих предков, поэтому у каждой вершины не больше hh вхождений в эту сумму, и мы получаем оценку ∑v∈V(G)∣V(Gv)∣⩽h⋅∣V(G)∣\sum_{v \in V(G)} |V(G_v)| \leqslant h \cdot |V(G)|.

Но тут есть вопрос: а как, собственно, оценить количество рёбер в этих подграфах? Количество вершин мы оценили, а количество рёбер — нет. С рёбрами есть очень простая, пусть и довольно грубая оценка — возможно, можно оценивать и сильнее, — и она связана с другим параметром.

— Скажите, друзья, пока есть какие-то вопросы? Нет?

Хорошо, у нас всё очень просто, мы уже размялись, можем идти бодрее. Стираем всё это.

Есть такой параметр, который называется вырожденность, по-английски degeneracy. В случае графов это не обзывательство. Параметр очень хороший, потому что он позволяет оценивать плотность графов, но при этом не очень интересный: маленькая вырожденность не гарантирует, что задача простая. Что же это такое? Граф называется kk-вырожденным, если его вершины можно упорядочить вот таким образом: граф у нас неориентированный, я выписываю вершины в ряд в порядке некоторой перестановки и ориентирую все рёбра слева направо. Я хочу, чтобы у каждой вершины было не больше kk рёбер направо. Это и называется kk-вырожденным графом. По сути, это то же самое, что сказать: я могу удалять из графа по одной вершине степени не больше kk, пока граф не исчезнет, — это ещё одно определение.

Вырожденность графа обозначается вот так: dg(G)=min⁡kdg(G) = \min k, при котором GG является kk-вырожденным. Вырожденность, конечно, ищется за полином: вы просто жадно берёте вершину минимальной степени и выкидываете её, и это работает. Древесная глубина всегда говорит нам, что в графе есть вершина степени не больше, чем древесная глубина минус один. Действительно, если вы возьмёте лист в вашем elimination tree, то его соседями могут быть только предки, и их не больше — больше просто быть не может. Поэтому мы знаем, что dg(G)⩽td(G)−1dg(G) \leqslant td(G) - 1.

Чем же нам вырожденность помогает? Это очень простой параметр для оценки разреженности графа: число рёбер в графе не превосходит вырожденности, умноженной на число вершин, то есть ∣E(G)∣⩽dg(G)⋅∣V(G)∣|E(G)| \leqslant dg(G) \cdot |V(G)|. Здесь даже можно было бы поставить ∣V(G)∣−1|V(G)| - 1, и вообще оценку можно сделать ещё точнее, но нам хватит и простой формы, поэтому минус единицу я стираю. И отсюда следует, что рёбер в наших подграфах тоже будет не слишком много — в худшем случае порядка квадрата. То есть алгоритм будет работать достаточно быстро.

Но можно заметить, что вырожденность — не очень хороший параметр для нас, потому что мы ищем параметры, относительно которых задача начнёт решаться эффективно.

— Как вы думаете, начиная с какой вырожденности задача решается сложно?

— Два.

Да, два. Давайте разберёмся по порядку.

— Вырожденность ноль — это какой граф?

Из зала отвечают верно. Действительно, dg(G)=0dg(G) = 0 означает, что E(G)=∅E(G) = \varnothing, то есть в GG нет рёбер. Если мы возьмём вырожденность один, это значит, что в графе всегда есть лист, то есть это лес (дерево, если граф связный). А когда вырожденность равна двум, это уже очень похоже на кубические графы: кубический граф — это граф, в котором степени всех вершин равны трём. Такие графы я плохо рисую сходу; простейший пример — K4K_4, это кубический граф. И если из такого графа удалить одну вершину, его вырожденность будет уже равна двум, при условии что он был связным.

А на кубических графах у нас уже куча задач NP-трудна — например, гамильтонов путь. Из вырожденности два, разумеется, не следует, что граф кубический или субкубический, — такого вывода сделать нельзя. А вот в обратную сторону верно: если GG субкубический, то есть является подграфом кубического, и при этом связный, то dg(G)=2dg(G) = 2. Так что многие задачи при степенях ровно три в графе уже не решаются. А когда максимальная степень в графе равна двум, это просто циклы или пути.

— Вопросы, друзья, по этой истории?

Но я вам обещал сказать, почему эта конструкция очень-очень нехорошая. Она очень простая, но очень нехорошая: она не позволяет почти ничего делать.

— Как вы думаете, почему эта конструкция нехорошая? Чего бы мы хотели от новой конструкции? Нет идей?

Согласен, странно задавать такой вопрос, когда ответ знаю только я, и догадаться, наверное, сложно. Ответ в том, что нам нужно обновление весов рёбер, а предложенная конструкция его не поддерживает. Возьмите очень простой elimination tree. Дерево с неглубоким elimination tree может быть очень широким — всё равно очень широким. Пусть у нас есть вот такая вершина, из которой выходит много-много длинных путей, и вот это ребро — прямо реально единственное ребро, соединяющее её со всем остальным. В предподсчёте у меня хранятся кратчайшие пути в эту вершину отовсюду. И если я поменяю вес этого ребра, а оно лежало вообще на любом пути отсюда вот сюда, то придётся менять все кратчайшие пути внутри этого графа. Нехорошо.

На самом деле нашу конструкцию можно было чуть ослабить: мы сделали её слишком сильной, считали слишком много, и поэтому ничего не получалось. И тут возникает штука, которая называется contraction hierarchies. Это прямо гуглится, про это есть нормальная статья в Википедии, там всё хорошо описано. Насколько я понимаю, изначально она не была связана с древесной глубиной, но так вышло, что древесная глубина очень-очень хорошо описывает эту конструкцию.

Идея в следующем: сокращать путь до такого короткого нам было не нужно. Что мы сделали? Мы взяли и превратили имевшийся (x,y)(x,y)-путь вообще в два ребра — назовём их сразу shortcut’ами, шорткатами. То есть я всегда знал: если я хочу соединить вот эти вершины между собой, у меня всегда найдётся один такой шорткат и один такой шорткат, и их сумма даст кратчайший путь. Но в асимптотике это сильно не помогало: нам всё равно нужно было искать ту самую вершину, то есть O(1)O(1) на запрос мы не добились. Давайте лучше применим другую идею: будем превращать путь в такой путь, который сначала поднимается по рангам, а потом опускается.

Понятно, что пока непонятно, что это значит. Сейчас объясню. Что мы вычисляли до этого? В том сценарии мы для каждой пары (p,v)(p,v), где pp — предок vv, считали dist(p,v)\mathrm{dist}(p,v). Но этого получилось очень много, и, как оказалось, пересчитывать это очень сложно. Более того, если мы меняем рёбра между высокоранговыми вершинами, это влияет на расстояния между низкоранговыми, то есть на какие-то вычисления на низкоранговых вершинах.

Давайте поймём, откуда вообще берутся contraction hierarchies. Нарисуем наш путь — эта картинка, если что, с Википедии, её можно потом посмотреть отдельно. Откуда берутся стягивания? Стягивания берутся из того, что мы добавляем не все шорткаты. Шорткат — это когда я прямо посчитал какое-то кратчайшее расстояние в каком-то графе. А здесь мы будем строить шорткаты следующим образом: мы будем запрещать вот такие ямы. Вот это наш путь, а по вертикали отложен ранг вершины, то есть её положение внутри elimination tree: самый низкоранговый — это лист, повыше — что-то промежуточное, на самом верху лежит корень. Вот эта верхняя вершина — та самая, которая раньше была общим предком, который мы искали.

Нарисуем для примера вот такую историю: пусть здесь у меня был очень хороший участок. И дальше я буду итеративно делать следующее. Если у вершины оба её соседа — более высокоранговые вершины, я создам между ними новый шорткат. Его желательно рисовать другим цветом; вопрос, какой цвет тут вообще будет видно — кажется, что на зелёной доске видно только красный. Так и будем продолжать. Вот эта вершина из пути как бы стирается, то есть дальше мы смотрим только на путь из новых шорткатов. Следующая вершина, видите, тоже находится в яме — этот участок тоже надо сократить, добавляем вот такой шорткат. В результате у нас получился вот такой путь, и его мы сокращаем так: из двух новых шорткатов делаем третий шорткат. Теперь наш путь действительно сначала поднимается по рангам от листьев к корню, а потом спускается.

На elimination tree это выглядит довольно сложно, но примерно так: была вершина, у неё было два ребра — в одного предка и в другого предка, — и поэтому мы сделали вот такой шорткат, который состоит из этих двух рёбер. Дальше это всё начинает подниматься наверх. Суть в том, что теперь шорткаты появляются друг из друга: два шортката превращаются в третий, и так далее. Но фишка в том, что шорткат меняет только шорткаты выше, чем он сам. Если у меня был шорткат с низкоранговой вершиной, идущий в более высокоранговые вершины, то новый шорткат, который я создам, будет лежать строго выше, чем эти два, — он как бы будет их накрывать. Из-за этого граф пересчёта у меня оказывается достаточно ограниченным: если ребро меняется, оно меняет только то, что сверху. Вот примерно такая история. Думаю, что contraction hierarchies я расскажу только на этом уровне, потому что…

Вычисление параметров: точно, перебором или приближённо

Не хочу убивать на это очень много времени: штука довольно сложная для осознания. Но идея понятная. Получилось, что теперь любой наш путь — это путь, который сначала поднимается по рангам, а потом опускается, потому что направления я выбрал именно так. Точнее говоря, у меня получается два склеенных пути, каждый из которых поднимается по рангам. Думаю, мы дадим какое-нибудь домашнее задание про contraction hierarchies — если кому интересно, как раз будет повод разобраться. Вопросы?

Итак, с такой системой, если её правильно построить, обновление одного ребра будет стоить O(h2)O(h^2), где hh — это как раз высота дерева исключений. Я, честно говоря, не знаю, как можно было эту конструкцию придумать: первая конструкция, где мы просто считаем расстояния для каждой пары (p,v)(p,v), где pp — предок vv, кажется мне суперестественной, а вот эта — совсем нет. Пока я готовился к лекции, пришлось попотеть, хотя я это сам реализовывал — конечно, не один, а с командой, часть из которой присутствует здесь. Штука совсем неочевидная. Вот примерно такая история про применение древесной глубины, которую я знаю; наверное, это самое релевантное в плане практической части.

Конечно, встаёт вопрос: а к чему всё это можно применить, то есть каким графам это всё применяется? И самое главное — хорошо, я знаю, что если нашёл хорошее дерево исключений, то, наверное, смогу что-то быстро пересчитывать. Но как же эти хорошие деревья исключений вообще искать? Не все параметры одинаково хороши в том плане, что их надо уметь хорошо искать. Поэтому мы плавненько переходим к вычислению параметров — к теме, о которой мы пока говорили мало, потому что у нас было слишком мало параметров, а теперь параметров достаточно много.

Одна из центральных проблем всей нашей истории в том, что параметры у нас есть и их надо использовать, но чтобы их использовать, нам нужно знать значение самого параметра, а более того — нужно знать ещё и структуру, которую этот параметр задаёт. То есть чтобы параметр использовать, его нужно вычислить: и его, и структуру. Если вспомнить древесную глубину, то мы знаем, что у нас есть дерево исключений. Но пусть мы умеем вычислять древесную глубину как число — это нам никак не поможет. Хотя, если мы умеем быстро вычислять древесную глубину, можно сделать такой переборчик: перебирать, какую вершинку поставить в корень, вычислять древесную глубину образовавшихся подграфов и выбирать лучший корень, рекурсивно действуя дальше. Для этого нам нужно изобрести алгоритм, который для любого подграфа вычисляет древесную глубину в точности, — и тогда структуру восстановить получится. Фишка в том, что если нам кто-то просто дал граф и сказал: «его древесная глубина вот такая», — нам это ничего не даст, потому что никакие наши алгоритмы мы ускорить не сможем.

Поэтому так или иначе нужно задаться вопросом: а как же параметры вообще вычисляются? И тут нужно отталкиваться от того, какие алгоритмы мы разрабатываем. Вот в этом примере мы разрабатывали полиномиальные алгоритмы, практически даже линейные: если древесная глубина — константа, предподсчёт вообще линейный, никаких квадратичных зависимостей нет, ну только если рёбер было очень много, тогда будет n2n^2. А какие у нас алгоритмы обычно? Давайте приведу пример: стандартный алгоритм работает за 2O(k)⋅nO(1)2^{O(k)} \cdot n^{O(1)} — это так называемый single-exponential. В перерыве мы достаточно подробно подискутировали по поводу того, что здесь бывает: в науке пытаются улучшать и константу в экспоненте, и уже даже полином nO(1)n^{O(1)}. Скорее люди пытаются понять, какие тут есть границы: если мы хотим линейное время, насколько можно уменьшить зависимость от kk, и наоборот — насколько можно уменьшить эту зависимость, повышая полином. Это всё изучают и этим интересуются, но какого-то чёткого требования строго улучшать полином, конечно же, нет.

Собственно, речь о чём? Мы хотим использовать параметр. Например, чтобы использовать параметр «вершинное покрытие» (VC), это самое вершинное покрытие нужно найти. И вот мы хотим, чтобы алгоритм остался single-exponential, то есть наш параметр — это kk. Что для этого можно сделать? Во-первых, параметр можно вычислить точно — и, конечно же, вместе со структурой. Но поскольку большинство разумных параметров вычислять NP-трудно, обычно это делается за какое-то большое, неполиномиальное время: либо у нас какое-нибудь f(k)⋅nO(1)f(k) \cdot n^{O(1)}, если параметр нам это позволяет (а не все параметры позволяют), либо параметр можно вычислять вообще только полным перебором, за 2n⋅nO(1)2^n \cdot n^{O(1)}.

Конечно, нас больше интересует первая история. И даже более того: если параметр вычисляется тоже за single-exponential время, то вообще всё шикарно — мы за single-exponential время вычисляем параметр и потом за single-exponential время решаем нашу задачу. Всё супер. А вот что творится в другом случае: даже если это single-exponential, экспонента здесь может быть больше, чем там, хотя это бывает редко. А может быть и так, что single-exponential алгоритма у меня вообще нет, функция ff нехорошая, и тогда вычисление параметра, конечно, будет доминировать над решением задачи. Но такие вычисления нас, в принципе, не очень интересуют: не очень понятен сценарий, в котором нам нужно вычислить параметр суперточно. Возможно, только если вы много раз решаете одну и ту же задачу, граф потом не будет меняться, и вам сейчас очень важно вычислить этот параметр точно.

Замечу, что это, в принципе, был некоторый перебор, а такое нам нужно не всегда. Смотрите, например, на вершинное покрытие: его действительно можно вычислить за время, зависящее от kk, и, кажется, быстрее, чем полным перебором — там уже константа лучше, чем 1,21{,}2. Точное время я, честно говоря, не помню, но давайте напишу примерно 1,2k⋅nO(1)1{,}2^k \cdot n^{O(1)}. А что ещё мы знаем про вершинное покрытие? Все очень любят 2-приближение для вершинного покрытия. Как оно строится? Найдём максимальное паросочетание и возьмём все вершинки — концы рёбер паросочетания. Заметим, что вставить сюда 2-приближение — это просто ухудшит в два раза показатель степени, так что при прочих равных нам это может пригодиться.

Поэтому второй способ — параметр можно аппроксимировать. Аппроксимаций есть очень много, и историй, как это делается, тоже. Самые сильные аппроксимации приближают с точностью (1+ε)(1+\varepsilon) для любого фиксированного ε\varepsilon. А что такое такое приближение? Мы находим какую-то структуру, которая не хуже, чем в (1+ε)(1+\varepsilon) раз: то есть здесь, грубо говоря, вместо kk будет (1+ε)k(1+\varepsilon)k. Самый лучший сценарий — когда это работает за f(ε)⋅nO(1)f(\varepsilon) \cdot n^{O(1)}; бывает сценарий, когда у меня nf(ε)n^{f(\varepsilon)} — я просто примеры напишу. Бывает просто constant-ratio, то есть CC-приближение только для какого-то конкретного CC, как в случае с вершинным покрытием.

Да, с вершинным покрытием мы знаем, что 2-приближение есть, — и если то, что недавно анонсировали, верно, то сделать лучше, чем 2-приближение, NP-трудно. Правда, для vertex cover, я думаю, уже доказано, что PTAS не бывает: вот такое — приближение с точностью (1+ε)(1+\varepsilon) за полиномиальное время для любого ε\varepsilon — называется polynomial-time approximation scheme. PTAS для него точно нет, потому что есть константа, для которой он не приближается; и, в общем, кажется, что 2−ε2-\varepsilon тоже уже нельзя. А бывает, что приближение какое-то похуже — как мы делали для древесной глубины, то есть f(k)f(k)-приближение. Для древесной глубины мы с вами на прошлой лекции за полином научились строить 2k2^{k}-приближение: мы просто построили DFS-дерево и сказали, что это 2k2^{k}-приближение. И всё это, конечно, за полиномиальное время.

Хорошо, давайте что-нибудь из этого тогда построим — не буду голословить. Применим какие-то из этих вещей к конкретным параметрам: для вершинного покрытия мы вроде всё обсудили более-менее, давайте обсудим, как вычисляются ещё какие-то параметры. Сегодня у нас будет обсуждаться примерно три параметра, сейчас поймём какие. Первый набор параметров — это расстояния до каких-то классов графов, как vertex cover: у нас были расстояние до кластера, расстояние до клики. Давайте возьмём параметр «расстояние до кластера», distance to cluster.

Первое, что нужно в таких штуках, — посмотреть на сам класс; для каких классов графов это всё работает, я объясню потом. Посмотрим просто на кластерные графы. Напомню определение: граф является кластерным, когда любая его компонента связности — это полный граф. Равносильно: в GG нет порождённого P3P_3. Что такое порождённый подграф? Это когда я оставил только какие-то вершины. Имеется в виду следующее: если я выберу любые три вершинки u,v,wu, v, w, я не получу граф, изоморфный пути на трёх вершинах, то есть G[{u,v,w}]≇P3G[\{u,v,w\}] \not\cong P_3. Это доказывается несложно, можете поупражняться.

Теперь, чтобы вычислить distance to cluster, что я просто должен сделать? Я должен удалить какие-то вершинки, чтобы в графе пропали все P3P_3, чтобы никакого P3P_3 не осталось. Отсюда следует простая переформулировка: давайте выделим все тройки вершин, образующие P3P_3. Тогда расстояние до кластера — это просто минимальное число вершин, которыми нужно проткнуть все P3P_3. То есть теперь я ищу множество SS, пересекающее каждую тройку хотя бы один раз. Понятно такое?

Отсюда сразу можно вывести алгоритм, который будет работать за FPT-время. Как его реализовать? Очень просто: строим SS полным перебором. Изначально S=∅S = \varnothing; если SS не протыкает некоторую тройку, переберу три варианта, что это за элемент. У меня получается дерево рекурсивного перебора: я начинаю с пустого множества SS, и у меня есть некоторая тройка, по которой я делаю ветвление — branching по-английски. Раньше любили это называть расщеплением; я против слова «расщепление», я не понимаю, откуда там расщепление, это ветвление, конечно.

Итак, в тройке три элемента: x1x_1, x2x_2 или x3x_3, и дальше перебор продолжается. Глубина у него будет не больше, чем kk: если вы ищете distance to cluster не больше, чем kk, то это дерево имеет высоту не больше, чем kk. То есть просто полный перебор, который обрубается на глубине kk. Так мы сможем вычислить наш distance to cluster за время 3k⋅nO(1)3^k \cdot n^{O(1)}. Конечно, я думаю, это не оптимальный алгоритм — но у нас в этом курсе нет задачи придумывать оптимальные алгоритмы, которые вычисляют параметры.

Супер, значит, 3k3^k мы получили. Но если 3k3^k вам не нравится и вам хотелось бы вычислять что-то за полином, можно построить 3-приближение. А каким образом его построить? Тут нужно просто сделать другое действие. Если SS не пересекает некоторую тройку, я же знаю, что я обязан содержать что-то из неё, — а давайте я возьму из неё всё целиком, все её элементы. Это не значит, что я одновременно беру все тройки: это просто такой алгоритм, который берёт произвольную ещё не проткнутую тройку и берёт все её элементы. Понятно, что все тройки, из которых я брал элементы, попарно не пересекаются.

Feedback vertex set и рандомизированный алгоритм

По построению все эти тройки не пересекаются. Из каждой я был обязан взять один элемент, а взял три — значит, это просто 33-приближение. То есть вот эта логика даёт мне 3k3^k, а вот эта — 33-приближение.

Замечу, товарищи, что на самом деле эта история работает для очень большого набора классов графов, которые задаются определённым образом. Называется это HH-free graphs, и это вообще отдельная история в структурной теории графов — изучать вот эти классы графов, то есть изучать конечное множество запрещённых графов HH. Кластерные графы — это у нас P3P_3-free graphs. Например, пустой граф — это просто K2K_2-free граф, потому что в нём нет ни одного ребра. Правда, P2P_2 обычно называют K2K_2, потому что это полный граф на двух вершинах. Какие-то ещё простые примеры знакомых нам классов графов, которые так описываются, я вспомнить не могу.

Но суть в том, что класс графов описывается конечным — а иногда и бесконечным — множеством запрещённых подграфов. И когда это множество конечно, всё делается вот таким же образом: у нас есть запрещённые картинки, мы находим запрещённую картинку, перебираем, что из неё надо удалить, и удаляем. Поэтому схема очень общая: для всех таких параметров у нас есть эффективные вычисления. Вопросы? Хорошо, давайте пойдём к следующему параметру.

Следующий параметр у нас будет feedback vertex set. Наверное, зря я стираю эту доску — надеюсь, вы либо запоминаете, либо записываете. Кто помнит, что такое feedback vertex set?

— Расстояние до леса.

Здорово, действительно так: это distance to forest. Лес — это тоже HH-free граф, но тут HH уже бесконечное — это просто набор всех циклов. И, конечно же, мы не можем выделить все циклы в графе, потому что циклов в графе может быть экспоненциально много; точно не полином, если их длина не константная. Кроме того, у нас может быть так, что расстояние до леса маленькое, а циклы очень длинные — достаточно взять один большой-большой длинный цикл. Поэтому этот параметр так просто не даётся: чтобы его посчитать, нужны какие-то преобразования графа.

Что мы сделаем первым делом? Заметим, что произвольную вершину степени 22 можно не удалять. Это не значит, что все вершины степени 22 можно не удалять — это, конечно, неправда. Это значит, что если я возьму какую-то конкретную вершину степени 22, я могу сказать: существует ответ, который её не содержит, существует такое множество, которое её не содержит. Доказывается это очень легко. Какая у меня задача? Разрушить все циклы. И если эта вершина попала в ответ, то понятно, что любой цикл, в котором она лежит, содержит и её, и каждого из её двух соседей, — так что я могу с успехом поменять её на соседнюю вершину.

Поэтому можно сделать следующее: взять вершину степени 22 и стянуть любое из двух инцидентных ей рёбер. Что такое стягивание ребра? Я просто склеиваю эти две вершинки, и больше ничего не меняется; в случае вершины степени 22 это равносильно замене двух её рёбер на одно ребро между её соседями. Это наше преобразование графа, и мы знаем, что если мы найдём ответ в новом графе, то будет ответ и в исходном. Но пока совершенно непонятно, чем нам стало проще жить после того, как мы это сделали.

Тут ещё был некоторый неприятный крайний случай — случай треугольника. Треугольник — это отдельный цикл, который стянуть не получается: если мы просто стянем вершину степени 22, то останется одно ребро. Поэтому нужно разрешить иметь параллельные рёбра, и тогда всё становится понятно: если мы получили пару параллельных рёбер, это просто значит, что одну из двух её вершин надо удалять. Проще всего в этом случае разрешить параллельные рёбра; какого-то другого простого способа избавиться от треугольников я не знаю. Могут возникать и петли, но если петля возникла, мы точно знаем, что эту вершинку надо удалить.

Что мы теперь можем сказать про оставшийся граф? Мы знаем, что степень любой вершины хотя бы 33: ∀v deg⁡(v)⩾3\forall v\ \deg(v) \geqslant 3. А отсюда мы можем посчитать, что рёбер в графе очень много. Сколько рёбер я знаю в графе GG, если минимальная степень равна 33, друзья?

— Три вторых.

Правильно, молодцы, сказали быстрее, чем я написал: ∣E(G)∣⩾32∣V(G)∣|E(G)| \geqslant \tfrac{3}{2}|V(G)|. А в чём фишка? Фишка в том, что когда мы удалим искомое множество SS, то в оставшемся графе число рёбер обязано быть меньше числа вершин — ведь это лес. Согласны с таким? То есть когда я найду свой distance to forest, я точно знаю, что ∣E(G−S)∣<∣V(G−S)∣<∣V(G)∣|E(G-S)| < |V(G-S)| < |V(G)|; в частности, рёбер остаётся меньше, чем ∣V(G)∣|V(G)|. Что отсюда получается? Что очень большая доля рёбер графа должна пропасть.

Давайте посчитаем, какая именно доля — правда, пара у нас поздняя, и считать мне уже сложно. Рассмотрим ∣E(G)∖E(G−S)∣|E(G) \setminus E(G-S)| — множество исчезнувших рёбер. У нас должна пропасть целиком половинка от ∣V(G)∣|V(G)|, а 12∣V(G)∣\tfrac{1}{2}|V(G)| — это хотя бы треть от ∣E(G)∣|E(G)|, правильно? Значит, ∣E(G)∖E(G−S)∣⩾13∣E(G)∣|E(G) \setminus E(G-S)| \geqslant \tfrac{1}{3}|E(G)|. Оценка тут не лучшая, но кажется, что так. Что отсюда следует? Что если я возьму случайное ребро, то с вероятностью хотя бы 13\tfrac{1}{3} этого ребра не будет в оставшемся графе. Согласны? Я ожидал, что там получится одна вторая, но у нас получилась одна треть.

Что мы теперь делаем, товарищи? Мы просто берём случайное ребро, и с вероятностью хотя бы 13\tfrac{1}{3} оно обязано из графа пропасть — а это значит, что какой-то его конец нужно удалить. Так давайте угадаем и конец, который нужно удалить: с вероятностью 12\tfrac{1}{2} мы правильно угадали вершину ответа. Итак: угадаем ребро — это ОК с вероятностью ⩾13\geqslant \tfrac{1}{3}; угадаем конец ребра из SS — это ОК с вероятностью ⩾12\geqslant \tfrac{1}{2}; значит, всё вместе ОК с вероятностью ⩾16\geqslant \tfrac{1}{6}. Оценил я очень грубо, кажется, можно оценить и лучше, но мы с вами не гонимся за константами в этом курсе — у нас приятное обсуждение идей.

И если мы предполагали, что существует некоторое SS размера ∣S∣⩽k|S| \leqslant k, то, повторив эту историю kk раз, мы получаем, что всё ОК с вероятностью ⩾6−k\geqslant 6^{-k}. Согласны? А дальше просто повторим весь алгоритм: повторим C⋅6kC \cdot 6^{k} раз, и будет ОК с вероятностью ⩾1−(1e)C\geqslant 1 - \left(\tfrac{1}{e}\right)^{C}. Здесь, друзья, очень-очень грубо, потому что точно эти вещи я без выкладок быстро не воспроизведу. И обратите внимание: у меня должно было получиться число, стремящееся к единице при увеличении CC, — поэтому именно 1−(1/e)C1 - (1/e)^{C}, а не (1/e)C(1/e)^{C}. Вот так всё и есть, а как это доказывать, вы разберётесь.

Вот и наш могучий параметр — с вероятностным FPT-алгоритмом. А как построить приближение? По той же схеме, что мы делали раньше: давайте возьмём случайное ребро и возьмём оба его конца в ответ. Можно посчитать матожидание всей этой истории и убедиться, что получится нормальное приближение; рассказывать это я сейчас не буду, времени остаётся очень мало. Понятно, как делать приближение на основе вот этой идеи — угадываем ребро, но вместо того, чтобы брать один конец, берём оба?

— Да, можно, конечно, можно. Просто мы пытаемся простыми идеями получить простые алгоритмы.

Там много всяких историй есть. Есть параметризованные алгоритмы, которые работают намного лучше, и они будут не рандомизированные — ведь у нас получился вероятностный алгоритм. Приближённые алгоритмы тоже есть; для feedback vertex set они, по-моему, используют линейное программирование, и это как-то связано с базисом циклов. Правда, базис циклов, по-моему, больше работает для рёбер. В общем, надо думать.

Хорошо, и наш любимый параметр — tree-depth. И тут самое интересное: оказалось, что здесь большая research-задача, не решённая до сих пор. Что про tdtd примерно известно? Известно, что 1.0031.003-приближение NP-трудно, то есть очень близко приблизить NP-трудно — в частности, PTAS не существует. Но, по-моему, никаких других нижних оценок на приближение у нас нет. Есть какие-то разные полиномиальные приближения; я не буду их выписывать, я лучше расскажу, чего бы мы хотели.

Чего мы на самом деле хотим добиться? Мы хотим добиться настоящей штуки. Мы с вами построили single-exponential алгоритм по tdtd — алгоритм, который работает за 2O(td)⋅nO(1)2^{O(td)} \cdot n^{O(1)}, то есть за экспоненту от tdtd на полином от размера инстанса. И для этого мы хотели бы, чтобы tdtd можно было вычислить примерно за такое же время. Причём даже не в точности вычислить: нам хотелось бы хотя бы следующего — за время 2O(td)⋅nO(1)2^{O(td)} \cdot n^{O(1)} вычислить дерево исключений (elimination tree) высоты O(td)O(td). Согласитесь, это решило бы все наши проблемы: мы вычислили его не точно, но точно нам и не нужно было — мы хотели лишь сохранить single-exponential.

То есть мы хотели бы алгоритм, который представляет собой микс из приближённых алгоритмов и параметризованных. Это нормально, это называется FPT approximation algorithm: видите, люди, когда могут что-нибудь придумать, миксуют идеи вместе. И такой алгоритм реально оказался бы полезным. Но это открытая задача.

Резюмирую, что мы примерно знаем про tdtd. Точные оценки я не готовил, потому что считаю, что точные оценки без алгоритмов нам не очень полезны. Кажется, за poly время можно найти дерево исключений высоты ⩽k⋅log⁡3/2k\leqslant k \cdot \log^{3/2} k — то есть приближение с множителем log⁡3/2k\log^{3/2} k, где k=tdk = td, так что сама высота получается порядка td⋅log⁡3/2tdtd \cdot \log^{3/2} td. И можно за время 2O(td2)2^{O(td^2)} вычислить tdtd точно. Но это примеры; я не уверен, что это реально state of the art результаты — у меня, к сожалению, не было времени сравнивать их между собой, я скорее искал, знаем ли мы нужную нам штуку.

И такую штуку мы действительно не знаем. Вроде бы мы подобрались близко: есть какие-то приближения, что-то присутствует, — но мы далеко. Поэтому, когда мы говорим, что у нас есть single-exponential algorithm от tdtd, мы говорим это только при условии, что нам кто-то дал дерево исключений нормальной высоты. Вопросы какие-нибудь? На этом, наверное, у нас всё: дальше говорить я, пожалуй, уже не смогу, что-то устал. Но на вопросы с удовольствием поотвечаю, если они у вас есть.

Вычисление древесной глубины: открытая задача и план курса

Давайте уточним первый пункт. За полиномиальное время можно найти elimination tree высоты не больше klog⁡3/2kk\log^{3/2}k, где k=td(G)k=td(G). Изначально я записал этот пункт как «можно получить klog⁡3/2kk\log^{3/2}k-приближение», но правильнее говорить именно о дереве исключений такой высоты, поэтому хвост про приближение я стираю. Обратите внимание: три вторых здесь — это степень логарифма, log⁡3/2k\log^{3/2}k, а не основание. И вот здесь я сомневаюсь: может быть, в показателе у kk была и двойка. Поэтому рядом я подписываю второй вариант — k2log⁡3/2kk^2\log^{3/2}k.

Я собирал эти оценки через специальных помощников, и они иногда выдавали мне разную информацию. В любом случае всё это гуглится в несколько запросов, точных оценок я здесь специально не добивался — цели такой у меня нет. Хороший вопрос, да: я сам это записал и не уверен. Мне кажется, что скорее верен второй вариант, с квадратом, но нужно отдельное исследование, чтобы установить, какой именно алгоритм у нас есть. Так что к числам на доске относитесь как к ориентиру, а не как к гарантированному state of the art.

Итоговая картина для вычисления древесной глубины такая. Приближение с коэффициентом 1,0031{,}003 уже NP-трудно. Есть однократно экспоненциальный по tdtd алгоритм со временем 2O(td)⋅nO(1)2^{O(td)}\cdot n^{O(1)}. За полиномиальное время мы умеем строить дерево исключений высоты ≤klog⁡3/2k\le k\log^{3/2}k (или k2log⁡3/2kk^2\log^{3/2}k — см. выше), а за время 2O(td2)2^{O(td^2)} умеем вычислять tdtd точно. А вот то, что хотелось бы иметь как минимум, остаётся открытой задачей: за время 2O(td)nO(1)2^{O(td)}n^{O(1)} построить дерево исключений высоты O(td)O(td). Это не домашнее задание, а настоящий открытый вопрос — он так и остаётся на доске с восклицательным знаком.

Потом, когда мы будем изучать параметры посложнее, чем древесная глубина, — а начнём мы, думаю, уже со следующей лекции, — картина станет богаче. Первая треть курса на этом закончилась: сегодня была четвёртая лекция, и дальше начинается вторая треть, про самые сочные параметры. В серединке у нас будут всякие древесные ширины и прочее, прочее.