Aumento de la conectividad fuerte

El aumento de la conectividad fuerte es un problema computacional en el estudio matemático de los algoritmos de grafos , en el que la entrada es un grafo dirigido y el objetivo del problema es agregar una pequeña cantidad de aristas, o un conjunto de aristas con un peso total pequeño, de manera que las aristas agregadas conviertan el grafo en un grafo fuertemente conectado .

El problema de aumento de conectividad fuerte fue formulado por Kapali Eswaran y Robert Tarjan ( 1976 ) . Demostraron que una versión ponderada del problema es NP-completa, pero el problema no ponderado puede resolverse en tiempo lineal . ^{[ 1 ]} Investigaciones posteriores han considerado la razón de aproximación y la complejidad parametrizada del problema ponderado. ^{[ 2 ] [ 3 ]} 

En el problema de aumento de conectividad fuerte sin ponderación, la entrada es un grafo dirigido y el objetivo es agregarle la menor cantidad posible de aristas para convertir el resultado en un grafo fuertemente conectado. El algoritmo para el caso sin ponderación de Eswaran y Tarjan considera la condensación del grafo dirigido dado, un grafo dirigido acíclico que tiene un vértice por componente fuertemente conectado del grafo dado.${\displaystyle s}$denota el número de vértices fuente en la condensación (componentes fuertemente conectados con al menos una arista saliente pero ninguna arista entrante),${\displaystyle t}$denotamos el número de vértices sumidero en la condensación (componentes fuertemente conectados con aristas entrantes pero sin aristas salientes), y${\displaystyle q}$denotan el número de vértices aislados en la condensación (componentes fuertemente conexas sin aristas entrantes ni salientes), observan que el número de aristas que se deben agregar es necesariamente al menos${\displaystyle \max(s+q,t+q)}$Esto se deduce de que${\displaystyle s+q}$Se deben agregar aristas para proporcionar una arista entrante para cada origen o vértice aislado, y al menos simétricamente${\displaystyle t+q}$Se deben agregar aristas para proporcionar una arista de salida para cada sumidero o vértice aislado. Su algoritmo para el problema encuentra un conjunto de exactamente${\displaystyle \max(s+q,t+q)}$aristas que se añaden al grafo para hacerlo fuertemente conectado. ^{[ 1 ]}

Su algoritmo utiliza una búsqueda en profundidad en la condensación para encontrar una colección de pares de fuentes y sumideros, con las siguientes propiedades: ^{[ 1 ]}

• El origen de cada par puede llegar al destino del par mediante una ruta en el grafo dado.
• Toda fuente que no pertenezca a ninguno de los pares puede alcanzar un sumidero que sí pertenezca a uno de los pares.
• Se puede acceder a cualquier sumidero que no esté en uno de los pares desde una fuente que sí esté en uno de los pares.

Posteriormente se encontró y corrigió un pequeño error en la parte de su algoritmo que encuentra los pares de fuentes y sumideros. ^{[ 4 ]}

Una vez encontrados estos pares, se puede obtener un aumento de conectividad fuerte agregando tres conjuntos de aristas: ^{[ 1 ]}

• El primer conjunto de aristas conecta los pares y los vértices aislados de la condensación en un único ciclo, que consta de una arista por cada par o vértice aislado.
• El segundo conjunto de aristas conecta cada uno de los sumideros restantes con una de las fuentes restantes (elegidas arbitrariamente). Esto vincula tanto la fuente como el sumidero al ciclo de pares y vértices aislados a un costo de una arista por cada par fuente-sumidero.
• Una vez que los dos conjuntos de aristas anteriores hayan agotado todas las fuentes o todos los sumideros, el tercer conjunto de aristas conecta cada fuente o sumidero restante con este ciclo añadiendo una arista más por cada fuente o sumidero.

El número total de aristas en estos tres conjuntos es${\displaystyle \max(s+q,t+q)}$. ^{[ 1 ]}

La versión ponderada del problema, en la que cada arista que se puede agregar tiene un peso dado y el objetivo es elegir un conjunto de aristas agregadas de peso mínimo que haga que el grafo dado sea fuertemente conectado, es NP-completa. [ ^{1 ] Frederickson} y Ja'Ja ' (1981) proporcionaron un algoritmo de aproximación con una razón de aproximación de 2. ^{[ 2 ]} Una versión parametrizada y ponderada del problema, en la que se debe agregar como máximo${\displaystyle k}$Las aristas de peso total mínimo para que el grafo dado esté fuertemente conectado, son tratables con parámetros fijos . ^{[ 3 ]}

Si una cuadrícula cuadrada está formada por varillas rígidas (los bordes de la cuadrícula) conectadas entre sí mediante articulaciones flexibles en los bordes, la estructura puede deformarse de diversas maneras en lugar de permanecer cuadrada. El problema del arriostramiento de cuadrículas plantea cómo estabilizar dicha estructura añadiendo arriostramiento transversal adicional en algunos de sus cuadrados. Este problema puede modelarse mediante la teoría de grafos , creando un grafo bipartito con un vértice por cada fila o columna de cuadrados en la cuadrícula, y una arista entre dos de estos vértices cuando un cuadrado en una fila y columna determinada está arriostrado transversalmente. Si el arriostramiento transversal dentro de cada cuadrado lo hace completamente rígido, entonces este grafo es no dirigido y representa una estructura rígida si y solo si es un grafo conexo . ^{[ 5 ]} Sin embargo, si los cuadrados están arriostrados solo parcialmente (por ejemplo, conectando dos esquinas opuestas mediante una cuerda o alambre que impide el movimiento expansivo pero no el contractivo), entonces el grafo es dirigido y representa una estructura rígida si y solo si es un grafo fuertemente conexo. ^{[ 6 ]}

Un problema asociado de aumento de conectividad fuerte plantea cómo agregar más refuerzos parciales a una cuadrícula que ya los tiene en algunos de sus cuadrados. Los refuerzos parciales existentes se pueden representar como un grafo dirigido, y los refuerzos parciales adicionales que se agreguen deben formar un aumento de conectividad fuerte de ese grafo. Para poder traducir una solución del problema de aumento de conectividad fuerte a una solución del problema de refuerzo original, se requiere una restricción adicional: cada arista agregada debe respetar la bipartición del grafo original y solo conectar vértices de fila con vértices de columna, en lugar de intentar conectar filas con filas o columnas con columnas. Esta versión restringida del problema de aumento de conectividad fuerte se puede resolver nuevamente en tiempo lineal. ^{[ 7 ]}