Was sind die Hauptschwierigkeiten beim Übergang von Grafiken zu Hypergraphen?

10

Es gibt viele Beispiele in der Kombinatorik und Informatik, in denen wir ein graphentheoretisches Problem analysieren können, aber für das Hypergraph-Analogon des Problems fehlen unsere Werkzeuge. Warum werden Probleme Ihrer Meinung nach bei 3-einheitlichen Hypergraphen oft viel schwieriger als bei 2-einheitlichen Graphen? Was sind die Grundschwierigkeiten?

Ein Problem ist, dass wir die spektrale Hypergraphentheorie noch nicht zufriedenstellend verstehen. Bitte zögern Sie nicht, mehr Licht in dieses Thema zu bringen. Ich suche aber auch nach anderen Gründen, die Hypergraphen zu schwierigeren Objekten machen.

Arnab
quelle
Ich frage mich, inwieweit dies mit der jüngsten Diskussion über die Änderung der Komplexität geometrischer Probleme von 2D zu 3D zusammenhängt ( cstheory.stackexchange.com/questions/5251/… ). Der Grund, warum ich dies sage, ist, dass Sie Kanten in einem 2-einheitlichen Diagramm mit Positionen auf einem 2D-Gitter verknüpfen können, während ein 3-einheitlicher Hypergraph dann Hyperkanten aufweisen würde, die Positionen in einem 3D-Gitter entsprechen.
Joe Fitzsimons
@ Joe Fitzsimons: guter Punkt. Konzepte und Techniken, die in der (Hyper-) Diagrammeinstellung natürlich sind, wie Untergraphen, Färbungen, Partitionierungen usw., sind in der geometrischen Einstellung möglicherweise nicht so natürlich. Ich stimme Ihnen auch darin zu, dass es in vielen Bereichen einen "Zwei-zu-Drei" -Übergang gibt.
Arnab
2
Ihre Frage ist schwierig, da eine zufriedenstellende Antwort das P vs NP-Problem lösen würde. Beachten Sie, dass eine perfekte Übereinstimmung für 2-einheitliche Diagramme einfach ist, während es für 3-einheitliche Hypergraphen schwierig ist.
Mohammad Al-Turkistany
Ist Hypergraph ein klar definiertes Konzept? (Zum einen weiß diese Rechtschreibprüfung nichts darüber :-) Handelt es sich um eine Beziehung fester oder variabler Arität?
Tegiri Nenashi
Ok, nach dem Besuch von Wikipedia sehe ich, dass es sich eigentlich nicht um eine Beziehung handelt, sondern um eine Familie von Mengen. Nimmt die Mainstream-Mathematik dieses "Hypergraph" -Konzept ernst?
Tegiri Nenashi

Antworten:

8

In dieser Frage verstehe ich, dass "Schwierigkeit" sich nicht auf "schwer zu berechnen" bezieht, sondern auf "schwer zu studieren".

Grafikprobleme sind (zumindest für mich) einfacher zu untersuchen, da einige Konzepte gleichwertig sind. Mit anderen Worten, wenn Sie Fragen für Diagramme auf Fragen für Hypergraphen verallgemeinern möchten, müssen Sie auf die "richtige" Verallgemeinerung achten, damit die gewünschte Konsequenz erzielt werden kann.

Stellen Sie sich zum Beispiel einen Baum vor. Bei Diagrammen ist ein Diagramm ein Baum, wenn er verbunden ist und keinen Zyklus enthält. Dies ist gleichbedeutend damit, verbunden zu sein und n-1 Kanten zu haben (wobei n die Anzahl der Eckpunkte ist) und auch gleichbedeutend damit, keinen Zyklus zu enthalten und n-1 Kanten zu haben. Für 3-einheitliche Hypergraphen ist ein 3-einheitlicher Hypergraph jedoch ein Baum, wenn er verbunden ist und keinen Zyklus enthält. Dies ist jedoch nicht gleichbedeutend damit, verbunden zu sein und n-1-Hyperedges zu haben, noch einen Zyklus zu enthalten und n-1-Hyperedges zu haben.

Ich habe gehört, dass eine Hauptschwierigkeit, um das Regelmäßigkeits-Lemma für einheitliche Hypergraphen zu beweisen, darin bestand, die richtigen Definitionen für Regelmäßigkeit und verwandte Konzepte zu finden.

Wenn Sie die "spektrale Hypergraphentheorie" betrachten möchten, können Sie versuchen, Tensoren oder Homologie zu untersuchen, wenn Sie einen k-einheitlichen Hypergraphen als einen (k-1) -dimensionalen einfachen Komplex sehen, aus dem natürlich die lineare Algebra hervorgeht. Ich weiß nicht, welche "richtige" Verallgemeinerung für Ihren Zweck ist, oder es ist möglich, dass keine der beiden richtig ist.

Yoshio Okamoto
quelle
7

Ich denke, dies ist zu einem großen Teil auf Lawlers "mystische Kraft der Zweiheit" zurückzuführen (die Beobachtung, dass viele parametrisierte Probleme in P für param = 2 und NP-vollständig für param≥3 sind). Ein Graph ist eine Sache, die 2-Tupel von Eckpunkten verbindet, und ein Hypergraph ist eine Sache, die k-Tupel von Eckpunkten für k ≥ 3 verbindet.

So ist z. B. 2-SAT in P und im Wesentlichen ein Graphproblem, während 3-SAT ein Problem bei 3-einheitlichen Hypergraphen ist und NP-vollständig ist.

David Eppstein
quelle
1
Genauer gesagt wollte ich fragen, ob man einige grundlegende Gründe dafür identifizieren kann, warum graphentheoretische Techniken zusammenbrechen. Zum Beispiel haben wir nicht wirklich linear-algebraische Methoden für Hypergraphen, weil der Tensorrang nicht gut verstanden ist (z. B. ist es NP-schwer zu berechnen).
Arnab
1
Die Absicht meiner Antwort war nicht so sehr "diese Probleme sind für Computer schwer zu lösen", sondern vielmehr, dass es eine starke Korrelation zwischen P / NPC und dem Vorhandensein / Nichtvorhandensein guter mathematischer Charakterisierungen gibt. Daher wird es schwieriger, die Probleme zusammen mit dem Werden zum NPC zu studieren.
David Eppstein
7
In diesem Zusammenhang ist die kürzlich veröffentlichte Frage cstheory.stackexchange.com/questions/14950/… sehr interessant: Das Erkennen von Liniendiagrammen von 2-Hypergraphen, dh Liniendiagrammen von (Mehrfach-) Graphen, ist in P, während das Erkennen von Liniendiagrammen von 3-Hypergraphen scheinen ein offenes Problem zu sein. Beachten Sie auch, dass das Charakterisierungsproblem für 3-Hypergraphen (durch verbotene induzierte Untergraphen) noch offen ist, während Liniendiagramme von (Mehrfach-) Graphen mehrere solcher Charakterisierungen zulassen.
vb le
5

Ein weiterer Grund wäre, dass wir viel mehr Wissen über binäre Beziehungen haben als alle anderen n-arischen Beziehungen für n größer als 2.

Natürlich betrachten wir binäre Beziehungen zwischen Objekten wie Adjazenz, nicht leere Schnittmenge, Äquivalenz usw. So können wir Diagramme als binäre Beziehungen definieren und sogar Diagramme basierend auf einer binären Beziehung in einem anderen Diagramm definieren. (Zum Beispiel Liniendiagramme, Cliquenbäume, Baumzerlegungen ...)

Aber was andere Beziehungen betrifft, so haben wir nicht viel Verständnis. Zum Beispiel dauert es einige Zeit, um eine interessante ternäre Beziehung zu finden. (Okay, teilweise aufgrund meiner Unwissenheit) Eigenschaften sind schwächer und Werkzeuge sind viel weniger bei der Untersuchung ternärer Beziehungen. (Wie definieren wir symmetrische oder transitive ternäre Beziehungen? Beide gehören zu den wichtigsten Beziehungen, die man studieren kann.)

Trotzdem weiß ich nicht, warum dies zwischen binären und ternären Beziehungen geschieht. Vielleicht, wie die Türkei sagte, ist diese Frage schwierig und kann mit dem Verständnis des P / NP-Problems zusammenhängen.

Hsien-Chih Chang 張顯 之
quelle
[Ungeachtet zylindrischer und polyadischer Algebren] gibt es keine zwingende Algebra für n-fache Beziehungen. Die Debatte kann sogar auf das Niveau gesenkt werden, wenn man die Position gegenüber der benannten Perspektive auf Beziehungsattribute argumentiert.
Tegiri Nenashi
2

Ich wollte zuerst die falsche Frage beantworten: "Welches Beispiel für Probleme ist in Hypergraphen viel schwieriger als in Grafiken?" Ich war besonders beeindruckt von dem Unterschied im Umgang mit dem maximalen Übereinstimmungsproblem in Diagrammen und dem gleichen bei Hypergraphen (einer Reihe paarweise disjunkter Kanten), die sehr leicht Farben, maximale unabhängige Mengen, maximale Cliquen modellieren können ...

Dann bemerkte ich, dass es nicht Ihre Frage war: "Was sind die Grundschwierigkeiten zwischen den beiden?".

Nun, auf diese würde ich antworten, dass ich bis jetzt nicht viele gemeinsame Punkte zwischen Graphen und Hypergraphen gesehen habe. Außer dem Namen selbst. Und die Tatsache, dass viele Leute versuchen, die Ergebnisse von der ersten auf die andere zu "erweitern".

Ich hatte die Gelegenheit, die Seiten von Berge's "Hypergraphs" und Bollobas '"Set Systems" umzublättern: Sie enthalten viele leckere Ergebnisse, und diejenigen, die ich am interessantesten fand, hatten nur wenige zu Grafiken zu sagen. Zum Beispiel Baranyais Theorem (es gibt einen schönen Beweis in Juknas Buch).

Ich kenne nicht viel von ihnen, aber ich denke gerade über ein Hypergraph-Problem nach und alles, was ich dazu sagen kann, ist, dass ich keine Grafik fühle, die irgendwo herum lauert. Vielleicht halten wir sie für "schwierig", weil wir nur versuchen, sie mit den falschen Werkzeugen zu studieren. Ich erwarte nicht, dass die Grafikprobleme, an denen ich arbeite, mithilfe der Zahlentheorie sofort verschwinden (obwohl dies manchmal vorkommt).

Oh, und noch etwas. Sie sind vielleicht schwieriger zu studieren, weil sie kombinatorisch viel ... mehr ?!

"Probieren Sie sie alle aus und sehen Sie, wann es funktioniert" ist manchmal eine gute Idee für Diagramme, aber bei Hypergraphen wird es schnell durch die Zahlen gedemütigt. :-)

Nathann Cohen
quelle