Граф H является ядром, если любой гомоморфизм из H в себя является биекцией. Подграф H группы G является ядром группы G, если H является ядром и существует гомоморфизм от G к H. http://en.wikipedia.org/wiki/Core_%28graph_theory%29
Учитывая граф G, какой самый известный точный алгоритм, чтобы найти его ядро?
ds.algorithms
graph-theory
graph-algorithms
регулярность
источник
источник
Ответы:
Вычислить ядро графа сложно: даже решение о том, является ли данный трехцветный граф ядром, является со-NP-полным, см. Ад и Несетрил . Существуют настройки, в которых вычисления ядра могут выполняться эффективно, см. « Эффективные вычисления ядра в обмене данными » Джорджа Готтлоба и Алана Нэша для настройки базы данных; здесь некоторые разумные ограничения на виды ограничений в схеме базы данных позволяют эффективно вычислять ядра.
Редактировать: Кроме упомянутой выше работы Готтлоба / Нэша, я не знаю о каких-либо других попытках предоставить эффективные алгоритмы для вычисления ядра. Приветствуются указатели на любые алгоритмы лучше, чем грубая сила (точная или нет).
источник
Проблема определения того, является ли данный граф графом ядра, легко увидеть в co-NP. На самом деле, это со-НП завершена.
Проблема определения того, является ли данный подграф H ядром данного графа G, относится к большему классу DP ( https://complexityzoo.uwaterloo.ca/Complexity_Zoo:D#dp ) и фактически завершена для этого класса ( архетипическая полная задача для этого класса состоит из пар булевых формул, где первая выполнима, а вторая не выполнима). Содержимое в DP ясно: проверьте, что G отображается гомоморфно в H (это кодируется как выполнимость) и одновременно, что H не имеет гомоморфизма к себе, который не относится к (это кодируется как неудовлетворенность). DP-твердость нетривиальна и доказана в статье:
Фагин, Рональд, Фокион Г. Колайтис и Люсьен Попа. «Обмен данными: добраться до сути». Транзакции ACM в системах баз данных (TODS) 30,1 (2005): 174-210.
источник