Временная сложность подсчета треугольников в плоских графах

16

Подсчет треугольников в общих графах можно сделать тривиально за раз, и я думаю, что делать намного быстрее сложно (ссылки приветствуются). Как насчет планарных графиков? Следующая простая процедура показывает, что это можно сделать за O ( n log n ) времени. У меня вопрос двоякий:O(n3)O(nlogn)

  • Какая ссылка для этой процедуры?
  • Можно ли сделать время линейным?

Из алгоритмического доказательства теоремы о плоском сепараторе Липтона-Тарьяна мы можем за время, линейное по размеру графа, найти разбиение вершин графа на три множества , в которых нет ребер с одной конечной точкой в A, а другой в B , S имеет размер, ограниченный O ( A,B,SABSи обаA,Bимеют размеры, ограниченные сверху 2O(n)A,B числа вершин. Обратите вниманиечто любой треугольник на графике либо целиком лежит внутриAили полностью внутриBили использованияпо меньшей мере одна вершинаSс двумя другими вершинами изASили оба изBS. Таким образом, достаточно посчитать количество треугольников в графе наSи соседейSвA(и аналогично дляB). Обратите внимание, чтоSи егоA-окрестности индуцируютk-строчный плоский граф (указанный граф является подграфом плоского графа диаметром4).23ABSASBSSSABSAk4). Таким образом, подсчет количества треугольников в таком графе может быть осуществлен непосредственно динамическим программированием или применением теоремы Курселя (я точно знаю, что такая версия для подсчета существует в мире Logspace Эльберфельдом и др., И я предполагаю, что она также существует в линейном мире времени), поскольку формирование ненаправленного треугольника является свойством и поскольку разложение дерева ограниченной ширины легко получить из вложенного плоского графа k- кривой.MSO1k

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

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

SamiD
источник
6
Вы можете посчитать треугольники в общих графах, взяв матрицу смежности и вычислив t r ( A 3 ) / 6 . Это занимает n ω времени, где ω < 2.373 - показатель умножения матриц. Atr(A3)/6nωω<2.373
Райан Уильямс
@RyanWilliams Вы правы, конечно! Я обновлю вопрос.
SamiD

Ответы:

20

Число вхождений любого фиксированного подграфа H в планарный граф G можно посчитать за время O (n), даже если H отключен. Это и некоторые связанные с ним результаты описаны в статье Дэвида Эппштейна (1999 г.) « Изоморфизм подграфа в плоских графах и смежные проблемы »; см. теорему 1. В работе действительно используются методы ширины дерева.

Барт Янсен
источник
19

Хотя ответ Барта Янсена решает общий случай подсчета подграфа, известно, что проблема подсчета (или перечисления) всех треугольников в плоском графе (или, в более общем случае, в любом графе ограниченной древовидности) является линейным временем гораздо дольше. Видеть

C. Пападимитриу и М. Яннакакис. Кликовская задача для плоских графов. Информ. Proc. Письма 13 (1981), стр. 131–133.

и

N. Chiba и T. Nishizeki, Алгоритмы и алгоритмы распечатки подграфа, SIAM J. Comput. 14 (1985), с. 210–223.

Дэвид Эппштейн
источник