Computando a constante Cheeger: viável para quais classes?

19

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!

Joseph O'Rourke
fonte
3
Essa é uma boa pergunta. As aproximações têm algo a ver com os métodos de corte mais esparsos?
Suresh Venkat
11
Eu sei que essa é uma pergunta antiga, mas eu queria saber se alguém sabia de uma aproximação de tempo polinomial para gráficos gerais que obtêm a constante dentro de uma porcentagem fixa?
yberman

Respostas:

11

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α

  1. Gênero limitado: http://dl.acm.org/citation.cfm?id=1873619

  2. 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.

O(logg)g

Sasho Nikolov
fonte
Você não pode regular qualquer gráfico adicionando auto-loops?
MCH 14/10
2
@MCH dessa forma vértices grau ímpar permanecem grau pares e ímpares vértices de grau permanecem mesmo grau
Sasho Nikolov
11
O resultado da dureza que você mencionou para a largura do caminho 2 é para cortes esparsos não uniformes , o que não é relevante para a constante Cheeger. De fato, até onde eu posso ver, é fácil calcular o corte mais esparso uniforme ou a constante Cheeger exatamente em gráficos de largura de árvore limitada.
Por Austrin
5

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.

Robert Krauthgamer
fonte