Существует ли тип щелевого усиления для задачи об изоморфизме графа?

53

Предположим, что и G 2 являются двумя неориентированными графами на множестве вершин { 1 , , n } . Графы изоморфны тогда и только тогда, когда существует перестановка Π такая, что G 1 = Π ( G 2 ) , или более формально, если существует перестановка Π такая, что ( i , j ) является ребром в G 1 тогда и только тогда если ( Π ( i ) , Π ( jG1G2{1,,n}ΠG1=Π(G2)Π(i,j)G1 это ребро в G 2 . Проблема изоморфизма графов - это проблема определения изоморфности двух данных графов.(Π(i),Π(j))G2

Есть ли операция над графами, которая производит «усиление зазора» в стиле доказательства Динура теоремы PCP ? Другими словами, существует ли вычисляемое преобразование за полиномиальное время из в ( G 1 , G 2 ) такое, что(G1,G2)(G1,G2)

  • если и G 2 изоморфны, то G ' 1 и G ' 2 также изоморфны, иG1G2G1G2
  • если и G - не изоморфны, то для каждой перестановки П , граф G ' 1 является « ε -far» от П ( G ' 2 ) для некоторых малых постоянная е , где & epsi ; -far означает , что , если мы выбираем ( i , j ) равномерно случайным образом, то с вероятностью ϵ либо G1G2ΠG1ϵΠ(G2)ϵϵ(i,j)ϵ
    • является ребром G 1 и ( Π ( i ) , Π ( j ) ) не является ребром G 2 , или(i,j)G1(Π(i),Π(j))G2
    • не является ребром в G 1, а ( Π ( i ) , Π ( j ) ) является ребром в G 2 .(i,j)G1(Π(i),Π(j))G2
Андре Шайо
источник
5
@domotorp: «Преобразование за полиномиальное время» - это стандартная терминология, относящаяся к детерминированной машине Тьюринга за полиномиальное время, вход и выход которой являются строками. В этом случае эта машина Тьюринга принимает пару (G1, G2) в качестве входных данных и генерирует пару (G′1, G′2) в качестве выходных данных. Каждый график кодируется, например, как смежная матрица.
Цуёси Ито
1
Я думал, что теорема PCP справедлива для любой задачи NP, поэтому в особенности она должна выполняться для изоморфизма графов?
Денис
2
@dkuper Автор хочет спросить, существует ли редукция, усиливающая разрыв, которая сводит случаи изоморфизма графов к случаям изоморфизма графов с большим разрывом; он не спрашивает непосредственно о теореме PCP, а только о методике, используемой для доказательства твердости аппроксимации ...
argentpepper
3
Возможно, это длинный путь, но не могли бы вы показать, что если бы это было так, то вы могли бы решить изоморфизм графов за квантовое полиномиальное время?
Нил Янг
3
Это согласуется с современным уровнем знаний о том, что даже SAT имеет линейный алгоритм времени, поэтому то, что вы написали, вряд ли будет известно. Если это так, пожалуйста, добавьте ссылку на ваш ответ.
Каве

Ответы:

2

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

В этой статье дается алгоритм аппроксимации для задачи «MAX-PGI» максимизации согласованных пар ребер / не ребер; если мы уменьшаем GI до «Gap-MAX-PGI», то мы можем приблизиться, чтобы различить, на какой стороне разрыва мы находимся.

Итак, я думаю, что доказательство Динуром теоремы PCP вряд ли будет непосредственно обобщено на такой «усилитель с зазором», учитывая препятствия, которые должны быть преодолены.

Джо Бебель
источник