Является ли «перестановка p автоморфизмом графа в моем множестве?» NP-полной?

Предположим, у нас есть множество S графов (конечных графов, но их бесконечное число) и группа перестановок P, которая действует на S.

Экземпляр: перестановка p в P.

Вопрос: существует ли граф g в S, который допускает автоморфизм p?

Является ли эта задача NP-полной для некоторых множеств S?

Было бы легко проверить, что граф допускает перестановку p (то есть сертификат). Более того, легко найти примеры S, где проблема не является NP-полной, например, S является множеством полных графов, откуда ответ всегда да.

Примечание: меня не очень интересует тип графиков; если хотите, они могут быть непростыми, направленными, цветными и т. д.

ДОБАВЛЕНИЕ: Проблема, которую я сейчас рассматриваю, заключается в классификации того, какие изотопизмы являются автотопизмами латинских квадратов (что также можно интерпретировать как специальный тип автоморфизма графов).

Учитывая латинский квадрат L (i, j), мы можем построить граф следующим образом:

Набор вершин представляет собой набор ячеек (i, j) в матрице и
Существует грань между различными (i, j) и (i ', j') всякий раз, когда i = i 'или j = j' или L (i, j) = L (i ', j').

Такой график называется графиком латинского квадрата (см., Например, эту статью Бэйли и Кэмерон http://designtheory.org/library/encyc/topics/lsee.pdf ). Мы можем интерпретировать автотопизм латинского квадрата как автоморфизм графа латинского квадрата. Итак, пусть S будет множеством графов латинских квадратов, образованных из латинских квадратов порядка n. Итак, вопрос, который меня интересует, таков:

При заданной перестановке p является ли автоморфизм одного (или нескольких) графов в S?

Мне кажется, что на этот вопрос в целом сложно ответить - в настоящее время я пишу статью на 30 с лишним страниц по этому вопросу (с двумя соавторами). На самом деле, в большинстве случаев это легко (в большинстве случаев это «нет»), но есть некоторые сложные случаи.

Поэтому я заинтересован в поиске решения проблем, которые будут связаны с «классификацией симметрии». Они не должны быть связаны с латинскими квадратами, я просто надеюсь использовать эти методы, чтобы ответить на вопрос о латинских квадратах.

cc.complexity-theory graph-theory np-hardness automorphism Дуглас С. Стоунс
источник

Я не уверен, правильно ли я понимаю проблему. Можете ли вы привести пример S и P (и групповое действие P на S)? Пример, который делает проблему нетривиальной (ни все-да, ни все-нет), поможет понять проблему.

Цуёси Ито

В примере полных графов я не понимаю, как перестановка в k точках действует на полный граф в n точках, где k ≠ n (особенно, если k> n).

Цуёси Ито

Мне удалось обмануть себя и подумать, что я понял проблему, но теперь я решил, что не понимаю. Действует ли группа перестановок S на графах в семействе P или только потенциально действует на графы в семействе P?

Ниль де Бодрап,

Одна из проблем здесь заключается в том, что нам нужно выбрать набор

для которого тестирование членства проводится в NP.

S

$S$

Эмиль

Я добавил немного больше фона в ответ. На самом деле, в общем, меня не волнует, действует ли группа на S, пока мы можем ответить: «Является ли эта перестановка автоморфизмом этого графа?» В случае латинских квадратов мы можем интерпретировать это как групповое действие.

Дуглас С. Стоунс

Ответы:

Возьмем любой язык (который состоит из двоичных строк). Построим множество графов следующим образом: $L$ $S$

Для каждой строки с , мы имеем граф в , с множеством узлов и следующие ребра: если бит из является , то узлы и $x \in L$ $|x| = n$ $G_x = (V_x,E_x)$ $S$ $V_x = \{1,2,...,3n\}$ $i$ $x$ $0$ $3i-2$ являются смежными, в противном случае и являются смежными. Других краев нет. $3i-1$ $3i-2$ $3i$

Пусть теперь будет перестановка . Предположим , что есть автоморфизм некоторого графа в . То есть, есть автоморфизм для некоторого . Пусть . Давайте рассмотрим следующие два случая: $p$ $\{1,2,...,3n\}$ $p$ $S$ $p$ $G_y$ $y \in L$ $i \in \{1,2,...,n\}$

, , . Тогда у нас должен быть бит of равный . $p(3i-2) = 3i-1$ $p(3i-1) = 3i-2$ $p(3i) = 3i$ $i$ $y$ $0$
, , . Тогда у нас должен быть бит of равный . $p(3i-2) = 3i$ $p(3i-1) = 3i-1$ $p(3i) = 3i-2$ $i$ $y$ $1$

Следовательно, если мы можем решить вопрос «является ли данный автоморфизмом некоторого », мы также можем решить вопрос «является ли заданная строка в ». Более того, если мы можем сделать первое, скажем, за полиномиальное время в , мы можем сделать последнее за полиномиальное время в также. $p$ $G \in S$ $y$ $L$ $|p|$ $|y|$

Теперь вы можете просто позволить быть вашей любимой NP-трудной проблемой. Или проблема остановки ... $L$

Юкка Суомела
источник

И чтобы фактически ответить на первоначальный вопрос: пусть

- NP-полная задача, и у вас будет

такая что задача автоморфизма NP-полная. Сертификат на ответ «да» является

такой , что

является автоморфизм

, плюс сертификат

L

$L$

S

$S$

G_{y} \in S

$G_y \in S$

p

$p$

G_{y}

$G_y$

y \in L

$y \in L$

Юкка Суомела

@Jukka: Один из способов приблизить вопрос к исходной мотивации графов латинских квадратов - это потребовать, чтобы множество графов

было замкнуто относительно изоморфизма. Это тоже вполне естественное ограничение. Множество

вы строите из произвольного языка

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

S

$S$

S

$S$

L

$L$

Джошуа Грохов

@ Джошуа: Я думаю, что можно изменить конструкцию, например, следующим образом: и графики, и перестановки, которые мы используем в запросах, состоят из непересекающихся циклов . Более подробно,

содержит цикл длиной

если бит

из

равен

. Аналогично, чтобы определить, является ли

, построить перестановку

которая содержит цикл длиной

если бит

из

равен

G_{x}

$G_x$

2 i + a + 1

$2i+a+1$

i

$i$

x

$x$

a

$a$

y \in L

$y \in L$

p

$p$

2 i + a + 1

$2i+a+1$

i

$i$

y

$y$

. (Возможно, я упустил некоторые детали, но я думаю, что основная идея должна работать ...)

a

$a$

Юкка Суомела

@Jukka: Отлично. Я считаю, что новая конструкция работает как написано (при условии, что мы разрешаем

действовать только на графы с ровно

вершинами, а не на графы с более чем

вершинами).

p \in S_{n}

$p \in S_n$

n

$n$

n

$n$

Джошуа Грохов

@ Джошуа: Я думаю, что возможность применения

к графам с более чем

узлами не имеет значения, если мы предположим, что язык

использует код без префиксов?

p \in S_{n}

$p \in S_n$

n

$n$

L

$L$

Юкка Суомела