Límites Inferiores Ajustados para la Esparcificación de Corte Direccionado y el Corte Mínimo Distribuido

En este artículo, consideramos dos problemas fundamentales de aproximación de corte en grandes grafos. Demostramos nuevos límites inferiores para ambos problemas que son óptimos hasta factores logarítmicos. El primer problema es aproximar cortes en grafos dirigidos balanceados. En este problema, queremos construir una estructura de datos que pueda proporcionar una aproximación de (1 ± ε) de los valores de corte en un grafo con n vértices. Para grafos dirigidos arbitrarios, tal estructura de datos requiere Ω(n²) bits incluso para ε constante. Para sortear esto, trabajos recientes estudian grafos β-balanceados, lo que significa que para cada corte dirigido, el peso total de las aristas en una dirección es como máximo β veces el peso total en la otra dirección. Consideramos el modelo 'for-each', donde el objetivo es aproximar cada corte con probabilidad constante, y el modelo 'for-all', donde todos los cortes deben ser preservados simultáneamente. Mejoramos el anterior límite inferior Ømega(n √β/ε) en el modelo 'for-each' a ~Ω(n √β/ε) y mejoramos el anterior límite inferior Ω(n β/ε) en el modelo 'for-all' a Ω(n β/ε²). Esto resuelve las principales preguntas abiertas de (Cen et al., ICALP, 2021). El segundo problema es aproximar el corte mínimo global en un modelo de consulta local, donde solo podemos acceder al grafo a través de consultas de grado, arista y adyacencia. Proporcionamos un límite inferior ΩL(min m, m/ε² k R) para este problema, que mejora el anterior límite inferior ΩL(m/k R), donde m es el número de aristas, k es el tamaño mínimo del corte, y buscamos una aproximación de (1+ε). Además, mostramos que los límites superiores existentes con ligeras modificaciones coinciden con nuestro límite inferior hasta factores logarítmicos.