Algoritmos de Aproximación $O(\log n)$ para la Razón de Bipartidez

Información Básica

• ID del Artículo: 2507.12847
• Título: Algoritmos de Aproximación $O(\log n)$ para la Razón de Bipartidez
• Autores: Tasuku Soma (The Institute of Statistical Mathematics & RIKEN AIP), Mingquan Ye (National Institute of Informatics & University of California, Santa Cruz), Yuichi Yoshida (National Institute of Informatics)
• Clasificación: cs.DS (Estructuras de Datos y Algoritmos)
• Fecha de Publicación: 5 de noviembre de 2025 (arXiv v2)
• Enlace del Artículo: https://arxiv.org/abs/2507.12847

Resumen

Este artículo propone el primer algoritmo de aproximación $O(\log n)$ para la razón de bipartidez (bipartiteness ratio) en grafos no dirigidos, donde $n$ es el número de vértices. El método extiende el marco de juego corte-emparejamiento del corte más disperso (sparsest cut) al problema de razón de bipartidez, requiriendo solo $\text{polylog } n$ cálculos de flujo máximo no dirigido de una sola mercancía. Combinado con los algoritmos de flujo máximo no dirigido más rápidos actuales, se logra complejidad de tiempo casi lineal. La investigación introduce el concepto de buena conectividad (well-linkedness) para grafos parcialmente simétricos y prueba una nueva caracterización de la razón de bipartidez en términos de buena conectividad en grafos auxiliares parcialmente simétricos. Como aplicación, se propone un algoritmo de corte mínimo no cortado (minimum uncut) con tiempo $\tilde{O}(mn)$. Además, se define la razón de bipartidez dirigida y se proporciona un algoritmo de aproximación $O(\log n)$ mediante incrustación de estilo Leighton-Rao dirigida.

Contexto de Investigación y Motivación

Definición del Problema

El problema de razón de bipartidez fue introducido por Trevisan Tre12 como un problema de optimización en teoría de grafos. Para un grafo no dirigido $G=(V,E,w)$, se define: $\beta(G) := \min_{x\in\{0,\pm1\}^V\setminus\{0\}} \frac{\sum_{e=(i,j)\in E} w(e)\cdot|x_i+x_j|}{\sum_{i\in V} \deg(i)\cdot|x_i|}$

Esta razón caracteriza la desviación del grafo respecto a ser bipartito: $\beta(G)=0$ si y solo si $G$ es bipartito.

Importancia de la Investigación

1. Significado Teórico: La razón de bipartidez es un concepto central en la desigualdad de Cheeger dual, estrechamente relacionada con el valor propio máximo $\lambda_n$ de la matriz laplaciana normalizada: $\frac{2-\lambda_n}{2} \leq \beta(G) \leq \sqrt{2(2-\lambda_n)}$
2. Valor de Aplicación:
   • Diseño de algoritmos espectrales: Trevisan utilizó esta desigualdad para diseñar algoritmos espectrales puros para corte máximo
   • Análisis de redes: Aplicaciones en agrupamiento de grafos con signo, detección de comunidades, etc. XOG20; AL20; NP22
   • Optimización combinatoria: Estrecha relación con problemas clásicos como corte máximo y corte mínimo no cortado

Limitaciones de Métodos Existentes

1. Ausencia de Algoritmos de Aproximación: Aunque existen algoritmos de aproximación maduros para desigualdad de Cheeger y corte más disperso (como aproximación $O(\sqrt{\log n})$), la razón de bipartidez no tenía ningún algoritmo de aproximación en tiempo polinómico anterior a este trabajo
2. Insuficiencia de Métodos Espectrales: Los métodos espectrales existentes (basados en vectores propios) solo proporcionan cotas teóricas y no pueden resolver directamente el problema de optimización
3. Diferencias con Corte Más Disperso: Aunque la razón de bipartidez tiene forma similar al corte más disperso, sus restricciones (estructura de tripartición) hacen que la aplicación directa de técnicas existentes sea desafiante

Motivación de la Investigación

Llenar el vacío en algoritmos de aproximación para la razón de bipartidez, proporcionando nuevas herramientas algorítmicas para teoría espectral de grafos y optimización combinatoria.

Contribuciones Principales

1. Primer Algoritmo de Aproximación: Se propone el primer algoritmo de aproximación $O(\log n)$ para la razón de bipartidez $b$, con complejidad de tiempo $\tilde{O}(\min\{b(V),n^2\}+m)$
2. Innovaciones Teóricas:
   • Introducción del concepto de buena conectividad (well-linkedness) para grafos parcialmente simétricos
   • Prueba de caracterización equivalente de la razón de bipartidez en términos de buena conectividad del grafo auxiliar $G'$ (Teorema 3.5)
   • Extensión del marco de juego corte-emparejamiento desde corte más disperso a razón de bipartidez
3. Aplicación de Corte Mínimo No Cortado: Diseño de algoritmo con tiempo $\tilde{O}(mn)$ que, para grafos con razón de corte mínimo no cortado $\eta$, encuentra un corte con razón de corte no cortado $O(\log n\log(1/\eta))\cdot\eta$
4. Extensión Dirigida:
   • Definición de razón de bipartidez dirigida y su caracterización mediante funciones submodulares pequeñas
   • Implementación de aproximación $O(\log n)$ mediante incrustación $\ell_1$ dirigida
   • Provisión de algoritmo de corte mínimo no cortado dirigido

Explicación Detallada del Método

Definición de la Tarea

Razón de bipartidez $b$: Dado un grafo no dirigido $G=(V,E,w)$ y pesos de vértice positivos $b:V\to\mathbb{Z}_{++}$, se define: $\beta_b(G) := \min_{x\in\{0,\pm1\}^V\setminus\{0\}} \beta_b(x), \quad \beta_b(x) := \frac{\sum_{(i,j)\in E} w(i,j)\cdot|x_i+x_j|}{\sum_{i\in V} b(i)\cdot|x_i|}$

Entrada: Grafo $G$, pesos de arista $w$, pesos de vértice $b$, parámetro $r>0$
Salida: Vector $x\in\{0,\pm1\}^V$ tal que $\beta_b(x)\leq O(\log n)\cdot\beta_b(G)$

Marco Técnico Principal

1. Construcción del Grafo Auxiliar

Se construye un grafo bipartito parcialmente simétrico $G'=(V^+\cup V^-,E')$:

• $V^+,V^-$ son dos copias disjuntas de $V$
• Para cada arista $(i,j)\in E$, se añaden aristas $(i^+,j^-)$ y $(i^-,j^+)$ a $E'$
• Se heredan los pesos de arista y vértice

Propiedad Clave (Lema 3.2): Para cualquier $x\in\{0,\pm1\}^V$ correspondiente a una tripartición $(L,R,Z)$, sea $S=L^+\cup R^-$, entonces: $\beta_b(x) = \frac{w(E'(S,\bar{S}))}{b(S)}$

Por lo tanto: $\beta_b(G) = \min_{S=L^+\cup R^-, \text{ disjuntos }L,R\subseteq V} \frac{w(E'(S,\bar{S}))}{b(S)}$

2. Caracterización de Buena Conectividad

Definición (Pares de fuente-sumidero simétricos): Un par $(A,B)$ se llama simétrico si existen $L,R\subseteq V$ disjuntos tales que: $A = L^+\cup R^-, \quad B = L^-\cup R^+$

Definición 3.3 (Buena Conectividad): Un par simétrico $(A,B)$ se llama $r$-bien conectado si en la red auxiliar $\mathcal{N}_{A,B,r}$ existe un flujo saturado de $s^+$ a $s^-$, donde:

• Capacidades de arista: la capacidad de $s^+$ a cada vértice $u$ en $A$ es $b(u)$; similar para $B$ a $s^-$
• Capacidad de arista $e$ en $E'$ es $w(e)/r$

$G'$ se llama $r$-bien conectado si todos los pares simétricos son $r$-bien conectados.

Teorema 3.5 (Caracterización Principal): $\beta_b(G)\geq r$ si y solo si $G'$ es $r$-bien conectado.

Esquema de Prueba:

• (⇒) Si $\beta_b(G)\geq r$, entonces para cualquier par simétrico $(A,B)$, el valor del corte mínimo $s^+$-$s^-$ es $\geq b(A)$, por el teorema de flujo máximo-corte mínimo existe un flujo saturado
• (⇐) Si existe un par simétrico $(A,B)$ que no es $r$-bien conectado, entonces el conjunto consistente $S$ correspondiente al corte mínimo satisface $w(E'(S,\bar{S}))/b(S)<r$

3. Juego Corte-Emparejamiento

Marco del Juego (Algoritmo 1):

• Mantenimiento: Matriz de densidad MMWU $X_t$, multigrafo vacío $H$
• Cada Ronda:
  1. Jugador Corte: Calcula descomposición de Gram (aproximada) de $D_b^{-1/2}X_tD_b^{-1/2}$ como $\{v_i\}$
  2. Muestrea vector gaussiano $g\sim\mathcal{N}(0,I_n)$, calcula $\tilde{v}_i=\langle g,v_i\rangle$
  3. Sea $L'=\{i:\tilde{v}_i>0\}$, $R'=\{i:\tilde{v}_i<0\}$, toma el más grande como $L$, establece $(A,B)$ como el par simétrico correspondiente
  4. Verificación: Si $(A,B)$ no es $r$-bien conectado, devuelve $x$ correspondiente al corte mínimo
  5. Jugador Emparejamiento: En caso contrario, encuentra flujo saturado, lo descompone en multiconjunto de caminos $\mathcal{P}_t$, el grafo de demanda es $M_t$
  6. Actualiza $F_t = D_b^{-1/2}(D_{M_t}+A_{M_t})D_b^{-1/2}$, realiza actualización MMWU
• Terminación: Después de $T=O(\log^2 n)$ rondas, devuelve $H=M_1\oplus\cdots\oplus M_T$

Análisis Clave:

1. Amplitud: $F_t\preceq 4I$ (prueba en lema)
2. Ganancia: $\langle F_t,X_t\rangle = \sum_{(i,j)\in M_t}\|v_i+v_j\|^2 \geq \Omega(1/\log n)$ (mediante proyección gaussiana)
3. Cota MMWU (Lema 3.7): $\lambda_{\min}\left(\sum_{t=1}^T F_t\right) \geq (1-\rho\delta)\sum_{t=1}^T\langle F_t,X_t\rangle - \frac{\ln n}{\delta}$
   Tomando $\delta=O(1)$, $T=O(\log^2 n)$, se obtiene $\lambda_{\min}\geq\Omega(\log n)$
4. Certificado: El Lema 3.9 prueba que $\beta_b(H)=\Omega(\log n)$, como $H$ puede incrustarse con congestión $O(T)$ en $G$, se obtiene $\beta_b(G)=\Omega(r/\log n)$

Puntos de Innovación Técnica

1. Explotación de Simetría Parcial: Mediante la estructura parcialmente simétrica del grafo auxiliar $G'$, se transforma el problema de tripartición en un problema de flujo de pares fuente-sumidero simétricos, esta es la reconstrucción de problema clave
2. Lema de Corte Consistente (Lema 3.4): Utilizando simetría parcial y Lema 2.5, se prueba que siempre se puede encontrar un corte mínimo consistente, simplificando el análisis
3. Técnica de Proyección Gaussiana:
   • Proyecta descomposición de Gram de alta dimensión a una dimensión, manteniendo aproximación de $\|v_i+v_j\|$ (Ecuación 3.6)
   • El Lema 3.8 utiliza la cota de Laurent-Massart para garantizar que $\sum b(i)|\tilde{v}_i|^2\geq 1/2$ se cumple con probabilidad constante
4. Descomposición de Gram Rápida (Lema 3.11): Mediante reducción de dimensión JL y expansión de Taylor truncada, se reduce la descomposición exacta de $O(n^3)$ a $\tilde{O}(\min\{b(V),n^2\})$

Configuración Experimental

Algoritmo Teórico, Sin Sección de Experimentos

Este artículo es un artículo de algoritmo puramente teórico, con contribuciones principales en:

1. Garantías teóricas: razón de aproximación $O(\log n)$
2. Análisis de complejidad de tiempo: $\tilde{O}(m)$ para razón de bipartidez original
3. Comparación teórica con métodos existentes (Tabla 1)

Resultados Experimentales

Resumen de Resultados Teóricos

Teorema Principal (Teorema 3.12):

• Razón de Aproximación: $O(\log n)$
• Complejidad de Tiempo:
  • $O(\log^3 n\cdot\max\{\log^2 n,\log b(V)\}\cdot\min\{b(V),n^2\})$ operaciones aritméticas
  • $O(\log^2 n)$ cálculos de flujo máximo de una sola mercancía
• Probabilidad de Éxito: $\geq 1-1/\text{poly}(n)$

Aplicación de Corte Mínimo No Cortado (Teorema 4.1):

• Entrada: Grafo con razón de corte mínimo no cortado $\eta$
• Salida: Corte con razón de corte no cortado $\leq O(\log n\log(1/\eta))\cdot\eta$
• Tiempo: $\tilde{O}(mn)$

Análisis Comparativo (Tabla 1):

Ventajas:

• Comparado con métodos espectrales Tre12, KLLO+13: no depende de valores propios, razón de aproximación superior
• Comparado con métodos SDP GVY93, ACMM05: aunque la razón de aproximación es ligeramente más débil, el tiempo se reduce de $\tilde{O}(m^\omega)$ a $\tilde{O}(mn)$ ($\omega\approx 2.37$)

Extensión a Grafos Dirigidos

Razón de Bipartidez Dirigida (Ecuación 1.3): $\beta_b(x) = \frac{\sum_{(i,j)\in E}\psi_{ij}(x)}{\sum_i b(i)|x_i|}, \quad \psi_{ij}(x)=\begin{cases}|x_i+x_j| & x_i\geq x_j\\ |x_i|+|x_j| & \text{en otro caso}\end{cases}$

Teorema 1.3: Algoritmo de aproximación $O(\log n)$ en tiempo polinómico, mediante:

1. Construcción de grafo auxiliar parcialmente simétrico pequeño $G'$
2. Resolución de relajación de semimétrica dirigida (PL)
3. Incrustación débil $\ell_1$ dirigida CMM06 para lograr aproximación $O(\log|V'|)=O(\log n)$

Teorema 1.4: Aproximación $O(\log n\log(1/\eta))\cdot\eta$ para corte mínimo no cortado dirigido

Trabajo Relacionado

Teoría Espectral de Grafos

1. Desigualdad de Cheeger AM85; Alo86: Relaciona el segundo valor propio más pequeño $\lambda_2$ con la conductancia $\phi(G)$: $\frac{\lambda_2}{2}\leq\phi(G)\leq\sqrt{2\lambda_2}$
2. Desigualdad de Cheeger Dual Tre12; BJ13: Relación entre la razón de bipartidez estudiada en este trabajo y el valor propio máximo $\lambda_n$
3. Métodos Espectrales de Orden Superior KLLO+13; GS11: Utilización de múltiples valores propios para mejorar aproximación

Algoritmos de Corte Más Disperso

1. Métodos Combinatorios:
   • Juego corte-emparejamiento KRV06: $O(\log^2 n)$
   • Mejora OSVV08: $O(\log n)$
   • Óptimo AK16: $O(\sqrt{\log n})$ mediante MMWU
2. Método SDP ARV09: $O(\sqrt{\log n})$ mediante incrustación de métrica
3. Grafos Dirigidos Lou10; LTW24: Aproximación $O(\log n)$ para corte más disperso dirigido

Corte Máximo/Corte Mínimo No Cortado

1. Algoritmos de Aproximación:
   • Algoritmo GW GW94: Aproximación $0.878$ (SDP)
   • Método espectral Tre12; KLLO+13: Depende de valores propios
   • Jerarquía SDP GS11; ACMM05: Más fuerte pero más lento
2. Contribución de Este Trabajo: Primera aplicación del juego corte-emparejamiento a razón de bipartidez, logrando tiempo casi lineal

Conclusiones y Discusión

Conclusiones Principales

1. Primera provisión de algoritmo de aproximación en tiempo polinómico $O(\log n)$ para razón de bipartidez
2. Introducción de buena conectividad para grafos parcialmente simétricos, establecimiento de nueva caracterización flujo-corte
3. Logro de tiempo casi lineal $\tilde{O}(m)$, mejora significativa sobre métodos SDP
4. Extensión exitosa a grafos dirigidos, provisión de marco unificado

Limitaciones

1. Razón de Aproximación: $O(\log n)$ más débil que $O(\sqrt{\log n})$ de SDP ARV09; ACMM05
2. Corte Mínimo No Cortado: Factor adicional $\log(1/\eta)$, brecha comparado con $O(\sqrt{\log n})\cdot\eta$ de ACMM05
3. Tiempo de Grafos Dirigidos: Versión dirigida aún requiere tiempo polinómico (no alcanza tiempo casi lineal), depende de resolución de PL
4. Rendimiento Práctico: Resultados puramente teóricos, sin verificación experimental

Direcciones Futuras

1. Mejora de Razón de Aproximación: ¿Puede alcanzarse $O(\sqrt{\log n})$ manteniendo tiempo casi lineal?
2. Aceleración de Grafos Dirigidos: ¿Puede la aproximación de razón de bipartidez dirigida también reducirse a tiempo $\tilde{O}(m)$?
3. Cotas Inferiores: ¿Es $O(\log n)$ una cota inherente de métodos basados en flujo?
4. Aplicaciones Prácticas: Investigación empírica en análisis de redes y detección de comunidades

Evaluación Profunda

Fortalezas

1. Avance Teórico:
   • Resolución de problema abierto de larga data (sin algoritmos de aproximación desde 2012)
   • Primera caracterización equivalente de razón de bipartidez con buena conectividad (Teorema 3.5)
   • Unificación elegante de casos no dirigido y dirigido
2. Innovación Técnica:
   • Explotación de Simetría Parcial: Construcción de grafo auxiliar ingeniosa que transforma tripartición en problema de flujo simétrico
   • Análisis MMWU: Aplicación creativa del marco de AK16 a nuevo problema, técnica de proyección gaussiana para manejar descomposición de Gram
   • Implementación Rápida: Descomposición de Gram aproximada del Lema 3.11 evita cuello de botella $O(n^3)$
3. Eficiencia Algorítmica:
   • Complejidad de tiempo $\tilde{O}(m)$ cercana a óptimo (requiere lectura del grafo)
   • Solo requiere flujo de una sola mercancía, puede utilizar algoritmos de tiempo casi lineal recientes CKLP+22
   • Mejora de orden de magnitud comparado con métodos SDP ($\tilde{O}(m^\omega)$)
4. Completitud Teórica:
   • Análisis probabilístico riguroso (Lema 3.8 utiliza cota de Laurent-Massart)
   • Desglose detallado de complejidad de tiempo
   • Extensión dirigida demuestra generalidad del marco

Deficiencias

1. Brecha en Razón de Aproximación:
   • $O(\log n)$ vs. $O(\sqrt{\log n})$ ARV09: Aunque aceptable, no es óptimo
   • No se discute si es posible mejora (por ejemplo, mediante relajación SDP más fuerte)
2. Ausencia de Experimentos:
   • Sin evaluación de rendimiento en grafos reales
   • Sin comparación de factores constantes (las constantes ocultas en O grande pueden ser grandes)
   • Falta de comparación empírica con métodos espectrales
3. Grafos Dirigidos Incompletamente Resueltos:
   • Complejidad de tiempo de versión dirigida no explícita (Teorema 1.3 solo dice "tiempo polinómico")
   • Requiere resolución de PL, posiblemente más lento que caso no dirigido
   • No se discute si es posible alcanzar $\tilde{O}(m)$
4. Detalles Técnicos:
   • Prueba del Lema 3.11 en apéndice, texto principal carece de intuición
   • Proyección gaussiana requiere $O(\log n)$ remuestreos (Lema 3.8), puede afectar rendimiento práctico
   • Selección de paso MMWU $\delta$ carece de orientación
5. Limitaciones de Aplicación:
   • Factor adicional $\log(1/\eta)$ en corte mínimo no cortado puede ser significativo cuando $\eta$ es muy pequeño
   • No se discute significado práctico de versión ponderada ($b$ arbitrario)

Impacto

1. Contribución Teórica:
   • Proporciona nueva perspectiva algorítmica para teoría espectral de grafos
   • Concepto de buena conectividad para grafos parcialmente simétricos puede tener valor independiente
   • Demuestra aplicabilidad más amplia del juego corte-emparejamiento
2. Impacto Técnico:
   • Paradigma MMWU + proyección gaussiana puede aplicarse a otros problemas de razón
   • Técnica de descomposición de Gram rápida (Lema 3.11) reutilizable
3. Valor Práctico:
   • Tiempo casi lineal hace procesamiento de grafos a gran escala viable
   • Puede promover aplicaciones de razón de bipartidez en análisis de redes
   • Versión dirigida proporciona herramienta para detección de comunidades en grafos dirigidos
4. Problemas Abiertos:
   • Inspira investigación para mejorar razón de aproximación
   • Problema de aceleración de grafos dirigidos tiene valor claro

Escenarios Aplicables

1. Análisis de Grafos a Gran Escala:
   • Detección de cuasi-bipartidez en redes sociales
   • Análisis de estructura de grafo usuario-artículo en sistemas de recomendación
2. Agrupamiento Espectral:
   • Como método de agrupamiento basado en valor propio máximo
   • Detección de comunidades en grafos con signo XOG20; NP22
3. Optimización Combinatoria:
   • Preprocesamiento para corte máximo (mediante bisección recursiva)
   • Heurísticas para problemas de partición de grafos
4. Investigación Teórica:
   • Punto de referencia para aproximación de parámetros de grafos
   • Nueva perspectiva sobre dualidad flujo-corte

No Aplicable: Escenarios que requieren aproximación óptima $O(\sqrt{\log n})$ (utilizar método SDP)

Referencias (Seleccionadas)

1. Tre12 L. Trevisan. "Max cut and the smallest eigenvalue". SIAM J. Comput. 41.6 (2012): Define razón de bipartidez, prueba desigualdad de Cheeger dual
2. KRV06 R. Khandekar, S. Rao, U. Vazirani. "Graph partitioning using single commodity flows". STOC 2006: Propone juego corte-emparejamiento
3. AK16 S. Arora, S. Kale. "A combinatorial, primal-dual approach to semidefinite programs". J. ACM 63.2 (2016): Marco MMWU, base técnica principal de este trabajo
4. ACMM05 A. Agarwal et al. "$O(\sqrt{\log n})$ approximation algorithms for min uncut...". STOC 2005: Método SDP para corte mínimo no cortado, comparación principal de este trabajo
5. CKLP+22 L. Chen et al. "Maximum flow and minimum-cost flow in almost-linear time". FOCS 2022: Flujo máximo en tiempo casi lineal, hace eficiente el algoritmo de este trabajo

Evaluación General: Este es un artículo de algoritmo teórico de alta calidad que resuelve un problema abierto de larga data, con innovación técnica significativa (caracterización de grafo parcialmente simétrico, extensión MMWU), logrando complejidad de tiempo casi lineal. Las deficiencias principales radican en que la razón de aproximación no alcanza lo óptimo y carece de verificación experimental. Tiene contribución importante para la comunidad de ciencias de la computación teórica, posiblemente iniciando investigación sobre aplicaciones prácticas de razón de bipartidez. Se recomienda publicación en conferencia de primer nivel (nivel FOCS/SODA).