Número isoperimétrico de um gráfico de vértice

Número isoperimétrico de um gráfico de vértice - NP-difícil?

$G=(V,E)$
$i_V(G) = \min\{\frac{|N(S)|}{|S|} : S \subseteq V, 1\le |S|\le \frac{|V|}{2}\}$

Você pode dar uma referência onde o seguinte problema é mostrado NP-complete: dado um gráfico e um número , a questão é decidir se tem um número isoperimétrico de vértice no máximo ? $G$ $t$ $G$ $t$

reference-request graph-theory np-hardness Serge Gaspers
fonte

Não está perto do corte máximo?

Saeed

Max Cut está realmente mais próximo da constante Cheeger, onde, na definição acima,é substituído pelo número de arestas com um ponto final em e o outro em . Para a constante Cheeger, as provas de dureza NP são facilmente encontradas na literatura.

| N (S) |

$|N(S)|$

S

$S$

N (S)

$N(S)$

Serge Gaspers

O seguinte pode ser útil. sciencedirect.com/science/article/pii/0020019081900508

Chandra Chekuri

Respostas:

O seguinte artigo: Sobre um problema isoperimétrico para gráficos de Hamming LH Harper. contém o seguinte:

O problema de vértice-isoperimetria é NP-completo [8] em geral, portanto, nenhuma solução polinomialmente limitada é conhecida e é improvável que exista uma.

Onde a referência [8] é MR Garey, DS Johnson, Computers and Intratability: A Guide to Theory of NP-Completeness ,

Este livro geralmente contém uma prova ou uma referência à prova. Infelizmente, não tenho acesso ao livro no momento.

user53923
fonte

Mas a variante de problema NP-difícil no artigo de Harper é diferente: dado um gráfico G e um número k, encontre um subconjunto S dos vértices com | S | = k que minimiza | N (S) |.

Gamow

Entendo, você está certo.

user53923