Имея 4-циклический свободный граф

Проблема цикла заключается в следующем: $k$

Экземпляр: неориентированный граф с вершинами и до $G$ $n$ края. $n \choose 2$

Вопрос: существует ли (правильный) цикл в ? $k$ $G$

Предыстория: для любого фиксированного мы можем решить цикл за времени. $k$ $2k$ $O(n^2)$

Рафаэль Юстер, Ури Цвик: Поиск еще более быстрых циклов. SIAM J.
Discrete Math. 10 (2): 209-222 (1997)

Тем не менее, неизвестно, сможем ли мы решить 3-тактный (т. Е. 3-кликовый) менее чем за время умножения матриц.

Мой вопрос: если предположить, что в нет 4-циклов, можем ли мы решить задачу с 3 циклами за времени? $G$ $O(n^2)$

Дэвид предложил подход для решения этого варианта задачи с 3 циклами за времени. $O(n^{2.111})$

graph-theory graph-algorithms clique polynomial-time fixed-parameter-tractable Майкл Вехар
источник

Кажется, что если наименьший цикл графа

имеет длину не менее 5, то он имеет не более

G

$G$

края. Ссылка:link.springer.com/article/10.1007%2FBF01787638

O (n^{\frac{3}{2}})

$O(n^{\frac{3}{2}})$

Майкл Вехар

Дополнительную информацию можно найти в этом документе: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.94.8121

Майкл Вехар,

Я думаю, что вас также могут заинтересовать Айзенбранд, Фридрих и Фабрицио Грандони. «О сложности фиксированного параметра клика и доминирующего множества». Теоретическая информатика 326.1 (2004): 57-67. (Если вы еще не знали об этом).

Юхо

Ответы:

Да, это известно. Он появляется в одной из обязательных ссылок на поиск треугольника ...

А именно, Итай и Родех показывают в SICOMP 1978, как найти за время цикл в графе, который имеет самое большее на одно ребро, чем цикл минимальной длины. (См. Первые три предложения тезисов здесь: http://www.cs.technion.ac.il/~itai/publications/Algorithms/min-circuit.pdf ) Это простая процедура, основанная на свойствах в ширину поиск. $O(n^2)$

Итак, если ваш график свободен от 4-х циклов и есть треугольник, их алгоритм должен вывести его, потому что он не может вывести 5-ти или более циклов.

Райан Уильямс
источник

$O(m^{2\omega/(\omega+1)})$ $\omega$ $\omega<2.373$ $m=O(n^{3/2})$ $4$ $3$ $O(n^{3\omega/(\omega+1)})=O(n^{2.111})$

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

Это круто! Я очень ценю это. :)

Майкл Вехар

O (n^{\frac{3}{2}})

$O(n^{\frac{3}{2}})$

2 k

$2k$

O (n^{1 + \frac{1}{k}})

$O(n^{1+\frac{1}{k}})$

O (n^{\frac{4}{3}})

$O(n^{\frac{4}{3}})$

O (n^{1.876})

$O(n^{1.876})$

k > 2

$k > 2$

G

$G$

2 k

$2k$

G

$G$

G

$G$

k = 2

$k = 2$

O (n^{2.111})

$O(n^{2.111})$