Сложность подсчета графовых эндоморфизмов

9

Гомоморфизм из графаG=(V,E) на график G=(V,E) это отображение f от V в V такой, что если x а также y смежны в E тогда f(x) а также f(y) смежны в E, Эндоморфизм графаG является гомоморфизмом из Gк себе; это без фиксированной точки, если нетx такой, что f(x)=xи это нетривиально, если это не идентичность.

Недавно я задал вопрос, связанный с автоморфизмами (и графами) множеств , то есть биективными эндоморфизмами, обратные к которым также являются эндоморфизмами. Я нашел соответствующую работу по подсчету (и определению существования) автоморфизмов, но в процессе поиска я не смог найти никаких результатов, связанных с эндоморфизмами.

Отсюда мой вопрос: в чем сложность, учитывая графикGпринятия решения о существовании нетривиального эндоморфизма Gили подсчета количества эндоморфизмов? Тот же вопрос с эндоморфизмами без неподвижных точек.

Я думаю, что аргумент, приведенный в этом ответе, распространяется на эндоморфизмы и оправдывает то, что случай ориентированных двудольных графов или по- зетов не проще, чем проблема для общих графов (проблема для общих графов сводится к этому случаю), но его сложность не кажется простым для определения. Известно, что решение о существовании гомоморфизма от одного графа к другому является NP-трудным (это ясно, поскольку оно обобщает раскраску графа), но кажется, что ограничение поиска гомоморфизмами от графа к себе может облегчить проблему, так что это не помогает мне определить сложность этих проблем.

a3nm
источник

Ответы:

6

Подсчет эндоморфизмов или эндоморфизмов без неподвижных точек завершен для FP#P: дан связный граф Gрассмотрим график G который является непересекающимся союзом Gи треугольник. затем|End(G)|=(|End(G)|+#3COL(G))(#{triangles in G}+33), так #3COLможет быть вычислено с использованием двух счетчиков эндоморфизмов (и по общему результату даже одного достаточно) и некоторой последующей обработки за многократное время. Обратите внимание, что количество треугольников можно посчитать за кубическое (или даже умножение матрицы) времени. То же самое уравнение справедливо для свободных эндоморфизмов с фиксированной точкой, поскольку 3-раскраски и треугольники являются эндоморфизмами без фиксированных точекG,

Если вы хотели бы GЧтобы быть на связи, вы можете сделать следующее. Прежде всего обратите внимание, что подсчет вершинного цвета графа эндоморфизмов (где вершины цветаc может быть сопоставлен только с другими вершинами цвета c) эквивалентен подсчету графовых эндоморфизмов следующим образом. Пусть цвета будут{1,...,C}, Для каждой вершиныv цвета c, добавить в новый непересекающийся нечетный циклCv размером как минимум n+2c (n=|V(G)|) и соединить одну вершину Cv в v, Каждый эндоморфизмG соответствует 2nэндоморфизмы нового графа (для каждого цикла у вас есть два варианта его отображения). Обратите внимание, что нет вершинG можно сопоставить с вершинами любого Cv, так как циклы слишком велики (вы должны быть в состоянии поместить один цикл в другой, что невозможно для нечетных циклов).

Теперь, чтобы сделать версию Gэто связано, мы начинаем с цветной версии, а затем применяем вышеупомянутое преобразование. Начните как прежде, добавив кG непересекающийся треугольник Δ, Теперь добавьте одну новую вершинуv0 который связан с каждой вершиной в GΔ, цветv0 красный и все остальные вершины синие.

Джошуа Грохов
источник
Спасибо! Я не уверен в вашей точной формуле|End(G)| (Я получил (|End(G)|+#3COL(G))(#triangles+33)и что-то подобное для фиксированной точки без), но аргумент все еще остается в силе. Вторая часть вашего аргумента показывает твердость, даже если предположить связность, я думаю, что это правда, но я думаю, что это не относится непосредственно к эндоморфизмам без неподвижных точек (в отображениях циклов есть фиксированные точки), но это не так важно. Мне было бы более любопытно узнать: является ли проблема решения NP трудной (для нетривиальных и для эндоморфизмов без неподвижных точек)? Еще раз спасибо!
a3nm
Вы правы насчет формулы - я обновил ее. Чтобы вторая часть применялась к неподвижной точке, поместите ребро от каждой из двух максимально удаленных вершинCv в v, Счет для фиксированной точки будет немного другим, но я думаю, что он все еще работает. (Вам также может понадобиться увеличить размер циклов ...). Для пар жестких графов (нетривиальных эндосов)G,H, решив существование эндос GH (дизъюнктное объединение) эквивалентно решению о существовании гомоморфизма GH или HG, Почти все графики жесткие, поэтому вполне возможно, что решение сложное для NP ...
Джошуа Грохов
ОК, я думаю, что я куплю ваш аргумент за счет без фиксированных точек. Для принятия решения теперь я замечаю, что «Ядро графа», Ад, с. 8-9, кажется, доказывает, что решение о существовании нетривиального эндоморфизма является NP-полным. (Вопрос об эндоморфизмах без неподвижных точек остается, но нет оснований полагать, что это тоже не сложно.)
a3nm