Вопросы с тегом «graph-isomorphism»

Два графа G, H изоморфны, если существует перемаркировка вершин G, порождающих H, и наоборот. Задача об изоморфизме графа (GI) состоит в том, чтобы решить, являются ли два заданных изоморфными. Помимо практического интереса, он был идентифицирован Карпом в 1972 году как имеющий неизвестную сложность, являющийся одним из немногих оставшихся естественных кандидатов для NP-промежуточной задачи, и привел к созданию класса сложности AM.

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

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

40
Последствия квазиполиномиального алгоритма времени для задачи об изоморфизме графа

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

36
Методы показа этой проблемы в твердости «подвешенный»

Учитывая новую проблему в , истинная сложность которой находится где-то между и являющейся NP-полной, я знаю два метода, которые можно использовать, чтобы доказать, что решить эту проблему сложно:NPNP\mathsf{NP}PP\mathsf{P} Покажите, что задача является GI-полной (GI = Изоморфизм графов) Покажите,...

30
Можно ли решить изоморфизм графа с ограниченным квадратным недетерминизмом?

Ограниченность недетерминизм связывает функцию g(n)g(n)g(n) с классом языков , принятых ресурсы ограничены детерминированные тьюринговых машинами, чтобы сформировать новый класс - . Этот класс состоит из тех языков, которые принимаются некоторой недетерминированной машиной Тьюринга подчиняющейся...

29
сертификат coNP для изоморфизма графов

Легко видеть, что изоморфизм графов (GI) находится в NP. Это большая открытая проблема, находится ли GI в coNP. Существуют ли потенциальные кандидаты в свойства графов, которые можно использовать как сертификаты coNP GI. Какие-нибудь домыслы, которые подразумевают ? Каковы некоторые последствия ?G...

24
Доказательство опровержения: любительские обзоры амбициозных документов CoRR

Я предполагаю, что я прочитал слишком много амбициозных статей CoRR . Проблема в том, что эти документы не рецензируются, но часто звучат интересно и проходят базовые проверки правдоподобия. Или, может быть, нет, и мне просто нужно улучшить проверку правдоподобия. Вот недавний образец таких работ:...

23
Каков статус результата изоморфизма графа Бабая?

Прошло более года с момента его отвода и исправления в январе 2017 года. Есть ли новости? Если нет, то нормально ли это для проверки? Я ожидаю, что это привлечет много внимания. Кто-нибудь отметил, чтобы поддержать / сомневаться в квазиполиномиальном...

23
Каковы доказательства того, что изоморфизм графов отсутствует в

По мотивам комментария Фортнау к моему сообщению, доказательством того, что проблема изоморфизма графов не является NпNпNP -полным , и тем фактом, что G IгяGI является главным кандидатом в NпNпNP -проблеменную проблему (не NпNпNP -полное ни в ппP ), я заинтересованы в известных доказательств , что...

21
Какова текущая известная твердость изоморфизма графов?

Вдохновленный вопросом, что факторинг известен как P-hard , мне интересно, каково текущее подобное состояние знаний о твердости изоморфизма графов. Я уверен, что в настоящее время неизвестно, находится ли G в P, но: какой самый известный в настоящее время класс, чем GI сложнее? (не было ответа на...

19
«Крошечный» граф Изоморфизм

Размышляя о сложности проверки изоморфизма асимметричных графов (см. Мой связанный с этим вопрос о теории), у меня возник дополнительный вопрос. Предположим, что у нас есть машина Тьюринга за полиномиальное время которая на входе генерирует граф с узлами.1 n G M , n nMMM1n1n1^nGM,nGM,nG_{M,n}nnn Мы...

18
Открытые проблемы, связанные с изоморфизмом графа

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

17
Нежное введение в изоморфизм графов для ограниченных валансных графов

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

17
Проблема изоморфизма графов

Я делаю обзор литературы по проблеме изоморфизма графов. Большинство статей, которые я читаю, написаны Э. М. Луксом и Ласло Бабаи. В этих работах используются знания высокого уровня теории групп и теории сложности. Поскольку я новичок в этой области, многие вещи мне не понятны. Может кто-нибудь...

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

При условии, что группа симметрии и две подгруппы и , имеет ли место ?SnSnS_nG,H≤SnG,H≤SnG, H\leq S_nπ∈Snπ∈Sn\pi\in S_nGπ∩H=∅Gπ∩H=∅G\pi\cap H=\emptyset Насколько я знаю, эта проблема известна как проблема пересечения смежных классов. Мне интересно, в чем сложность? В частности, известна ли эта...

16
Взаимосвязь между симметрией и вычислительной непроницаемостью?

-fixed точки без проблем автоморфизма запрашивает автоморфизм графа , который перемещается по крайней мере , к ( п ) узлы. Проблема в том, что N P- полна, если k ( n ) = n c для любого c > 0.kkkk(n)k(n)k(n)NPNPNPk(n)=nck(n)=nck(n)=n^cccc Однако, если то задача полиномиального времени Тьюринга...

16
NP-сложность проблемы разбиения графа?

Меня интересует эта проблема: учитывая неориентированный граф , существует ли разбиение G на графы G 1 ( E 1 , V 1 ) и G 2 ( E 2 , V 2 ), такие что G 1 а G 2 изоморфны?G(E,V)G(E,V)G(E, V)GGGG1(E1,V1)G1(E1,V1)G_1(E_1, V_1)G2(E2,V2)G2(E2,V2)G_2(E_2, V_2)G1G1G_1G2G2G_2 Здесь разбивается на два...

16
Жесткие экземпляры для проверки изоморфизма графов

Является ли случай строго регулярных графов самым сложным для тестирования ЖКТ? где «самый трудный» используется в некотором смысле «здравый смысл», или, так сказать, «в среднем». Wolfram MathWorld упоминает некоторые «патологически сложные графы». Кто они такие? Мой примерный набор из 25 пар...

16
Контрпример для эффективного алгоритма Корнеила для графа Изоморфизм

В работе «Эффективный алгоритм изоморфизма графов » Корнейла и Готлиба, 1970 г. была высказана гипотеза, на которой основывался алгоритм для решения GI за полиномиальное время. А именно: что репрезентативные графы демонстрируют автоморфизм разбиения данного графа Очевидно, что эта гипотеза не...

16
Сильно регулярный граф и GI-полнота

Не известно , если изоморфизм графов (GI) для сильно регулярных графов (SRGS) в P . Есть ли намеки на то, что это может или не может быть GI- Complete? Есть ли сильные последствия в таких случаях? (Аналогично убеждению, что GI не может быть...