Определить, содержит ли граф треугольник?

Эта проблема имеет простое решение, если наша целевая временная сложность O (| V | * | E |) или O (V ^ 3) и тому подобное. Однако мой профессор недавно дал нам задание с выражением проблемы:

Пусть G = (V, E) - связный неориентированный граф. Напишите алгоритм, определяющий, содержит ли G треугольник в O (| V | + | E |).

В этот момент я в тупике. Wikipedia говорит:

Можно проверить, нет ли графика с m ребрами без треугольника во времени O (m ^ 1.41).

Не было упоминания о возможности более быстрого алгоритма, кроме того, который работает на компьютере Quantum. После этого я начал прибегать к лучшим источникам. Вопрос о Math.SE связал меня с этой статьей, в которой говорится:

Самый быстрый алгоритм, известный для нахождения и подсчета треугольников, основан на быстром матричном произведении и имеет сложность времени O (n ^ ω), где ω < 2.376 - показатель быстрой матрицы.

И что там, где я начал понимать, что, может быть, нас обманывают в работе над нерешенной проблемой! Этот подлый профессор!

Однако, я все еще немного скептически настроен. В документе говорится "поиск и подсчет". Является ли это эквивалентом проблемы, которую я пытаюсь решить?

TL; DR: Меня обманывают, или я пропускаю что-то настолько тривиальное?

Ответ 1

Ну, оказывается, это действительно не выполнимо в O (| V | + | E |). Или, по крайней мере, мы не знаем. Я прочитал 4 статьи, чтобы достичь этого результата. Я остановился на полпути к одному из них, потому что понял, что он больше ориентирован на распределенные вычисления, чем на теорию графов. Один из них даже дал вероятностные алгоритмы для определения треугольной степени в "почти линейном" времени. Три соответствующие статьи:

Поиск и подсчет заданных циклов длины от Alon, Yuster и Zwick.
Тестирование треугольника-разреженности в общих графиках Алон, Кауфман, Кривелевич и Рон.
Вычисления треугольников главной памяти для очень больших (разреженных (Power-Law)) графиков от Latapy

Я написал около 2 страниц LaTeX для задания, цитируя статьи с правильными цитатами. Соответствующие заявления в документах помещены в коробку:

В конце концов, я поговорил с моим профессором, и, оказывается, на самом деле это была непреднамеренная ужасная ошибка. Затем он изменил требуемую сложность на O (| V | * | E |). Я не обвиняю его, он заставил меня узнать больше теории графов!

Ответ 2

Здесь код для версии O (| E | * | V |).

Когда вы ограничиваете | V | битовая маска пересекается - любая операция эффективно O (1), которая получает вас O (| E |), но это обман.

Реально сложность O (| E | * (| V |/C)), где C - некоторая константа, специфичная для архитектуры (т.е. 32, 64, 128).

function hasTriangle(v, e) {
  if(v.length > 32) throw Error("|V| too big, we can't pretend bit mask intersection is O(1) if |V| is too big!");
  // setup search Array
  var search = new Uint32Array(v.length);
  // loop through edges O(|E|)
  var lastEdge = [-1, -1];
  for(var i=0, l=e.length; i < l; i++) {
    var edge = e[i];
    if(edge[0] == lastEdge[0]) {
      search[lastEdge[1]] = search[lastEdge[1]] | (1 << edge[0]);
      search[edge[1]] = search[edge[1]] | (1 << edge[0]);
    } else {
      lastEdge = edge;
    }
    // bit mask intersection-any O(1), but unfortunately considered O(|V|)
    if( (search[edge[0]] & search[edge[1]]) > 0 ) {
      return true;
    }
  }
  return false;
}

var V = [0, 1, 2, 3, 4, 5];
var E_no_triangle = [[0, 4], [0, 5], [1, 2], [1, 3], [2, 5]];
var E_triangle = [[0, 1], [0, 2], [0, 3], [1, 4], [2, 1], [2, 3], [4, 5]]; // Triange(0, 2, 3)
console.log(hasTriangle(V, E_no_triangle)); // false
console.log(hasTriangle(V, E_triangle)); // true