Нужно ли называть матричное умножение раз, чтобы найти коготь

20

Коготь - это . Тривиальный алгоритм обнаружит коготь за времени. Это можно сделать в , где - показатель быстрого умножения матриц следующим образом: возьмите подграф, индуцированный для каждой вершины , и найдите треугольник в его дополнение.K1,3O(n4)O(nω+1)ωN[v]v

Насколько я знаю, эти основные алгоритмы известны только. Спинрад перечислил в своей книге «эффективные представления графов» обнаружение когтя за время как открытую проблему (8.3, стр. 103). Для нижней границы мы знаем, что алгоритм -времени будет подразумевать алгоритм времени для нахождения треугольника. Таким образом, мы можем рассматривать \ Omega (n ^ \ omega) как нижнюю границу.o(nω+1)O(nc)O(nmax(c,2))Ω(nω)

Вопрос:

  1. Есть ли прогресс в этом. Или какой-либо прогресс в показе это невозможно?
  2. Есть ли другие естественные проблемы с алгоритмами O(nω+1) , которые являются лучшими?

Замечание:

  1. Я явно прошу об обнаружении когтя вместо распознавания без когтей графов. Хотя алгоритм обычно решает оба, есть несколько исключений.
  2. В «Справочнике алгоритмов и теоретической информатики» утверждается, что его можно найти за линейное время, но это была только опечатка (см. «Эффективное представление графа»).
Исин Цао
источник
Вы можете использовать метод Алона и др. Для нахождения треугольника в O(|E|1.41) , для каждого узла, который заканчивается в O(|V||E|1.41) который лучше, чем |V|ω+1 если граф не слишком плотный.
РБ
@RB, спасибо, что указали на это. Основная идея по-прежнему состоит в том, чтобы запускать алгоритм what -треугольника-обнаружения n раз, чего я хочу избежать.
Исинь Цао
Как мы можем ожидать найти какой-то алгоритм, который не связан с поиском треугольника? Потому что каким бы ни был алгоритм, следует проверять соседей каждой вершины. Я имею в виду, что свойство является очень локальным свойством, за исключением того, что с постоянной разностью факторов следует видеть каждую вершину. (Или я не могу представить какой-либо естественный алгоритм, который избегает этой местности). У тебя есть хоть какая-то смутная идея?
Саид
2
Может быть, стоит упомянуть, что, если мы можем найти коготь за время f (n), мы также можем найти треугольник за время f (n + 1) (просто возьмите дополнение графа и добавьте еще одну вершину, связанную с каждым ), поэтому мы не должны надеяться найти что-то лучше, чем . nω
domotorp
1
@domotorp, кажется, что часть ясна, наоборот неясно, я имею в виду, почему нам нужен линейный поиск. Как также указал Yixin, может быть есть другой алгоритм, который не использует алгоритм поиска треугольника и решает проблему в , который, я думаю, трудно найти такой алгоритм и, вероятно, проще показать, что любой алгоритм использует поиск треугольника в качестве подпрограммы (или может быть преобразован) с линейным поиском по нему. o(nω+1)
Саид

Ответы:

16

Я думаю, что мы можем сделать немного лучше, чем для плотных графов, используя умножение прямоугольной матрицы. Аналогичная идея была использована Эйзенбрандом и Грандони («О сложности клики с фиксированным параметром и доминирующим множеством», Теоретическая компьютерная наука, том 326 (2004) 57–67) для обнаружения 4 клик.O(n1+ω)

Пусть - граф, на котором мы хотим обнаружить существование когтя. Пусть множество (упорядоченных) пар вершин в . Рассмотрим следующую булеву матрицу размера: каждая строка индексируется некоторой , каждый столбец индексируется некоторой , и соответствующая запись равна единице тогда и только тогда, когда , и . Рассмотрим булеву матрицу произведение и транспонированной . Граф имеет коготь тогда и только тогда, когда он существуетG=(V,E)AVM|V|×|A|uV(v,w)A{u,v}E{v,w}E{u,w}EMMTG{u,v}E такой, что запись в строке, индексированной и столбце, индексированном равна единице.MMTuv

Сложность этого алгоритма, по сути, заключается в сложности вычисления логического произведения матрицы матрицу , где обозначает количество вершин в графе. Известно, что такое матричное произведение может быть вычислено за время , что лучше, чем для наилучшей известной верхней границы . Конечно, если (как предполагалось), то оба подхода дают одинаковую сложность .n×n2n2×nnO(n3.3)O(n1+ω)ωω=2O(n3)

Франсуа Ле Галль
источник
Большой! Это именно то, что я хочу для моего первого вопроса: только один вызов умножения матриц, хотя и больший. Я буду ждать больше комментариев или ответов на мой второй вопрос, прежде чем принять его в качестве ответа.
Исин Цао
15

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

Клокс, Тон; Крач, Дитер; Мюллер, Хайко (2000), «Эффективный поиск и подсчет малых индуцированных подграфов», Письма обработки информации 74 (3–4): 115–121, doi: 10.1016 / S0020-0190 (00) 00047-8, MR 1761552.

Первое наблюдение заключается в том, что при умножении матриц матрицы на самом деле не , а где - степень каждой вершины, потому что то, что вы ищете, является ко-треугольником. в окрестности каждой вершины.n×nd×dd

Во-вторых, в графе без когтей каждая вершина должна иметь соседей. В противном случае множество соседей будет иметь слишком мало ребер, чтобы избежать добавления треугольника в дополнение. Поэтому, когда вы выполняете умножение матриц, вам нужно делать это только на матрицах размером а не .O(m)O(m)n

Кроме того, каждое ребро может вносить вклад в размер задачи умножения матриц только для двух вершин, ее конечных точек. Наихудший случай случается, когда для общего размера этих задач умножения матриц распределяется в подзадач размером каждая, что дает общую временную границу , улучшение для разреженных графов над границей упомянутое R B.2mO(m)O(m)O(m(1+ω)/2)O(nmω/2)

Дэвид Эппштейн
источник
Вау, это умная идея, я думал о том, возможно ли выполнить сублинейный поиск (фактически опровергая это), и даже не думал о внутренних свойствах проблемы.
Саид
Спасибо, Дэвид. Я оставляю это открытым на мгновение, поскольку мой второй вопрос, кажется, еще не замечен.
Исинь Цао