Детерминированный параллельный алгоритм для идеального сопоставления в общих графах?

20

В классе сложности есть некоторые проблемы, предположительно не входящие в класс N C , то есть проблемы с детерминированными параллельными алгоритмами. Проблема максимального потока является одним из примеров. И есть проблемы, СЧИТАЕМЫЕ быть в N C , но доказательство еще не найдено.PNCNC

Идеальный Matching проблема является одной из наиболее фундаментальной проблемы , затронутой в теории графов: для графа , мы должны найти идеальное соответствие для G . Как я мог найти в интернете, несмотря на прекрасный алгоритм Блоссома с полиномиальным временем Эдмондса и RANDOMIZED параллельный алгоритм Карпа, Апфала и Вигдерсона в 1986 году, известно, что только несколько подклассов графов имеют N C алгоритмов.GGNC

В январе 2005 года есть запись в блоге вычислительной сложности , что претензии он остается открытым ли паросочетания в . Мой вопрос:NC

Есть ли какой-либо прогресс с тех пор, кроме рандомизированного алгоритма ?NC

Чтобы прояснить мой интерес, любой алгоритм, который имеет дело с общими графами, хорош. Хотя алгоритмы для подклассов графов тоже в порядке, это может быть не мое внимание. Спасибо вам всем!


РЕДАКТИРОВАТЬ в 12/27:

Спасибо за вашу помощь, я стараюсь обобщить все результаты в одну цифру: Отношения между классами, связанные с соответствием

Наименее известные классы содержат следующие проблемы:

  • Сопоставление в общих графах: [ KUW86 ], R N C 2 [ CRS93 ]RNCRNC2
  • Соответствие в двудольных планарных / константных графах: / S P L [ DKT10 ] / [ DKTV10 ]ULSPL
  • Соответствует, когда общее число является полиномиальным: [ H09 ]SPL
  • Максимальное совпадение с первым Lex: [ MS89 ]CC

Кроме того, при предположении вероятной сложности: для требуются экспоненциальные схемы, в общих графах сопоставление выполняется в S P L [ ARZ98 ].SPACE[n]SPL

Сянь-Чжи Чан 張顯 之
источник
1
Возможно, это не имеет прямого отношения, но в детерминированных алгоритмах достигнут определенный прогресс в подсчете количества совершенных совпадений, например, «Алгоритм детерминированной аппроксимации Гамарника для вычисления перманента матрицы 0,1»
Ярослав Булатов
2
Здесь есть похожая
Сянь-Чи Чанг 張顯 之
@ Hsien-ChihChang 張顯 之 Разве не L в NC, который находится в NC ^ 2, который находится в P?
T ....

Ответы:

13

NC

NC2

NCPNCNC

ULNCULNC

Надеюсь это поможет.

Ramprasad
источник
1
Да, я заметил результат Винодчандран-Тевари. На самом деле, этот пост каким-то образом мотивирован их результатом, но не напрямую. Я проверю бумаги Агравал-Хоанг-Тирауф!
Сянь-Чи Чан 之
10

Несколько лет спустя :) и Perfect Matching теперь известны в Quasi-NC (то есть, вам нужно квазиполиномиально много процессоров). См. Статью Феннера, Гурджара и Тирауфа (для двудольных графов) https://arxiv.org/pdf/1601.06319.pdf и нашу работу с Олой Свенссон (для общих графиков): https://arxiv.org/pdf/1704.01929

Якуб Тарнавский
источник
8

Дерандомизация леммы об изоляции по Тевари-Винодчандрану, к сожалению, не дает верхней границы UL для плоского сопоставления. На самом деле я даже не думаю, что алгоритм NC не известен для плоского сопоставления. Но в недавней работе с Datta, Kulkarni и Nimbhorkar мы показываем верхнюю границу UL для двустороннего плоского сопоставления (запись этого результата все еще продолжается). Это интересно, потому что до этого даже NL-граница не была известна для этой проблемы.

Рагхунат Тевари
источник
Добро пожаловать на биржу стека TCS!
Сянь-Чжи Чанг 之 之
Теперь я нашла статью Датты, Кулкарни и тебя. Я прочитаю это как можно скорее, спасибо!
Сянь-Чи Чанг 27 之
7

Когда известно, что проблема оптимизации трудна, обычно рассматривают их максимальные версии. Например, в то время как независимый набор является NP-Complete, лекс первый максимальный независимый набор, который является P-Complete.

n

Все это говорит о том, что не может быть легко распараллеливаемой версии NC для этого. Но тогда кто знает? Кто-то может дерандомизировать версию RNC на следующей неделе!

Редактировать: Спасибо, Рампрасад. Но вот еще одна ссылка на статью.

V Vinay
источник
1
К сожалению, у меня нет учетной записи для доступа к бумаге. Какое у него название?
Сянь-Чи Чанг 之 之
1
«Сложность схемы и стабильность сети». Я поместил копию этого документа здесь: cmi.ac.in/~ramprasad/00041817.pdf (надеюсь, проблем с авторским правом нет!)
Ramprasad
1

(1ϵ)NCnΘ(1/ϵ)O(log3n)

Т. Фишер, А. В. Гольдберг, DJ Хаглин и С. Плоткин. Аппроксимирующие совпадения параллельно. Информация. Proc. Lett., 46 (3): 115, 1993

Мухаммед Аль-Туркистани
источник