Оптимальный алгоритм нахождения обхвата разреженного графа?

14

Интересно, как найти обхват разреженного неориентированного графа. Под разреженным я подразумеваю . Под оптимальным я подразумеваю минимальную временную сложность.|E|=O(|V|)

Я думал о некоторой модификации алгоритма Тарьяна для неориентированных графов, но я не нашел хороших результатов. На самом деле я думал, что если бы я мог найти 2-связные компоненты в , то я мог бы найти обхват посредством некоторой индукции, которая может быть достигнута из первой части. Возможно, я не на том пути. Любой алгоритм, асимптотически лучше, чем (т. ), приветствуется.Θ ( | V | 2 ) o ( | V | 2 )O(|V|)Θ(|V|2)o(|V|2)

Saeed
источник
1
У Вирджинии Василевской Уильямс и Райана Уильямса есть статья, показывающая, что нахождение оборота в общих графах эквивалентно APSP при субкубических преобразованиях. Я не знаю, верно ли это соотношение для разреженных графов, но это означает, что переход к субквадратичному может быть трудным. Я позволю любому из них опубликовать детали :)
Suresh Venkat
Мы не оставляем комментарии к записям FAQ, если у вас есть предложение, вы можете начать мета-обсуждение или опубликовать здесь .
Каве

Ответы:

24

Вот что я знаю о проблеме обхвата в неориентированных невзвешенных графах. Прежде всего, если обхват четный, вы можете определить его за времени - это старый результат Итай и Родех (А. Итай и М. Родех. Нахождение минимальной цепи в графе. SIAM J. Computing, 7 (4): 413-423, 1978.). Идея такова: для каждой вершины графа запускайте BFS, пока не закроется первый цикл (затем остановитесь и перейдите к следующей вершине); вернуть самый короткий найденный цикл. Если обхват даже самый короткий найденный цикл будет самым коротким циклом. В частности, если ваш график является двудольным, он всегда вычисляет обхват. Однако, если обхват нечетный, вы найдете цикл длины или , так что вы можете быть на .г г г + 1 1O(n2)ggg+11

Теперь настоящая проблема с нечетным обхватом состоит в том, что ваш алгоритм неизбежно должен был бы определить, есть ли на графике треугольник. Лучшие алгоритмы для этого используют умножение матриц: min { время для графов на узлах и ребрах. Итай и Родех также показали, что любой алгоритм, который может найти треугольник в плотных графах, также может вычислять обхват, поэтому у нас есть алгоритм временного обхвата. Однако время выполнения для обхвата в разреженных графиках не так хорошо, как для поиска треугольников. Лучшее, что мы знаем в целом, это . В частности, то, что кажется самым сложным, - это найти алгоритм времени для графов сn 2,38 , м 1,41 ) n m O ( n 2,38 ) O ( m n ) o ( n 2 ) m = O ( n ) .O(n2.38,m1.41)nmO(n2.38)O(mn)o(n2)m=O(n)

2n1+1/k2k, Таким образом, чем плотнее график, тем легче найти хорошее приближение к обхвату. Когда график очень разреженный, обхват может быть существенно большим.

Virgi
источник
5
классно ! Я надеялся, что эксперт появится :)
Суреш Венкат
O(m1.41)
2
O(m1.41)
Существует простой и общий алгоритм O (nm) на основе BFS, который, как я удивлен, никто не упомянул: webcourse.cs.technion.ac.il/234247/Winter2003-2004/ho/WCFiles/…
Labo
5

Нахождение обхвата плоского графа имеет интересную историю. См. Эту статью Чанга и Лу для алгоритма линейного времени и истории улучшений.

Не существует общего метода, чтобы найти обхват любого разреженного графа. Часто нам приходится искать соответствующие специальные разложения или вложения, чтобы получить лучшие оценки. Если граф «доказуемо» разрежен, с ним часто ассоциируется хорошая структура. Например, ограниченные графы длины дерева разрежены, и у них есть связанные разложения дерева.

o(n2)

Шива Кинтали
источник
Планарная бумага кажется интересной, спасибо.
Саид