Сложность вычисления среднего расстояния графа

Пусть - среднее расстояние связного графа $\rm{ad}(G)$ $G.$

Одним из способов вычисления является суммирование элементов матрицы расстояний и соответствующее масштабирование суммы. $\rm{ad}(G)$ $D(G),$ $G$

Если выходной граф представляет собой дерево, то известно, что среднее расстояние может быть вычислено за линейное время (см. B.Mohar, T.Pisanski - Как вычислить индекс Винера для графа). По-видимому, существуют быстрые алгоритмы для графов с ограниченной шириной дерева.

Поэтому интересен вопрос, помогает ли это узнатьДругими словами $D(G).$

Можно ли вычислить за субквадратичное время? $\rm{ad}(G)$

Мне интересно знать, есть ли теоретическая нижняя граница того, почему это невозможно.

cc.complexity-theory graph-theory graph-algorithms Jernej
источник

Наряду с результатом ограниченной длины деревьев, о котором вы упомянули (Кабелло и Кнауэр, «Алгоритмы для графиков ограниченной длины деревьев с помощью поиска по ортогональному диапазону», Comp. Geom. 2009), известно, как быстро вычислить это значение для графов, изометрически встраиваемых в декартовы произведения деревьев ( что оказывается актуальным для алгоритмов химических графов) - см. Yeh и Gutman, "О сумме всех расстояний в составных графах", Discrete Math. 1994, и Чепой и Клавжар, «Индекс Винера и индекс Сегеда бензеноидных систем в линейное время», JCICS 1997.

Дэвид Эппштейн

Ответы:

Вычисление ad (G) за времени для постоянной даже в графах с ребрами и вершинами будет означать, что гипотеза сильного экспоненциального времени (SETH) ) ложно (SETH был определен Impagliazzo, Paturi и Zane'01 и подразумевает, что CNF-SAT по переменным не имеет временных алгоритмов.) $O(n^{2-\delta})$ $\delta>0$ $\tilde{O}(n)$ $n$ $n$ $O(2^{(1-\varepsilon)n})$

Чтобы доказать это, отметим, что недавно мы доказали в (Алгоритмы быстрого приближения для диаметра и радиуса разреженных графов, Лиам Родитти, В. Васильевска, Вильямс. STOC'13.), Что если можно различать графы диаметра 2 и 3 в субквадратичном время, то SETH ложно. Доказательство проходит через сокращение от CNF-SAT. Такое же сокращение можно использовать, чтобы показать, что вычисление ad (G) в субквадратичном времени показывает, что SETH является ложным, поскольку среднее расстояние на графиках в сокращении будет равно (где и - количество узлов и ребер в экземпляре сокращения), если экземпляр CNF-SAT не удовлетворяется, и более того, если имеется удовлетворяющее назначение. $2-M/{N\choose 2}$ $N$ $M$

Virgi
источник