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

34

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

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

Эолдуалф
источник
Просто чтобы уточнить: вес имеют только узлы, а не ребра?
Генрих Апфельмус
Да, только узлы.
Ealdwulf
4
Похоже, это почти дубликат cstheory.stackexchange.com/questions/553/… ?
Юкка Суомела
на самом деле это кажется более общим, поскольку присвоение весов единиц всем вершинам сводит эту проблему к проблеме достижимости.
Суреш Венкат
Приближение, кажется, не трудно сделать с некоторыми дополнительными факторами полилога ...
Сариэль Хар-Пелед

Ответы:

17

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

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

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

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

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

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

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

Цуёси Ито
источник
4
Вчера вечером я думал об этом, так как одно практическое решение использует битовые векторы для подсчета исключений. Я предполагаю, что единственный вопрос заключается в том, разумно ли предположить, что веса могут иметь длину в битах, пропорциональную n. На практике я могу представить, что веса ограничены некоторым k, так что максимально возможная сумма равна kn, что недостаточно для того, чтобы использовать этот трюк.
В Вогнсен
@Per: Я согласен, что предположение, что веса вершин могут быть n-битными целыми числами, может быть сомнительным. Я отредактировал ответ, чтобы сделать это предположение явным. Благодарность!
Цуёси Ито
1
@Per: я понял, что если веса вершин представляют собой целые числа, ограниченные O (1), проблема сводится к случаю, когда все вершины имеют вес 1, путем дублирования вершин подходящим способом.
Цуёси Ито
К сожалению, я не вижу ответа в этой теме на проблему подсчета. Подсчет содержит логарифмически меньше информации, чем перечисление транзитивного замыкания, O (n log n) против O (n ^ 2), поэтому я не понимаю, как может работать прямое сокращение.
Per Vognsen
Кстати, интересная версия этой проблемы заключается в том, что мы имеем ограничение на фактор ветвления и информацию о росте размеров поколений (в топологическом смысле) DAG. Если рост экспоненциальный, шаблон по сути древовидный. Что, если он линейный, логарифмический, квадратичный и т. Д.?
Per Vognsen
2

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

ω(n)O(n)

Gr,cr×crrc

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

nω(log n)

ω(n)2c(r1)=O(n)

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

Андраш Саламон
источник
Этот аргумент интересен, но я не уверен, что его можно превратить в доказательство какого-либо интересного утверждения. Учитывая повсеместную трудность доказательства нижних границ проблем, этот аргумент кажется мне сложным.
Tsuyoshi Ito
@ Tsuyoshi: я думаю, что существование должно работать через вероятностный аргумент, а нижняя граница слабая, поэтому, похоже, для этого достаточно места для работы. Но вы правы, это волнистое выражение, что фраза «не подлежащие повторному использованию дополнения в среднем» нуждается в лучшем обосновании.
Андрас Саламон
-2

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

k

kO(k|V|)

O(|V|+|E|)

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

Андраш Саламон
источник
4
Я этого не получал. Как избежать двойного счета, когда DAG не является деревом? Фактически, если я не ошибаюсь, общий случай может быть сведен к случаю, когда каждая вершина имеет не более двух предшественников, и любой алгоритм с линейным временем для последнего случая дает алгоритм времени строки для общего случая.
Цуёси Ито
O(|V|+|E|)k
Боюсь, что вы неправильно поняли мой комментарий. Я ставлю под сомнение правильность вашего алгоритма, а не время выполнения. Предположим, что DAG с четырьмя вершинами A, B, C, D с ребрами A → B → D и A → C → D с каждой вершиной, имеющей некоторый вес. После вычисления частичных сумм для B и C, вы не можете просто добавить частичные суммы для B и C, чтобы вычислить сумму для D, потому что это добавило бы вес вершины A дважды.
Цуёси Ито
u<vw(u)
1
Да. И теперь я помню, что когда я впервые увидел этот вопрос, я неправильно прочитал вопрос и подумал, что это будет очевидно. Но нет, реальный вопрос сложнее этого. Время, чтобы подумать….
Цуёси Ито