Algoritmo determinístico paralelo para correspondência perfeita em gráficos gerais?

20

Na classe de complexidade , existem alguns problemas conjecturados para NÃO pertencer à classe N C , ou seja, problemas com algoritmos paralelos determinísticos. O problema de fluxo máximo é um exemplo. E acredita-se que haja problemas em N C , mas uma prova ainda não foi encontrada.PNCNC

Perfeito Matching problema é um dos problemas mais fundamental levantado em teoria dos grafos: dado um grafo , temos de encontrar uma correspondência perfeita para G . Como pude encontrar na internet, apesar do belo algoritmo polinomial Blossom, de Edmonds, e de um algoritmo paralelo RANDOMIZED, de Karp, Upfal e Wigderson, em 1986, sabe-se que apenas algumas subclasses de gráficos possuem algoritmos N C.GGNC

Em janeiro de 2005, há um post no blog Complexidade Computacional que afirma que permanece em aberto se Perfeito Matching está em . Minha pergunta é:NC

Existe algum progresso desde então, além do algoritmo aleatório ?NC

Para esclarecer meu interesse, qualquer algoritmo que lide com gráficos GERAIS é bom. Embora algoritmos para subclasses de gráficos também sejam bons, isso pode não estar nas minhas atenções. Obrigado a todos!


EDIT em 27/12:

Obrigado por toda sua ajuda, tento resumir todos os resultados em uma figura: Relações entre classes relacionadas a Correspondência

As classes mais baixas conhecidas contêm os seguintes problemas:

  • Correspondência em gráficos gerais: [ KUW86 ], R N C 2 [ CRS93 ]RNCRNC2
  • Correspondência em gráficos bipartidos de gênero planar / constante: / S P L [ DKT10 ] / [ DKTV10 ]ULSPL
  • Correspondência quando o número total é polinomial: [ H09 ]SPL
  • Primeira correspondência máxima de Lex: [ MS89 ]CC

Além disso, sob suposição de complexidade plausível: requer circuitos exponenciais, a correspondência nos gráficos gerais está em S P L [ ARZ98 ].SPACE[n]SPL

Hsien-Chih Chang 張顯 之
fonte
1
Talvez não diretamente relevante, mas tem havido algum progresso no algoritmo determinístico para contar o número de emparelhamentos perfeitos, ou seja, "Aproximação algoritmo determinístico para computação um Permanente de uma matriz de 0,1" de Gamarnik
Yaroslav Bulatov
2
Existe uma publicação relacionada aqui por Robin Kothari: cstheory.stackexchange.com/questions/1317/…
Hsien-Chih Chang,
@ Hsien-ChihChang 之 之 Não é L no NC, que está no NC ^ 2, que está no P?
T ....

Respostas:

13

algoritmos N C para combinações perfeitas nos gráficos gerais ainda estão abertos, mas houve algum progresso. Aqui estão alguns que eu conheço:NC

Para gráficos gerais, Agrawal-Hoang-Thierauf mostrou que, dada a promessa de que o número de combinações perfeitas é pequeno, existe um algoritmo para enumerar todas elas.NC2

Para a classe de gráficos planares, o pfaffian desempenha um grande papel. Kastelyn mostrou como todo gráfico planar pode ser orientado de tal maneira que o pfaffian seja exatamente igual ao número de combinações perfeitas. (Isso foi usado por Valiant para fornecer " algoritmos holográficos " para vários problemas) Mahajan-Subramanya-Vinay mostrou como o pfaffian pode ser calculado em usando modificações de sequências de clow. (Kastelyn, de fato, fornece um algoritmo para encontrar a incorporação em P, mas não tenho certeza se a incorporação pfaffian também pode ser calculada em N C ; se sim, isso significaria que a contagem de combinações perfeitas em gráficos planares está em N C. )NCPNCNC

ULNCULNC

Espero que isto ajude.

Ramprasad
fonte
1
Sim, eu notei o resultado de Vinodchandran-Tewari. De fato, este post é motivado pelo resultado de alguma forma, embora não diretamente. Vou verificar o artigo de Agrawal-Hoang-Thierauf!
Hsien-Chih Chang # 15/1110
10

Alguns anos depois :) e o Perfect Matching agora é conhecido como Quasi-NC (ou seja, você precisa de quase polinomialmente muitos processadores). Veja o artigo de Fenner, Gurjar e Thierauf (para gráficos bipartidos) https://arxiv.org/pdf/1601.06319.pdf e nosso trabalho com Ola Svensson (para gráficos gerais): https://arxiv.org/pdf/1704.01929

Jakub Tarnawski
fonte
8

Infelizmente, a derandomização do lema de isolamento por Tewari-Vinodchandran não fornece um limite superior de UL na correspondência planar. Na verdade, eu nem acho que um algoritmo NC não seja conhecido pela correspondência planar. Porém, em um trabalho recente com Datta, Kulkarni e Nimbhorkar, mostramos um limite superior do UL na correspondência planar bipartida (a redação desse resultado ainda está em andamento). Isso é interessante porque antes disso, mesmo um limite NL não era conhecido por esse problema.

Raghunath Tewari
fonte
Bem-vindo ao TCS Stack Exchange!
Hsien-Chih Chang # 15/1110
Agora encontrei o artigo de Datta, Kulkarni e você. Vou ler o mais rápido possível, obrigado !!
Hsien-Chih Chang,
7

Quando se sabe que um problema de otimização é difícil, é comum observar suas versões máximas. Por exemplo, enquanto o conjunto independente é NP-Complete, o lex primeiro conjunto independente máximo, que é P-Complete.

n

Tudo isso indica que pode não haver uma versão NC facilmente paralelizável para isso. Mas então quem sabe? Alguém pode derandomizar a versão RNC na próxima semana!

Edit: Obrigado Ramprasad. Mas aqui está outro link para o jornal.

V Vinay
fonte
1
Ops, não tenho conta para acessar o documento. Qual é o título dele?
Hsien-Chih Chang,
1
"A complexidade do valor do circuito e a estabilidade da rede". Eu coloquei uma cópia do documento aqui: cmi.ac.in/~ramprasad/00041817.pdf (esperança não existem questões de direitos autorais!)
Ramprasad
1

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

T. Fischer, AV Goldberg, DJ Haglin e S. Plotkin. Aproximações correspondentes em paralelo. Info. Proc. Lett., 46 (3): 115, 1993

Mohammad Al-Turkistany
fonte