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

Número isoperimétrico de vértice de un gráfico - NP-hard?

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

¿Puede dar una referencia donde el siguiente problema se muestra NP completo: dado un gráfico y un número , la pregunta es decidir si tiene un número isoperimétrico de vértice como máximo ? $G$ $t$ $G$ $t$

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

¿No está esto cerca del corte máximo?

Saeed

Max Cut está realmente más cerca de la constante Cheeger, donde, en la definición anterior,se reemplaza por el número de aristas con un punto final en y el otro en . Para la constante Cheeger, las pruebas de dureza NP se encuentran fácilmente en la literatura.

| N (S) |

$|N(S)|$

S

$S$

N (S)

$N(S)$

Serge Gaspers

Lo siguiente puede ser útil. sciencedirect.com/science/article/pii/0020019081900508

Chandra Chekuri

Respuestas:

El siguiente documento: Sobre un problema isoperimétrico para los gráficos de Hamming LH Harper. contiene lo siguiente:

El problema del vértice isoperimétrico es NP-completo [8] en general, por lo que no se conoce una solución polinomialmente limitada y es poco probable que exista una.

Donde la referencia [8] es MR Garey, DS Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness ,

Este libro generalmente contiene una prueba o una referencia a la prueba. Lamentablemente no tengo acceso al libro en este momento.

usuario53923
fuente

Pero la variante del problema NP-hard en el artículo de Harper es diferente: dado un gráfico G y un entero k, encuentre un subconjunto S de los vértices con | S | = k que minimice | N (S) |.

Gamow

Ya veo, tienes razón.

user53923