Известна ли сложность этой проблемы пути?

9

Экземпляр: неориентированный графGс двумя выделенными вершинами и целым числом .stk0

Вопрос: существует ли путь в , такой, что путь пересекает не болееstGkтреугольники? (Для этой задачи говорят, что путь пересекает треугольник, если путь содержит хотя бы одно ребро из треугольника.)

Андрас Фараго
источник
3
Это неправильно? Мы назначаем вес каждому ребру и затем находим кратчайший путь. Вес каждого ребра - это количество треугольников, которые включают это ребро. Вес этого пути не равен количеству встречаемых треугольников, но это первый путь с минимальным количеством треугольников. (Возможная проблема состоит в том, что мы можем считать один или несколько треугольников дважды, потому что мы посещаем два ребра этого треугольника, но причина, по которой мы выбираем их, состоит в том, что они меньше, чем проходя через другой край треугольника, и у нас также есть простые средства пути два ребра треугольника находятся рядом друг с другом).
Саид
3
@ Seed Я не понимаю: каков аргумент, что перерасчет не заставляет вас выбирать неоптимальный путь? Ваш алгоритм, безусловно, является 2-приближением. Может быть, исправить это добавить край(u,w) для каждого пути uvw с весом, равным количеству треугольников, содержащих оба (u,v) а также (v,w)
Сашо Николов
2
Правильно, мы можем перейти от u к v, а затем выбрать x (какой-то другой узел, не входящий в треугольник uvw), а затем перейти к w, что неправильно (моя ошибка заключалась в том, что я пропустил между вершинами, которых нет в треугольнике uvw) , но с вашим исправлением это правильно, потому что для каждого пути с α треугольники в исходном графе есть путь веса αво вспомогательном графе. Кроме того, вес пути в новом графе всегда равен как минимум количеству треугольников в соответствующем пути в исходном графе.
Саид
1
Я немного больше об этом думаю, даже после исправления это не работает. Извините, Андрас, если я принес неверную надежду. Чтобы понять, почему исправление является неправильным, рассмотрим вершиныu>v>w>x в пути P и у нас есть треугольник u,v,w а также v,w,x и предположим, что края vx а также uwслучаются слишком много треугольников. Если мы используем искусственное новое ребро, которое соединяетu>w тогда мы посчитали треугольник v,w,xдважды. PS: мои рассуждения снова были неправильными, потому что я думал, что мы просто заменимu>v а также v>w с новым (мульти) краем u>w, Если мы добавим эти искусственные ребра для каждого пути, это будет работать тривиально. Кажется, это NPC.
Саид
1
Моя идея не сработает - мне нужно поддерживать несколько наборов, и я думаю, что их будет слишком много.
reinierpost

Ответы:

1

Предположим, что в G,

Для каждого ребра между узлами vi а также vj в G, позволять E[i,j]=1, а также E[i,j]=0если нет края. вычислениеn×n матрица C[i,j]=k=1nE[i,k]E[k,j], который дает количество двухшаговых путей между каждой парой узлов vi а также vj, Тогда для края междуvi а также vj в G вычисление D[i,j]=E[i,j]C[i,j] иначе установлено D[i,j]=, который дает количество треугольников, частью которых является ребро (или бесконечность, если ребра нет). Матричное умножение, необходимое для вычисленияC расходы O(n3) (может быть вычислено быстрее в зависимости от разреженности G).

Теперь вычислим n×n матрица Aтакой, что A[i,j]=min(D[i,j],mink(D[i,k]+D[k,j]E[i,j])), A все кратчайшие пути в D длиной до двух дополнен, чтобы учесть пути, которые идут по двум краям некоторого треугольника.

Теперь просто вычислите кратчайший путь между vi а также vj в G на новом графике которого A является (взвешенной) матрицей смежности с использованием Дейкстры (поскольку все ребра-веса положительны), т.е. A[i,j]k, где A это замыкание над тропическим полукольцом (которое дает матрицу расстояний).

Эдгар
источник