Hipótesis de expansión de conjuntos pequeños

Supuesto de dureza computacional

La hipótesis de expansión de conjuntos pequeños o conjetura de expansión de conjuntos pequeños en la teoría de la complejidad computacional es un supuesto de dificultad computacional no demostrado . Según la hipótesis de expansión de conjuntos pequeños, se supone que es computacionalmente inviable distinguir entre una cierta clase de grafos expansores llamados "expansores de conjuntos pequeños" y otros grafos que están muy lejos de ser expansores de conjuntos pequeños. Este supuesto implica la dificultad de varios otros problemas computacionales y la optimalidad de ciertos algoritmos de aproximación conocidos .

La hipótesis de expansión de conjuntos pequeños está relacionada con la conjetura de los juegos únicos , otro supuesto de dificultad computacional no demostrado según el cual aproximar con precisión el valor de ciertos juegos es computacionalmente inviable. Si la hipótesis de expansión de conjuntos pequeños es verdadera, entonces también lo es la conjetura de los juegos únicos.

Fondo

Expansión de aristas frente a conjuntos pequeños. El gráfico de hipercubo de 16 vértices que se muestra tiene para las ocho aristas rojas y los ocho vértices azules que se muestran a la izquierda, por lo que su expansión de aristas es 1. Para conjuntos pequeños de como máximo vértices, la relación mínima entre aristas y vértices es , para las ocho aristas rojas y los cuatro vértices azules que se muestran a la derecha, por lo que su expansión de conjunto pequeño es 2. ${\displaystyle |\partial X|/|X|=8/8=1}$ ${\displaystyle n/\log _{2}n=4}$ ${\displaystyle 8/4=2}$

La expansión de aristas de un conjunto de vértices en un grafo se define como donde las barras verticales denotan el número de elementos de un conjunto , y denota el conjunto de aristas que tienen un punto final en y el otro punto final en su complemento. ^[a] Este número puede ser tan bajo como cero, cuando es un componente conexo del grafo, porque en este caso no hay aristas que se conecten a otras partes del grafo. Un grafo se llama regular o -regular cuando cada vértice incide en el mismo número de aristas, , el grado del grafo. Para un grafo -regular, la máxima expansión de aristas posible es . Esta expansión se logra mediante cualquier subconjunto que induzca un conjunto independiente , ya que en este caso todas las aristas que tocan vértices en pertenecen a . ^{[1] [2]} ${\displaystyle X}$ ${\displaystyle G}$ $${\displaystyle {\frac {|\partial X|}{|X|}},}$$ ${\displaystyle \partial X}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle d}$ ${\displaystyle d}$ ${\displaystyle d}$ ${\displaystyle d}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle \partial X}$

La expansión de aristas de un grafo con vértices se define como la expansión de aristas mínima entre sus subconjuntos de como máximo vértices. ^[b] En cambio, la expansión de conjuntos pequeños se define como el mismo mínimo, pero solo sobre subconjuntos más pequeños, de como máximo vértices. De manera informal, un expansor de conjuntos pequeños es un grafo cuya expansión de conjuntos pequeños es grande. ^{[1] [c]} ${\displaystyle n}$ ${\displaystyle n/2}$ ${\displaystyle n/\log _{2}n}$

Declaración

La hipótesis de expansión de conjuntos pequeños utiliza un número real como parámetro para formalizar lo que significa que la expansión de un conjunto pequeño de un grafo sea grande o pequeña. Afirma que, para cada , es NP-difícil distinguir entre grafos -regulares con expansión de conjuntos pequeños al menos (buenos expansores de conjuntos pequeños), y grafos -regulares con expansión de conjuntos pequeños como máximo (muy lejos de ser un expansor de conjuntos pequeños). Aquí, el grado es una variable que podría depender de la elección de , a diferencia de muchas aplicaciones de grafos expansores donde se supone que el grado es una constante fija. ^{[1] [c]} ${\displaystyle \varepsilon }$ ${\displaystyle \varepsilon >0}$ ${\displaystyle d}$ ${\displaystyle (1-\varepsilon )d}$ ${\displaystyle d}$ ${\displaystyle \varepsilon d}$ ${\displaystyle d}$ ${\displaystyle \varepsilon }$

Consecuencias

La hipótesis de expansión de conjuntos pequeños implica la NP-dureza de varios otros problemas computacionales. Como es sólo una hipótesis, esto no prueba que estos problemas sean realmente NP-duros. Sin embargo, sugiere que sería difícil encontrar una solución eficiente para estos problemas, porque resolver cualquiera de ellos también resolvería otros problemas cuya solución hasta ahora ha sido esquiva (incluido el propio problema de expansión de conjuntos pequeños). En la otra dirección, esta implicación abre la puerta a la refutación de la hipótesis de expansión de conjuntos pequeños, al proporcionar otros problemas a través de los cuales podría ser atacada. ^[1]

En particular, existe una reducción en tiempo polinomial desde el reconocimiento de expansores de conjuntos pequeños hasta el problema de determinar el valor aproximado de juegos únicos, mostrando que la hipótesis de expansión de conjuntos pequeños implica la conjetura de juegos únicos . ^{[1] [2]} Boaz Barak ha sugerido con más fuerza que estas dos hipótesis son equivalentes. ^[1] De hecho, la hipótesis de expansión de conjuntos pequeños es equivalente a una forma restringida de la conjetura de juegos únicos, afirmando la dureza de las instancias de juegos únicos cuyos gráficos subyacentes son expansores de conjuntos pequeños. ^[3] Por otro lado, es posible resolver rápidamente instancias de juegos únicos cuyo gráfico es "certificadamente" un expansor de conjuntos pequeños, en el sentido de que su expansión puede verificarse mediante optimización de suma de cuadrados . ^[4]

Otra aplicación de la hipótesis de expansión de conjuntos pequeños se refiere al problema computacional de aproximar el ancho de árbol de grafos, un parámetro estructural estrechamente relacionado con la expansión. Para grafos de ancho de árbol , la mejor razón de aproximación conocida para un algoritmo de aproximación de tiempo polinomial es . ^[5] La hipótesis de expansión de conjuntos pequeños, si es verdadera, implica que no existe un algoritmo de aproximación para este problema con razón de aproximación constante. ^[6] También se puede utilizar para implicar la inaproximabilidad de encontrar un grafo bipartito completo con el número máximo de aristas (posiblemente restringido a tener números iguales de vértices en cada lado de su bipartición) en un grafo más grande. ^[7] ${\displaystyle w}$ ${\displaystyle O({\sqrt {\log w}})}$

La hipótesis de expansión de conjuntos pequeños implica la optimalidad de razones de aproximación conocidas para ciertas variantes del problema de cobertura de aristas , en el que se deben elegir la menor cantidad posible de vértices para cubrir un número dado de aristas en un gráfico. ^[8]

Historia y resultados parciales

La hipótesis de expansión de conjuntos pequeños fue formulada y conectada con la conjetura de juegos únicos por Prasad Raghavendra y David Steurer en 2010, ^[2] como parte de un conjunto de trabajos por el que recibieron el Premio Michael y Sheila Held 2018 de la Academia Nacional de Ciencias . ^[9]

Un enfoque para resolver la hipótesis de expansión de conjuntos pequeños es buscar algoritmos de aproximación para la expansión de aristas de conjuntos de vértices pequeños que sean lo suficientemente buenos para distinguir las dos clases de grafos en la hipótesis. En este sentido, la mejor aproximación conocida, para la expansión de aristas de subconjuntos de como máximo vértices en un grafo -regular, tiene una razón de aproximación de . Esto no es lo suficientemente fuerte como para refutar la hipótesis; hacerlo requeriría encontrar un algoritmo con una razón de aproximación acotada. ^[10] ${\displaystyle n/\log n}$ ${\displaystyle d}$ ${\displaystyle O({\sqrt {\log n\log \log n}})}$

Notas

1. Esta definición sigue la notación utilizada en el artículo sobre gráficos expansores ; algunas fuentes, como Raghavendra y Steurer (2010), en cambio normalizan la expansión del borde dividiéndola por el grado del gráfico.
2. Esta definición evita el uso de subconjuntos cuyo número de vértices sea cercano a , porque estos subconjuntos tendrían una pequeña expansión incluso en gráficos que de otro modo tendrían una alta expansión. ${\displaystyle n}$
3. Esta formulación es de Barak (2016), quien señala que elimina algunos parámetros sin importancia que aparecen en otras formulaciones de la misma hipótesis, como la de Raghavendra y Steurer (2010).

Referencias

1. Barak, Boaz (2016), "SOS Lecture 6: The SOS approach to refuting the UGC" (PDF) , Notas de la conferencia sobre "Pruebas, creencias y algoritmos a través de la lente de la suma de cuadrados" , consultado el 14 de marzo de 2023
2. Raghavendra, Prasad; Steurer, David (2010), "Expansión de grafos y la conjetura de juegos únicos", en Schulman, Leonard J. (ed.), Actas del 42.º Simposio ACM sobre teoría de la computación, STOC 2010, Cambridge, Massachusetts, EE. UU., 5-8 de junio de 2010 (PDF) , Association for Computing Machinery, págs. 755-764, doi :10.1145/1806689.1806792, S2CID  1601199
3. Raghavendra, Prasad; Steurer, David; Tulsiani, Madhur (2012), "Reducciones entre problemas de expansión", Actas de la 27.ª Conferencia sobre Complejidad Computacional, CCC 2012, Oporto, Portugal, 26-29 de junio de 2012 , IEEE Computer Society, págs. 64-73, arXiv : 1011.2586 , doi : 10.1109/CCC.2012.43
4. Bafna, Mitali; Barak, Boaz ; Kothari, Pravesh K.; Schramm, Tselil; Steurer, David (2021), "Jugar juegos únicos en expansores de conjuntos pequeños certificados", en Khuller, Samir ; Williams, Virginia Vassilevska (eds.), STOC '21: 53.º Simposio anual ACM SIGACT sobre teoría de la computación, evento virtual, Italia, 21 al 25 de junio de 2021 , Association for Computing Machinery, págs. 1629–1642, arXiv : 2006.09969 , doi : 10.1145/3406325.3451099
5. Feige, Uriel ; Hajiaghayi, Mohammadtaghi ; Lee, James R. (2008), "Algoritmos de aproximación mejorados para separadores de vértices de peso mínimo", SIAM Journal on Computing , 38 (2): 629–657, doi :10.1137/05064299X, MR  2411037
6. Wu, Yu; Austrin, Per; Pitassi, Toniann ; Liu, David (2014), "Inaproximabilidad del ancho del árbol, problemas de diseño relacionados y de diseño en bloque de una sola muestra", Journal of Artificial Intelligence Research , 49 : 569–600, doi : 10.1613/jair.4030 , MR  3195329
7. Manurangsi, Pasin (2018), "Inaproximabilidad de problemas biclique máximos, k -corte mínimo y al menos k -subgrafo más denso a partir de la hipótesis de expansión de conjuntos pequeños", Algorithms , 11 (1): P10:1–P10:22, arXiv : 1705.03581 , doi : 10.3390/a11010010 , MR  3758880
8. Gandhi, Rajiv; Kortsarz, Guy (2015), "Sobre los problemas de expansión de conjuntos y la conjetura de expansión de conjuntos pequeños" (PDF) , Discrete Applied Mathematics , 194 : 93–101, doi :10.1016/j.dam.2015.05.028, MR  3391764
9. Premio Michael y Sheila Held 2018: Prasad Raghavendra y David Steurer, Academia Nacional de Ciencias , consultado el 23 de noviembre de 2023
10. Bansal, Nikhil; Feige, Uriel ; Krauthgamer, Robert; Makarychev, Konstantin; Nagarajan, Viswanath; Naor, Joseph ; Schwartz, Roy (2014), "Particionamiento de grafos min-max y expansión de conjuntos pequeños" (PDF) , SIAM Journal on Computing , 43 (2): 872–904, doi :10.1137/120873996, MR  3504685