Computar a constante Cheeger de um gráfico , também conhecida como constante isoperimétrica (porque é essencialmente uma relação área / volume mínima), é conhecida por ser NP-completa. Geralmente é aproximado. Estou interessado em saber se os algoritmos polinomiais exatos são conhecidos para classes especiais de gráficos. Por exemplo, ainda é NP-completo para gráficos regulares ? Para gráficos regulares à distância ? (Não estudei as provas de completude de NP existentes para examinar suas suposições.) Indicadores de literatura apreciados - obrigado!
ds.algorithms
reference-request
graph-algorithms
Joseph O'Rourke
fonte
fonte
Respostas:
Observe que a aproximação do corte mais esparso dentro de fornece uma aproximação de 2 α para a constante Cheeger, conforme definido. Aqui estão alguns trabalhos que fornecem algoritmos de aproximação constante para cortes mais esparsos em gráficos restritos:α 2 α
Gênero limitado: http://dl.acm.org/citation.cfm?id=1873619
Largura da árvore limitada: http://arxiv.org/abs/1006.3970
Além disso, http://arxiv.org/abs/1006.3970v2 prova que o corte mais esparso é NP-difícil para gráficos com largura de caminho 2 e tem muito mais referências à aproximação do corte mais esparso em instâncias restritas.
Eu diria que, para todas as classes de gráficos mencionadas no artigo, nenhum algoritmo exato é conhecido (pois eles estão interessados em aproximações). Em particular, se o corte mais esparso é NP-difícil para gráficos com largura de caminho 2, também é NP-difícil para gráficos de largura de árvore 2 e largura de corte 2. Suponho que isso não dê muito espaço .. talvez haja outro melhor parametrização para corte mais esparso.
Tenho certeza de que o corte mais esparso é NP-difícil em gráficos regulares, mas não consigo encontrar uma referência.
Per notou que não tomei cuidado ao olhar para os papéis acima. O resultado da dureza é para cortes esparsos não uniformes. A computação de um corte mais esparso uniforme ou a constante Cheeger é fácil nas árvores (WLOG, o corte ideal separa uma subárvore). Com um pouco mais de trabalho que fornece um algoritmo de programação dinâmica para calcular a constante Cheeger em gráficos de largura de árvore limitados.
A Tabela 1 no artigo 2 acima também menciona um resultado que fornece uma aproximação constante para gráficos com um menor excluído.
fonte
Para obter uma solução exata em gráficos planares, consulte Park e Phillips, STOC 93 . Isso é essencialmente para as demandas uniformes de corte mais esparso, com a menor diferença de que seu denominador é | S | em vez de | S | * | VS |. Conforme apontado por Per, o caso de demandas não uniformes é diferente.
fonte