Komplexität bei der Berechnung der durchschnittlichen Entfernung eines Graphen

Lassen $\rm{ad}(G)$ der durchschnittliche Abstand eines zusammenhängenden Graph $G.$

Eine Möglichkeit, zu berechnen, besteht darin $\rm{ad}(G)$ , die Elemente von $D(G),$ die Abstandsmatrix von $G$ summieren und die Summe entsprechend zu skalieren.

Wenn das Ausgabediagramm ein Baum ist, ist bekannt, dass die durchschnittliche Entfernung in linearer Zeit berechnet werden kann (siehe B. Mohar, T. Pisanski - Berechnen des Wiener-Index eines Diagramms). Es scheint auch schnelle Algorithmen für Diagramme mit begrenzter Baumbreite zu geben.

Eine interessante Frage ist daher, ob es hilfreich ist, zu kennen $D(G).$ Mit anderen Worten

Ist es möglich, $\rm{ad}(G)$ in subquadratischer Zeit zu berechnen ?

Was mich interessiert, ist, ob es eine theoretische Untergrenze gibt, warum dies nicht möglich wäre.

cc.complexity-theory graph-theory graph-algorithms Jernej
quelle

Zusammen mit dem von Ihnen erwähnten Ergebnis der begrenzten Baumbreite (Cabello und Knauer, "Algorithmen für Diagramme der begrenzten Baumbreite über die Suche nach orthogonalen Bereichen", Comp. Geom. 2009) ist bekannt, wie dies schnell für Diagramme berechnet werden kann, die isometrisch in kartesische Baumprodukte eingebettet sind ( was sich als relevant für chemische Graph-Algorithmen herausstellt) - siehe Yeh und Gutman, "Zur Summe aller Abstände in zusammengesetzten Graphen", Discrete Math. 1994 und Chepoi und Klavžar, "Der Wiener-Index und der Szeged-Index von Benzoloid-Systemen in linearer Zeit", JCICS 1997.

David Eppstein

Antworten:

$O(n^{2-\delta})$ $\delta>0$ $\tilde{O}(n)$ $n$ $n$ $O(2^{(1-\varepsilon)n})$

Um dies zu beweisen, haben wir kürzlich in (Schnelle Approximationsalgorithmen für den Durchmesser und den Radius spärlicher Graphen, Liam Roditty, V. Vassilevska Williams. STOC'13.) Bewiesen, dass man in subquadratischen Graphen zwischen Durchmesser 2 und 3 unterscheiden kann Zeit, dann ist SETH falsch. Der Beweis erfolgt über eine Reduktion von CNF-SAT. Die gleiche Reduktion kann verwendet werden, um zu zeigen, dass die Berechnung von Anzeige (G) in subquadratischer Zeit zeigt, dass SETH falsch ist, da der durchschnittliche Abstand in den Graphen in der Reduktion (wobei und sind die Anzahl der Knoten und Kanten in der Reduktionsinstanz), wenn die CNF-SAT-Instanz nicht erfüllbar ist, und mehr als die, wenn eine zufriedenstellende Zuordnung vorliegt. $2-M/{N\choose 2}$ $N$ $M$

Jungfrau
quelle