Нижняя граница для динамической связности

Ключевые слова и синонимы

Динамические деревья (Dynamic trees)

Постановка задачи

Задача о динамической связности требует поддержки структуры графа [math]\displaystyle{ G }[/math] следующими операциями:

insert(u, v): вставка неориентированного ребра (u, v) в граф;

delete(u, v): удаление ребра (u ,v) из графа;

connected(u, v): проверка, находятся ли u и v в одной и той же связной компоненте.

Пусть [math]\displaystyle{ m }[/math] – верхняя граница количества ребер в графе. В данной статье обсуждаются нижние границы клеточного зонда для этой задачи. Обозначим за [math]\displaystyle{ t_u }[/math] сложность вставки и удаления, а за [math]\displaystyle{ t_q }[/math] – сложность проверки.

Задача о частных суммах

Нижние границы для задачи о динамической связности тесно связаны с нижними границами для другой классической задачи – поддержки частных сумм. Формально, задача состоит в том, чтобы поддерживать массив A[1..n], выполняя следующие операции:

update(k, [math]\displaystyle{ \Delta }[/math]: обновление [math]\displaystyle{ A[k] \leftarrow \Delta }[/math];

sum(k): возвращает частную сумму [math]\displaystyle{ \sum^k_{i=1} A[i] }[/math].

testsum(k, [math]\displaystyle{ \sigma }[/math]): возвращает булево значение, указывающее, верно ли, что [math]\displaystyle{ sum(k) = \sigma }[/math].

Чтобы полностью сформулировать задачу, будем считать, что элементы [math]\displaystyle{ A[i] }[/math] берутся из произвольной группы [math]\displaystyle{ G }[/math], содержащей не менее [math]\displaystyle{ 2^{\delta} }[/math] элементов. В модели клеточного зонда с b-битными ячейками обозначим за [math]\displaystyle{ t_u^{\Sigma} }[/math] сложность обновления (update), а за [math]\displaystyle{ t_q^{\Sigma} }[/math] – сложность проверки (testsum) (которая также является нижней границей sum).

Компромисс между [math]\displaystyle{ t_u^{\Sigma} }[/math] и [math]\displaystyle{ t_q^{\Sigma} }[/math] хорошо изучен для всех значений [math]\displaystyle{ b }[/math] и [math]\displaystyle{ \delta }[/math]. Далее будут рассматриваться только нижние границы при стандартных предположениях, что [math]\displaystyle{ b = \Omega(lg \; n) }[/math] и [math]\displaystyle{ t_u \ge t_q }[/math]. Стандартным является предположение [math]\displaystyle{ b = \Omega(lg \; n) }[/math] для верхних границ в модели с оперативной памятью; это предположение также означает, что нижняя граница применима к машине с указателями. При этих условиях Петрашку и Демейн [6] доказали следующее утверждение:

Теорема 1. Сложность задачи о частных суммах удовлетворяет соотношению: [math]\displaystyle{ t_q^{\Sigma} \cdot lg(t_u^{\Sigma} / t_q^{\Sigma}) = \Omega(\delta/b \cdot lg \; n) }[/math].

Заметим, что это совпадает с хрестоматийной верхней границей при использовании дополненных деревьев. Можно построить сбалансированное бинарное дерево над [math]\displaystyle{ A[1], ..., A[n] }[/math] и хранить в каждом внутреннем узле сумму его поддерева. Тогда обновления и запросы затрагивают [math]\displaystyle{ O(lg \; n) }[/math] узлов (и тратят [math]\displaystyle{ O(\lceil \delta\b \rceil) }[/math] времени в каждом из них из-за размера группы). Чтобы уменьшить время запросов, можно использовать B-дерево.

Связь с динамической связностью

Теперь поясним, как из нижних границ для поддержания частных сумм следуют нижние границы для динамической связности. Рассмотрим задачу о частных суммах над группой [math]\displaystyle{ G = S_n }[/math], то есть группой перестановок на [math]\displaystyle{ n }[/math] элементах. Заметим, что [math]\displaystyle{ \delta = lg(n!) = \Omega(n \; lg \; n) }[/math]. Стандартно задается [math]\displaystyle{ b = \Theta(lg \; n) }[/math], так как это естественный размер слова, используемый в верхних границах для динамической связности. Отсюда следует, что [math]\displaystyle{ t_q^{\Sigma} lg(t_u^{\Sigma}/t_q^{\Sigma}) = \Omega(n \; lg \; n) }[/math].

Нижняя граница вытекает из реализации операций поддержки частных сумм с помощью операций поддержки динамической связности. На рис. 1 вершины графа образуют целочисленную сетку размером [math]\displaystyle{ n \times n }[/math]. Каждая вершина инцидентна не более чем двум ребрам, одно из которых соединяется с вершиной в предыдущем столбце, а другое – с вершиной в следующем столбце. Точка [math]\displaystyle{ (x, y_1) }[/math] в сетке соединена с точкой [math]\displaystyle{ (x + 1, A[x](y_1)) }[/math], т. е. ребра между двумя смежными столбцами описывают соответствующую перестановку из вектора частных сумм.

Чтобы реализовать операцию update(x, [math]\displaystyle{ \pi }[/math]), сначала удаляются все ребра между столбцами x и x + 1, а затем вставляются новые ребра согласно [math]\displaystyle{ \pi }[/math]. Это дает [math]\displaystyle{ t_u^{\Sigma} = O(2n \cdot t_u) }[/math]. Для реализации операции testsum(x, [math]\displaystyle{ \pi }[/math]) можно использовать [math]\displaystyle{ n }[/math] запросов connected между парами точек [math]\displaystyle{ (1, у) \rightsquigarrow (х + 1, \pi(у)) }[/math]. Тогда [math]\displaystyle{ t_q^{\Sigma} = O(n \cdot t_q) }[/math]. Заметим, что запрос sum не может быть реализован так же просто. Динамическая связность является основным мотивом для изучения запроса testsum.

Рисунок 1. Построение экземпляра задачи о динамической связности, имитирующего задачу о частных суммах

Нижняя граница теоремы 1 соответствует [math]\displaystyle{ nt_q \cdot lg(2nt_u/nt_q) = \Omega(n \; lg \; n) }[/math]; следовательно, [math]\displaystyle{ t_q \; lg(t_u/t_q) = \Omega(lg \; n) }[/math]. Заметим, что из этой нижней границы следует [math]\displaystyle{ max \{ t_u, t_q \} = \Omega(lg \; n) }[/math]. Лучшая известная верхняя граница (с использованием амортизации и рандомизации) равна [math]\displaystyle{ O(lg \; n(lg \; lg \; n)^3) }[/math] [9]. Известно, что для любого [math]\displaystyle{ t_u = \Omega(lg \; n(lg \; lg \; n)^3) }[/math] компромиссная нижняя граница является строгой. Отметим, что граф в нижней границе всегда является несвязным объединением путей. Из этого следует оптимальность нижних границ для двух важных частных случаев: динамических деревьев [8] и динамической связности в планарных графах [2].

Основные результаты

Понимание иерархий

Эпохи

Для описания техник, связанных с нижними границами, сначала рассмотрим запрос sum и предположим, что [math]\displaystyle{ \delta = b }[/math]. В 1989 году Фредман и Сакс [3] положили начало изучению нижних границ динамических клеточных зондов, по сути, доказав нижнюю границу [math]\displaystyle{ t_q^{\Sigma} \; lg \; t_u^{\Sigma} = \Omega(lg \; n) }[/math]. Заметим, что это означает, что [math]\displaystyle{ max \{ t_q^{\Sigma}, t_u^{\Sigma} \} = \Omega(lg \; n/lg \; lg \; n) }[/math].

На интуитивном уровне их аргументация выглядит следующим образом. В жестком экземпляре будет [math]\displaystyle{ n }[/math] случайных обновлений, за которыми следует один случайный запрос. Оставим [math]\displaystyle{ r \ge 2 }[/math] для последующего определения. Идя назад по времени от запроса, можно сгруппировать обновления в экспоненциально растущие эпохи: последние [math]\displaystyle{ r }[/math] обновлений – это эпоха 1, более ранние [math]\displaystyle{ r^2 }[/math] обновлений – эпоха 2 и т. д. Обратите внимание, что номера эпох увеличиваются с течением времени, и всего существует [math]\displaystyle{ O(log_r \; n) }[/math] эпох.

Для некоторой эпохи [math]\displaystyle{ i }[/math] рассмотрим раскрытие в запросе всех обновлений, выполненных во все эпохи, отличные от [math]\displaystyle{ i }[/math]. Тогда запрос сводится к запросу частных сумм среди обновлений в эпоху [math]\displaystyle{ i }[/math]. Если запрос не касается индекса ниже минимального индекса, обновленного в эпоху [math]\displaystyle{ i }[/math], ответ на запрос остается равномерно случайным, то есть имеет [math]\displaystyle{ \delta }[/math] бит энтропии. Более того, даже если дано, скажем, [math]\displaystyle{ r_i \delta/100 }[/math] бит информации об эпохе [math]\displaystyle{ i }[/math], ответ все равно имеет в среднем [math]\displaystyle{ \Omega(\delta) }[/math] бит энтропии. Это происходит потому, что запрос и обновления в эпоху [math]\displaystyle{ i }[/math] равномерно случайны, поэтому запрос может касаться любой частной суммы этих обновлений равномерно случайным образом. Каждая из частных сумм [math]\displaystyle{ r_i }[/math] является независимой случайной переменной от энтропии [math]\displaystyle{ \delta }[/math].

Теперь можно поинтересоваться, сколько информации доступно для запроса. Пусть в момент запроса каждая ячейка связана с эпохой, в которую она была записана в последний раз. Выбрав эпоху [math]\displaystyle{ i }[/math] равномерно случайным образом, можно привести следующие интуитивные соображения:

1. Ни одна ячейка, записанная в эпохи [math]\displaystyle{ i + 1, i + 2,... }[/math], не может содержать информацию об эпохе [math]\displaystyle{ i }[/math], так как все они были записаны в прошлом.

2. В эпохи [math]\displaystyle{ 1, ..., i - 1 }[/math] было записано [math]\displaystyle{ b t_u^{\Sigma} \cdot \sum_{j = 1}^{i - 1} r^j \le b t_u^{\Sigma} \cdot 2 r^{i - 1} }[/math] бит. Это меньше, чем [math]\displaystyle{ r_i \delta/100 }[/math] бит информации для [math]\displaystyle{ r \gt 200 t_u^{\Sigma} }[/math] (вспомним предположение [math]\displaystyle{ \delta = b }[/math]). Из вышесказанного следует, что ответ на запрос все еще имеет [math]\displaystyle{ \Omega(\delta) }[/math] бит энтропии.

3. Поскольку значение [math]\displaystyle{ i }[/math] равномерно случайно среди [math]\displaystyle{ \Theta(log_r \; n) }[/math] эпох, запрос делает ожидаемое число [math]\displaystyle{ \Theta(t_q^{\Sigma}/log_r \; n) }[/math] зондирований ячеек из эпохи [math]\displaystyle{ i }[/math]. Все запросы, которые не делают ни одного зондирования ячеек в эпоху [math]\displaystyle{ i }[/math], получают фиксированный ответ (энтропия 0), а все остальные запросы получают ответы с энтропией менее [math]\displaystyle{ \delta }[/math]. Поскольку средний запрос имеет энтропию [math]\displaystyle{ \Omega(\delta) }[/math], запрос должен зондировать ячейку из эпохи [math]\displaystyle{ i }[/math] с константной вероятностью. Это означает, что [math]\displaystyle{ t_q^{\Sigma} / log_r \; n = \Omega(1) }[/math], а [math]\displaystyle{ \sum = \Omega(log_r \; n) = \Omega(lg \; n/lg \; t_u^{\Sigma}) }[/math].

Следует оценить двойственность между техникой доказательства и естественными верхними границами, основанными на иерархии. Рассмотрим верхнюю границу, основанную на дереве степени r. Последние r случайных обновлений (эпоха 1), вероятно, равномерно распределены в массиве. Это означает, что обновления касаются разных дочерних элементов корня. Аналогично, r2 обновлений в эпоху 2, скорее всего, коснутся каждого узла на втором уровне дерева, и так далее. Нижняя граница свидетельствует, что запрос должен пройти путь от корня к листьям, прощупывая узел на каждом уровне дерева (что эквивалентно одной ячейке из каждой эпохи).

Иерархии времени

Несмотря на значительное усовершенствование техники нижних границ, нижняя граница £2(\gn/\g\gn) не была улучшена до 2004 года. Тогда Петрашку и Демейн [ ] показали оптимальное ограничение tq \g(t*/tf) = £2(\g n), что означает max{fjf, tf} = £2(lg n). Для простоты нижеследующее обсуждение пренебрегает этим компромиссом и просто набрасывает нижнюю границу Q (lg n).

Техника подсчета Петрашку и Демейна [ ] довольно сильно отличается от техники эпох; см. рис. 2. Жесткий экземпляр представляет собой последовательность из n операций, чередующих обновления и запросы. Они рассматривают сбалансированное бинарное дерево на временной оси, каждый лист которого является операцией. Теперь для каждого узла дерева авторы предлагают подсчитать количество клеточных зондирований, выполненных в правом поддереве, относительно клетки, записанной в левом поддереве. Каждое зондирование подсчитывается ровно один раз, для получения наименьшего общего предка времен чтения и записи.

Рисунок 2. Анализ зондирования клеток в методах a, основанном на эпохах, и b, основанном на иерархии времени

Теперь рассмотрим два «братских» поддерева, каждое из которых содержит k операций. Предполагается, что k/2 обновлений в левом поддереве и k/2 запросов в правом поддереве будут чередоваться в пространстве индексов. Таким образом, запросы в правом поддереве запрашивают Q(k) различных частных сумм обновлений в левом поддереве. Таким образом, правому поддереву «нужно» Q(k&) бит информации о левом поддереве, и эта информация может поступать только из ячеек, записанных в левом поддереве и прочитанных в правом. Отсюда следует нижняя граница в Q(k) зондов, связанных с родителем «братских» поддеревьев. Эта граница линейна по числу листьев, так что, суммируя по всему дереву, мы получаем полную нижнюю границу Q(n\g n), или стоимость £?(lg n) на операцию.

Оптимальное построение эпох

Как ни удивительно, но Петрашку и Тарнрфа [ ] удалось воспроизвести оптимальный компромисс теоремы 1 с минимальными изменениями рассуждений об эпохах. В старой версии этих рассуждений информация, раскрываемая эпохами 1; : : : : ; i - 1 об эпохе i, ограничивалась количеством ячеек, записанных в эти эпохи. Ключевая идея заключается в том, что не менее удачным ограничением является количество ячеек, прочитанных в эпохи 1; : : : : ; i - 1 и записанных в эпоху i.

В принципе, все операции чтения ячеек из эпохи i - 1 могут читать данные из эпохи i, что делает эти две границы идентичными. Однако можно рандомизировать построение эпох, вставляя запрос после непредсказуемого количества обновлений. Такая рандомизация «сглаживает» распределение эпох, из которых считываются ячейки, то есть запрос считывает O(fl?/logr n) ячеек из каждой эпохи, что выходит за рамки случайности в построении эпохи. Тогда обновления O(r'~l) в эпохи 1; : : : ; i - 1 читают только O(r'~l ■ fjf/logr n) ячеек из эпохи i. Этой информации недостаточно, если r 3> t£/logr n = 0(t^lt^), из чего следует, что tf = <2(logr n) = QQgn/]g(tZ/tf)).

Технические трудности

Недетерминизм

Нижние границы, описанные выше, основаны на том, что запрос суммы должен выводить Q (<5) бит информации о каждом запросе. Если мы имеем дело с запросом о принятии решения для testsum, то аргумент, основанный на энтропии вывода, уже не работает.

Наиболее удачной идеей для запросов на принятие решений было преобразование их в запросы с небулевым результатом в расширенной модели клеточного зонда, допускающей недетерминизм. В этой модели алгоритм запроса может порождать произвольное количество вычислительных потоков. Каждый поток может сделать tq клеточных зондирований, после чего он должен либо завершиться ответом «отказ», либо вернуть ответ на запрос. Все потоки, не завершающиеся отказом, должны возвращать один и тот же результат. В этой модели запрос с произвольным результатом эквивалентен запросу на принятие решения, поскольку можно просто недетерминистским образом угадать ответ, а затем проверить его.

Исходя из вышесказанного, задача состоит в том, чтобы доказать хорошие нижние границы для суммы даже в недетерминистской модели. Недетерминизм поколебал представление о том, что при анализе эпохи i имеют значение только запросы к ячейкам эпохи i. Проблема в том, что запрос может не знать, какие из его зондирований действительно относятся к эпохе i. Зонд, считывающий ячейку из предыдущей эпохи, предоставляет по крайней мере некоторую информацию об эпохе i: ни одно обновление в эту эпоху не решило перезаписать клетку. Ранее это не было проблемой, поскольку целью было только исключить случай, когда в эпоху i существует ноль зондирований. Теперь, однако, различные потоки могут зондировать любую ячейку в памяти, и невозможно определить, какие потоки на самом деле избегают зондирования чего-либо в эпоху i. Другими словами, между эпохой i и запросом существует скрытый канал связи, в котором эпоха может использовать выбор того, какие ячейки записывать, чтобы передать информацию запросу.

Существует две основные стратегии для работы с алгоритмами недетерминированных запросов. Хасфельдт и Раухе [4] приводят доказательство, основанное на некоторых интересных наблюдениях о комбинаторике недетерминированных запросов. Петрашку и Демейн [6] используют силу самого недетерминизма для вывода небольшого сертификата, исключающего бесполезные зондирования ячеек. Из последнего результата вытекает оптимальная нижняя граница Теоремы 1 для testsum и, следовательно, логарифмическая нижняя граница для динамической связности.

Альтернативные истории

Описанная выше схема опирается на фиксацию всех обновлений в эпохи, отличные от i, к среднему значению и утверждение, что ответ на запрос все равно имеет большую вариативность, зависящую от обновлений в эпоху i. Это верно для задач агрегирования, но не для задач поиска. Если искомый элемент найден с равной вероятностью в любой эпохе, то фиксация всех остальных эпох делает эпоху i нерелевантной с вероятностью 1 - 1/(logr n).

Олстрап и др. [] предложили очень интересное усовершенствование этой техники, доказав нижние границы Q (lg n/ lg lg n) для впечатляющей коллекции задач поиска. Интуитивно их идея заключается в рассмотрении O(logr n) альтернативных историй обновлений, выбранных независимо друг от друга случайным образом. Эпоха i релевантна хотя бы в одной из историй с константной вероятностью. С другой стороны, даже если известно, что эпохи с 1 по i - 1 узнали об эпохе i во всех историях, ответить на случайный запрос все равно сложно.

Сложность битового зонда

Интуитивно понятно, что если размер слова равен b = 1, то нижняя граница связности должна быть примерно £?(lg 2n), поскольку для запроса требуется £?(lg n) бит из каждой эпохи. Однако исключить что-либо, кроме нулевых зондирований в эпоху, оказывается сложно по той же причине, по которой сложен недетерминированный случай. Не давая вполне удовлетворительного понимания этой проблемы, Петрашку и Тарнифа [ ] используют большой набор трюков, чтобы продемонстрировать нижнюю границу £?((lg n/lglg n)2) для динамической связности. Более того, они рассматривают проблему частных сумм в Z2 и показывают нижнюю границу £?(lg n/lglg lg n), трижды логарифмически удаленную от верхней.

Применение

Обсуждаемая здесь нижняя граница путем простых редукций распространяется практически на все естественные полностью динамические задачи на графах [6].

Открытые вопросы

Наиболее важной задачей будущих исследований является получение нижней границы !(lg n) на операцию для некоторой динамической структуры данных в модели клеточного зонда с размером слова @(lg n). Милтерсен [ ] определяет набор технических условий для того, что считается решением такой задачи. В частности, задача должна быть проблемой динамической принадлежности языку. Для задачи о частных суммах, хотя операция sum вполне изучена, testsum все еще не имеет строгих границ для определенных диапазонов параметров [ ]. Кроме того, получение строгих границ в модели битового зонда для частных сумм в Z2 представляется довольно сложной задачей.

Литература

1. Alstrup, S., Husfeldt, T., Rauhe,T.: Marked ancestor problems. In: Proc. 39th IEEE Symposium on Foundations of Computer Science (FOCS), 1998, pp. 534-543

2. Eppstein, D., Italiano, G.F., Tamassia, R., Tarjan, R.E., Westbrook, J.R., Yung, M.: Maintenance of a minimum spanning forest in a dynamic planar graph. J. Algorithms 13,33-54 (1992). See also SODA'90

3. Fredman, M.L., Saks, M.E.: The cell probe complexity of dynamic data structures. In: Proc. 21st ACM Symposium on Theory of Computing (STOC), 1989, pp. 345-354

4. Husfeldt, T., Rauhe, T.: New lower bound techniques for dynamic partial sums and related problems. SIAM J. Comput. 32,736-753 (2003). See also ICALP'98

5. Miltersen, P.B.: Cell probe complexity-a survey. In: 19th Conference on the Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 1999 (Advances in Data Structures Workshop)

6. Patrascu, M. and Demaine, E.D.: Logarithmic lower bounds in the cell-probe model. SIAM J. Comput. 35, 932-963 (2006). See also SODA'04 and STOC'04

7. Patrascu, M., Tarnija, C.: On dynamic bit-probe complexity. Theor. Comput. Sci. 380,127-142 (2007). See also ICALP'05

8. Sleator, D.D., Tarjan, R.E.: A data structure for dynamic trees. J. Comput. Syst. Sci. 26, 362-391 (1983). See also STOC'81

9. Thorup, M.: Near-optimal fully-dynamic graph connectivity. In: Proc. 32nd ACM Symposium on Theory of Computing (STOC), 2000, pp. 343-350