Учитывая взвешенный знак, существует ли алгоритм O (V + E) для замены каждого веса суммой весов его предков?

Проблема, конечно, в двойном учете. Это достаточно просто сделать для определенных классов DAG = дерева или даже последовательно-параллельного дерева. Единственный алгоритм, который я нашел, который работает с общими группами доступности баз данных в разумные сроки, является приблизительным (диффузия Synopsis), но увеличение его точности является экспоненциальным по количеству бит (и мне нужно много бит).

Справочная информация: эта задача выполняется (несколько раз с разными «весами») в рамках вычислений вероятности в BBChop (http://github.com/ealdwulf/bbchop) программе для поиска случайных ошибок (то есть байесовской версии '). git bisect '). Таким образом, рассматриваемая DAG является историей изменений. Это означает, что число ребер вряд ли приблизится к квадрату числа узлов, скорее всего, оно будет меньше, чем k раз числа узлов для небольшого k. К сожалению, я не нашел никаких других полезных свойств ревизионных групп DAG. Например, я надеялся, что самый большой трехсвязный компонент будет расти только как квадратный корень из числа узлов, но, к сожалению (по крайней мере, в истории ядра Linux), он растет линейно.

Мы предполагаем, что веса вершин могут быть произвольными натуральными числами или, точнее, они могут быть натуральными числами не более 2 ⁿ . Тогда текущая задача не может быть выполнена даже в несколько более слабой временной привязке O ( n ² ), если только транзитивное замыкание произвольного ориентированного графа не может быть вычислено за время O ( n ² ), где n обозначает количество вершин. (Обратите внимание, что алгоритм O ( n ² ) времени для транзитивного замыкания будет прорывом.) Это противоречит следующему утверждению:

Претензии . Если текущая задача может быть выполнена за время O ( n ² ), транзитивное замыкание произвольного ориентированного графа, заданного в качестве его матрицы смежности, можно вычислить за время O ( n ² ) (предполагая некоторую разумную вычислительную модель).

Доказательство . В качестве предварительной обработки мы вычисляем разложение сильно связанного компонента заданного ориентированного графа G за время O ( n ² ), чтобы получить DAG G ′. Обратите внимание , что если мы можем вычислить транзитивное замыкание G ', мы можем реконструировать транзитивное замыкание G .

Теперь присвойте вес 2 ⁱ каждой вершине i DAG G ′ и используйте алгоритм для текущей задачи. Тогда двоичное представление суммы, присваиваемой каждой вершине i, точно описывает множество предков i , другими словами, мы вычислили транзитивное замыкание G ′. КЕД .

Обратное утверждение также верно: если вы можете вычислить транзитивное замыкание данного DAG, легко вычислить требуемые суммы, выполнив дополнительную работу за время O ( n ² ). Следовательно, теоретически вы можете выполнить текущую задачу за время O ( n ^2.376 ), используя алгоритм транзитивного замыкания, основанный на алгоритме умножения матриц Копперсмита-Винограда .

Редактировать : Редакция 2 и более ранние версии не содержали предположения о диапазоне весов вершин в явном виде. Пер Вогсен указал в комментарии, что это неявное предположение не может быть разумным (спасибо!), И я согласен. Даже если произвольные веса не требуются в приложениях, я предполагаю, что этот ответ мог бы исключить некоторые подходы следующим рассуждением: «Если бы этот подход работал, он дал бы алгоритм для произвольных весов, который исключается, если только переходный замыкание может быть вычислено за время O ( n ² ) ».

Редактировать : Версия 4 и ранее указали направление ребер неправильно.

Это расширение моего комментария к ответу Цуёси. Я думаю, что отрицательный ответ на вопрос можно сделать безоговорочным.

$\omega(n)$$O(n)$

$G_{r,c}$$r \times c$$r$$r$$c$

$r = (\log\ n)/2$$c = 2n/\log\ n$

$\sqrt{n}$$\omega(\log\ n)$

$\omega(n)$$2c(r-1) = O(n)$

Дело в том, что основной частичный порядок является плотным, но DAG представляет его транзитивное сокращение, которое может быть редким.

Это неправильно и основано на недоразумении по этому вопросу. Спасибо Tsuyoshi за терпеливое указание на мою ошибку. Уход в случае, если другие совершат ту же ошибку.

$k$

$k$$O(k|V|)$

$O(|V|+|E|)$

Этот подход также должен хорошо работать, если есть несколько узлов со многими непосредственными предшественниками, если они относительно редки.