Was ist der genaueste Algorithmus, um den Kern eines Graphen zu berechnen?

24

Ein Graph H ist ein Kern, wenn jeder Homomorphismus von H zu sich selbst eine Bijektion ist. Ein Teilgraph von G H ist ein Kern von G , wenn H ein Kern und es gibt einen Homomorphismus von G nach H ist http://en.wikipedia.org/wiki/Core_%28graph_theory%29

Was ist der bekannteste exakte Algorithmus, um den Kern eines gegebenen Graphen G zu finden?

ds.algorithms graph-theory graph-algorithms Regelmäßigkeit
quelle
Auf den ersten Blick scheint dieses Problem sehr schwierig zu sein, aber eine Reduzierung des Graph-Isomorphismus oder anderer verwandter Probleme ist (für mich) nicht offensichtlich. Gute Frage.
Derrick Stolee

Antworten:

22

Das Berechnen des Kerns eines Graphen ist schwierig: Selbst die Entscheidung, ob ein gegebener dreifarbiger Graph ein Kern ist, ist co-NP-vollständig, siehe Hell und Nesetril . Es gibt Einstellungen, in denen die Kernberechnung effizient durchgeführt werden kann. Eine Datenbankeinstellung finden Sie unter Effiziente Kernberechnung im Datenaustausch von Georg Gottlob und Alan Nash. Hier ermöglichen einige vernünftige Einschränkungen für die Art der Einschränkungen im Datenbankschema eine effiziente Berechnung der Kerne.

Bearbeiten: Abgesehen von der oben erwähnten Gottlob / Nash-Arbeit sind mir keine weiteren Versuche bekannt, effiziente Algorithmen für die Kernberechnung bereitzustellen. Hinweise auf Algorithmen, die besser sind als Brute Force (exakt oder auf andere Weise), wären willkommen.

András Salamon
quelle
1
Andras, das Papier, auf das Sie verlinken, scheint zu zeigen (das Abstract zu lesen), dass die Überprüfung, ob ein Graph sein eigener Kern ist, NP-vollständig ist. Beantwortet das Papier auch die Frage, die das OP stellt?
Suresh Venkat
8
@ Suresh: Ich denke, dass der Hinweis auf die NP-Vollständigkeit eine der guten Möglichkeiten ist, eine Frage zu beantworten, die nach einem Algorithmus fragt.
Tsuyoshi Ito
1
Recht. Ich habe mich nur gefragt, ob es mehr in der Zeitung gibt (dh können Sie überprüfen, ob der Kern klein ist oder ob der Kern trivial ist, usw. usw.)
Suresh Venkat
9

Das Problem der Bestimmung, ob ein gegebener Graph ein Kerngraph ist, ist leicht in co-NP zu sehen. Tatsächlich ist es co-NP vollständig.

Das Problem der Bestimmung, ob ein gegebener Teilgraph H ein Kern eines gegebenen Graphen G ist, liegt in der größeren Klasse DP ( https://complexityzoo.uwaterloo.ca/Complexity_Zoo:D#dp ) und ist tatsächlich für diese Klasse vollständig ( Das archetypische Gesamtproblem für diese Klasse besteht aus Paaren von Booleschen Formeln (wobei die erste erfüllbar und die zweite nicht erfüllbar ist). Der Einschluss in DP ist klar: Testen Sie, ob G homomorph zu H abgebildet ist (dies wird als Erfüllbarkeit kodiert) und gleichzeitig, dass H keinen Homomorphismus zu sich selbst hat, der nicht darauf liegt (dies wird als Unerfüllbarkeit kodiert). DP-Härte ist nicht trivial und wird in der Arbeit bewiesen:

Fagin, Ronald, Phokion G. Kolaitis und Lucian Popa. "Datenaustausch: Auf den Kern kommen." ACM-Transaktionen auf Datenbanksystemen (TODS) 30.1 (2005): 174-210.

Szymon Toruńczyk
quelle
Das Papier ist bei dx.doi.org/10.1145/1061318.1061323
András Salamon