Die Komplexität der Feststellung, ob ein fester Graph einem anderen untergeordnet ist

25

Das Ergebnis von Robertson und Seymour demonstriert einen -Algorithmus zum Testen, ob ein fester Graph G ein kleinerer Teil von H ist . Ich habe zweieinhalb Fragen zu diesem Thema:O(n3)GH

1) Es scheint, dass seitdem Verbesserungen an diesem Algorithmus vorgenommen wurden. Was ist derzeit der bekannteste Algorithmus?

2a) Was vermuten die Menschen, um die optimale Grenze zu sein?

Mohars Algorithmus zum Einbetten auf einer festen Oberfläche und Kawarabayashis Algorithmus zum Erkennen von apex-Graphenk entscheiden über die Zugehörigkeit zu Graphen, die von verbotenen Minderjährigen in linearer Zeit charakterisiert werden, und motivieren die letzte Frage:

2b) Gibt es einen Grund zu der Annahme, dass wir dies in linearer Zeit tun können?

Wenn sich jemand bereits einen linearen Zeitalgorithmus ausgedacht hat, sind die letzten beiden Fragen natürlich albern. :)

Timothy Sun.
quelle
Ich bin sehr neugierig, mehr darüber zu hören.
Suresh Venkat
10
Ich habe gehört, dass Bruce Reed und Ken-ichi Kawarabayashi einen -Zeitalgorithmus haben , aber er wurde nicht geschrieben. Diese Behauptung erscheint hier zum Beispiel. O(nlogn)
Robin Kothari
2
Also hat keiner von beiden beschlossen, es nach mehr als drei Jahren aufzuschreiben?
Timothy Sun

Antworten:

13

Es gibt einen Vorabdruck von Ken-ichi Kawarabayashi, Yusuke Kobayashi und Bruce Reed, der einen quadratischen Zeitalgorithmus behauptet: " Das Problem der disjunkten Pfade in quadratischer Zeit ". Es ist eher als Konferenzbeitrag als als Journalarbeit formatiert, daher bin ich mir nicht sicher, ob es möglich ist, die Details zu überprüfen (ich habe es selbst nicht wirklich versucht).

Eine kürzlich von Kawarabayashi durchgeführte Umfrage nennt dies als das bekannteste Ergebnis für das eng verwandte Problem der disjunkten Pfade: Ken-ichi Kawarabayashi (2011), "Das Problem der disjunkten Pfade: Algorithmus und Struktur", WALCOM: Algorithms and Computation, LNCS 6552, pp 2–7, doi: 10.1007 / 978-3-642-19094-0_2 .

O(nlogn)

David Eppstein
quelle
O(nlogn)
6

Hh G2O(h)n+O(n2logn)nh

Bart Jansen
quelle