Ist es notwendig, die Matrixmultiplikation

20

Eine Klaue ist eine . Ein trivialer Algorithmus erkennt eine Klaue in . Dies kann in , wobei der Exponent der schnellen Matrixmultiplikation ist, und zwar wie folgt: Nehmen Sie den durch induzierten Teilgraphen für jeden Scheitelpunkt und finden Sie ein Dreieck in seine Ergänzung. O ( n 4 ) O ( n & ohgr; + 1 ) & ohgr; N [ v ] vK1,3O(n4)O(nω+1)ωN[v]v

Soweit ich weiß, sind diese grundlegenden Algorithmen nur bekannt. Spinrad listete in seinem Buch "Effiziente Graphendarstellungen" das Erkennen einer Klaue in als offenes Problem auf (8.3, Seite 103). Für die untere Schranke wissen wir, dass ein -Zeitalgorithmus einen -Zeitalgorithmus zum Finden eines Dreiecks impliziert. Wir können also als Untergrenze betrachten.O ( n c ) O ( n max ( c , 2 ) ) , Ω ( n ω )o(nω+1)O(nc)O(nmax(c,2))Ω(nω)

Frage:

  1. Gibt es hier irgendwelche Fortschritte? Oder irgendwelche Fortschritte, um zu zeigen, dass es unmöglich ist?
  2. Gibt es andere natürliche Probleme mit -Zeitalgorithmen, die die besten sind?O(nω+1)

Anmerkung:

  1. Ich fordere ausdrücklich die Erkennung einer Klaue anstelle der Erkennung von klauenfreien Graphen. Obwohl ein Algorithmus normalerweise beide Probleme löst, gibt es nur wenige Ausnahmen.
  2. Im Handbuch für Algorithmen und Theoretische Informatik wird behauptet, dass es in linearer Zeit gefunden werden kann, aber es war nur ein Tippfehler (siehe "Effiziente Graphendarstellungen").
Yixin Cao
quelle
Sie können mit Alon et al ist. Verfahren Dreieck in der Suche O(|E|1.41) für jeden Knoten , die an einem Ende O(|V||E|1.41) die ist , Besser als |V|ω+1 wenn der Graph nicht zu dicht ist.
RB
@ RB, vielen Dank für den Hinweis. Die Grundidee ist immer noch, den Algorithmus zur Dreieckserkennung n mal auszuführen , was ich vermeiden möchte.
Yixin Cao
Wie können wir damit rechnen, einen Algorithmus zu finden, der nicht mit dem Finden von Dreiecken zusammenhängt? Denn was auch immer der Algorithmus ist, sollte die Nachbarn jedes Scheitelpunkts überprüfen. Ich meine, dass Eigenschaft eine sehr lokale Eigenschaft ist, außer dass bei konstantem Faktorunterschied jeder Scheitelpunkt gesehen werden sollte. (Oder ich kann mir keinen natürlichen Algorithmus vorstellen, der diese Lokalität vermeidet). Hast du noch eine vage Idee?
Saeed
2
Vielleicht ist es gut zu erwähnen, dass wir, wenn wir in f (n) Zeit eine Klaue finden, auch in f (n + 1) Zeit ein Dreieck finden können (nehmen Sie einfach das Komplement des Graphen und fügen Sie einen weiteren Scheitelpunkt hinzu, der mit jedem verbunden ist ), also sollten wir nicht hoffen, etwas Besseres als . nω
Domotorp
1
@domotorp, scheint, dass der Teil klar ist, umgekehrt ist nicht klar, ich meine, warum wir lineare Suche brauchen. Wie Yixin ebenfalls betonte, gibt es möglicherweise einen anderen Algorithmus, der keinen Dreiecksuchalgorithmus verwendet und das Problem in löst , was meiner Meinung nach schwierig ist, einen solchen Algorithmus zu finden und wahrscheinlich einfacher ist um zu zeigen, dass jeder Algorithmus die Dreiecksuche als Subroutine verwendet (oder konvertiert werden kann), mit linearer Suche darauf. o(nω+1)
Saeed

Antworten:

16

Ich denke, dass wir für dichte Graphen etwas besser als können, wenn wir eine rechteckige Matrixmultiplikation verwenden. Eine ähnliche Idee wurde von Eisenbrand und Grandoni ("Zur Komplexität von Clique mit festen Parametern und dominierender Menge", Theoretical Computer Science Volume 326 (2004) 57–67) für die Erkennung von 4 Cliquen verwendet.O(n1+ω)

Sei der Graph, in dem wir die Existenz einer Klaue erkennen wollen. Lassen die Menge (geordnet) Paare von Eckpunkten in sein . Betrachten Sie die folgende Boolesche Matrix der Größe: Jede Zeile wird durch ein indiziert, jede Spalte wird durch ein indiziert , und der entsprechende Eintrag ist nur dann eins, wenn , und . Betrachten wir die Boolesche Matrixprodukt von und seine transponieren . Der Graph hat genau dann eine Klaue, wenn es eine gibtA V MG=(V,E)AVMu V ( v , w ) A { u , v } E { v , w } E { u , w } E M|V|×|A|uV(v,w)A{u,v}E{v,w}E{u,w}EM G { u , v } E M MMTG{u,v}E so, dass der Eintrag von in der von indizierten Zeile und der von indizierten Spalte eins ist. u vMMTuv

Die Komplexität dieses Algorithmus ist im Wesentlichen die Komplexität der Berechnung des Booleschen Produkts einer Matrix durch eine Matrix, wobei die Anzahl der Eckpunkte im Graphen bezeichnet. Es ist bekannt, dass ein solches Matrixprodukt in der Zeit berechnet werden kann , die für die bekannteste Obergrenze von besser ist als . Wenn natürlich (wie vermutet), ergeben die beiden Ansätze die gleiche Komplexität .n 2 × n n O ( N 3,3 ) O ( n 1 + ω ) ω ω = 2 O ( n 3 )n×n2n2×nnO(n3.3)O(n1+ω)ωω=2O(n3)

Francois Le Gall
quelle
Groß! Dies ist genau das, was ich für meine erste Frage möchte: Nur ein Aufruf der Matrixmultiplikation, obwohl eine größere. Ich warte auf weitere Kommentare oder Antworten zu meiner zweiten Frage, bevor ich sie als Antwort nehme.
Yixin Cao
15

Ich weiß nicht, wie man es vermeidet, Matrixmultiplikationen durchzuführen, aber Sie können es so analysieren, dass die Zeit tatsächlich die einer kleineren Anzahl von ihnen ist. Dieser Trick ist vonn

Kloks, Ton; Kratsch, Dieter; Müller, Haiko (2000), "Effizientes Finden und Zählen kleiner induzierter Teilgraphen", Information Processing Letters 74 (3–4): 115–121, doi: 10.1016 / S0020-0190 (00) 00047-8, MR 1761552.

Die erste Beobachtung ist, dass, wenn Sie Matrix-Multiplikationen durchführen, die Matrizen nicht wirklich , sondern wobei der Grad jedes Scheitelpunkts ist, denn was Sie suchen, ist ein Co-Dreieck in der Nachbarschaft jedes Scheitelpunkts.d × d dn×nd×dd

Zweitens muss in einem klauenfreien Diagramm jeder Scheitelpunkt Nachbarn haben. Denn sonst hätte die Menge der Nachbarn zu wenige Kanten, um ein Dreieck im Komplement zu vermeiden. Wenn Sie also Matrixmultiplikationen durchführen, müssen Sie dies nur für Matrizen der Größe und nicht für tun .O(O(m)nO(m)n

Außerdem kann jede Kante nur für zwei Eckpunkte, ihre Endpunkte, zur Größe des Matrixmultiplikationsproblems beitragen. Der schlimmste Fall tritt auf, wenn die für die Gesamtgröße dieser Matrixmultiplikationsprobleme in Unterprobleme der Größe aufgeteilt werden, was eine Gesamtzeitgrenze von ergibt , eine Verbesserung für spärliche Graphen gegenüber dem von R B genannten .O ( 2mO(O(m)O(m ( 1 + ω ) / 2 )O(nm ω / 2 )O(m)O(m(1+ω)/2)O(nmω/2)

David Eppstein
quelle
Wow, das ist eine clevere Idee, ich habe darüber nachgedacht, ob es möglich ist, eine sublineare Suche durchzuführen (was dies tatsächlich widerlegt) und habe nicht einmal über die eigentlichen Eigenschaften des Problems nachgedacht.
Saeed
Vielen Dank, David. Ich lasse es für einen Moment offen, da meine zweite Frage noch nicht bemerkt zu sein scheint.
Yixin Cao