Сложность «граф продукт»

25

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

Существуют различные графические продукты, и я заинтересован в любом из них здесь. В чем сложность определения того, является ли граф изоморфным нетривиальному произведению? (Конечно, для декартового произведения где - граф с одной вершиной.)K = K 1KK=K11

Я посмотрел на страницах «Фактор графа» и «График факторизации» в Википедии, но ни один из них, похоже, не связан. Эта проблема известна под другим именем?

Максимум
источник

Ответы:

15

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


Более детально:

Пусть Γ - класс конечных простых графов, а Γ0 - класс конечных простых графов, которые могут иметь самоконтроли. (Понятно ΓΓ0 .)

Решение о том, имеет ли связанный входной граф факторы в может быть за полиномиальное время для декартовых и сильных произведений, а также для прямого произведения, когда не двудольный. Решение о том, имеет ли факторы в принимается за полиномиальное время для декартового произведения, но вряд ли будет за полиномиальное время для лексикографического произведения. Я не знаю статус решения, если имеет факторы в для прямых и сильных продуктов.Γ 0 G G Γ G ΓGΓ0GGΓGΓ

Соответствующие результаты от Имрича и Клавжара:

Теорема 4.10. Для связного графа на вершинах и ребрах можно найти простую факторизацию по декартовому произведению за времени, используя пространство .н м О ( м н ) О ( м )GnmO(mn)O(m)

Теорема 5.43. Первичное множитель разложения связных недвойственных графов в относительно прямого произведения и связных простых графов относительно сильного произведения может быть определен за полиномиальное время.Γ0

Затем результат для декартового произведения улучшается до времени и пространства в главе 7. Как указывалось в других ответах, с тех пор оно было улучшено до линейного времени.O ( м )O(mlogn)O(m)

Для лексикографического продукта:

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

Теорема 6.21. Решение задачи о том, является ли данный связный граф простым по отношению к лексикографическому произведению, не сложнее, чем решение полиномиального числа (по ) задач изоморфизма графов, размер каждой из которых также является полиномом по .нnn

Поэтому решение о том, является ли граф простым по отношению к лексикографическому произведению, эквивалентно изоморфизму ГРАФА в отношении сокращений по Тьюрингу.

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

  • Вильфрид Имрич и Сэнди Клавжар. Графики продуктов: структура и признание . Wiley, 2000. ISBN 0-471-37039-8.
Андраш Саламон
источник
Я принял @ чей-то ответ, но спасибо за дополнительную информацию.
Макс
12

Существует линейно-временной алгоритм определения простых множителей связных графов относительно декартового произведения. Смотрите статью Имрича и Петерина.

Йота Отачи
источник