Fuerte aumento de conectividad

El aumento de conectividad fuerte es un problema computacional en el estudio matemático de algoritmos de gráficos , en el que la entrada es un gráfico 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 modo que los bordes añadidos convierten el gráfico en un gráfico fuertemente conectado .

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

Versión no ponderada

En el problema de aumento de conectividad fuerte no ponderado, la entrada es un gráfico dirigido y el objetivo es agregarle la menor cantidad posible de bordes para convertir el resultado en un gráfico fuertemente conectado. El algoritmo para el caso no ponderado de Eswaran y Tarjan considera la condensación del grafo dirigido dado, un grafo acíclico dirigido que tiene un vértice por componente fuertemente conectado del grafo dado. Dejar denotar el número de vértices de origen en la condensación (componentes fuertemente conectados con al menos un borde saliente pero sin bordes entrantes), denotar el número de vértices sumideros en la condensación (componentes fuertemente conectados con bordes entrantes pero sin bordes salientes), y${\displaystyle s}$${\displaystyle t}$${\displaystyle q}$denotan el número de vértices aislados en la condensación (componentes fuertemente conectados sin bordes entrantes ni salientes), observan que el número de bordes a agregar es necesariamente al menos . Esto se debe a que es necesario agregar bordes para proporcionar un borde entrante para cada fuente o vértice aislado, y simétricamente al menos es necesario agregar bordes para proporcionar un borde saliente para cada sumidero o vértice aislado. Su algoritmo para el problema encuentra un conjunto de bordes exactos para agregar al gráfico para que esté fuertemente conectado. ^[1]${\displaystyle \max(s+q,t+q)}$${\displaystyle s+q}$${\displaystyle t+q}$${\displaystyle \max(s+q,t+q)}$

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]

• La fuente de cada par puede llegar al sumidero del par por una ruta en el gráfico dado.
• Toda fuente que no esté en uno de los pares puede llegar a un sumidero en uno de los pares.
• Cada sumidero que no esté en uno de los pares se puede acceder desde una fuente en uno de los pares.

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

Una vez que se han encontrado estos pares, se puede obtener un fuerte aumento de la conectividad agregando tres conjuntos de bordes: ^[1]

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

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

Versión ponderada y parametrizada

La versión ponderada del problema, en la que cada borde que podría agregarse tiene un peso determinado y el objetivo es elegir un conjunto de bordes adicionales de peso mínimo que haga que el gráfico dado esté fuertemente conectado, es NP-completo. ^[1] Un algoritmo de aproximación con relación aproximación 2 fue proporcionado por Frederickson y Ja'Ja'(1981) . ^[2] Una versión parametrizada y ponderada del problema, en la que uno debe agregar como máximo los bordes del peso total mínimo para hacer que el gráfico dado esté fuertemente conectado, es manejable con parámetros fijos . ^[3]${\displaystyle k}$

Versión bipartita y aplicación de refuerzo de rejilla

Si una cuadrícula cuadrada está hecha de varillas rígidas (los bordes de la cuadrícula) conectadas entre sí por juntas flexibles en los bordes de la cuadrícula, entonces la estructura general se puede doblar de muchas maneras en lugar de permanecer cuadrada. El problema del arriostramiento de la rejilla pregunta cómo estabilizar dicha estructura agregando arriostramientos transversales adicionales dentro de algunos de sus cuadrados. Este problema se puede modelar usando la teoría de grafos, haciendo un gráfico bipartito con un vértice para cada fila o columna de cuadrados en la cuadrícula, y un borde entre dos de estos vértices cuando un cuadrado en una fila y columna dadas se cruza entre corchetes. Si el refuerzo transversal dentro de cada cuadrado lo hace completamente rígido, entonces este gráfico no está dirigido y representa una estructura rígida si y solo si es ungráfico conectado . ^[5] Sin embargo, si los cuadrados están solo parcialmente arriostrados (por ejemplo, conectando dos esquinas opuestas con una cuerda o alambre que previene el movimiento expansivo pero no evita el movimiento contractivo), entonces el gráfico está dirigido y representa una estructura rígida si y solo si es un gráfico fuertemente conectado. ^[6]

Un fuerte problema de aumento de conectividad asociado pregunta cómo agregar más arriostramientos parciales a una cuadrícula que ya tiene arriostramientos parciales en algunos de sus cuadrados. El arriostramiento parcial existente se puede representar como un gráfico dirigido, y el arriostramiento parcial adicional que se agregará debe formar un fuerte aumento de conectividad de ese gráfico. Para poder traducir una solución al fuerte problema de aumento de conectividad a una solución del problema de arriostramiento original, se requiere una restricción adicional: cada borde agregado debe respetar la bipartición del gráfico original y solo conectar los vértices de fila con la columna. vértices en lugar de intentar conectar filas a filas o columnas a columnas. Esta versión restringida del fuerte problema de aumento de la conectividad puede resolverse nuevamente en tiempo lineal. ^[7]

Referencias

1. Eswaran, Kapali P .; Tarjan, R. Endre (1976), "Problemas de aumento", SIAM Journal on Computing , 5 (4): 653–665, doi : 10.1137 / 0205044 , MR  0449011
2. Frederickson, Greg N .; Ja'Ja ', Joseph (1981), "Algoritmos de aproximación para varios problemas de aumento de gráficos", SIAM Journal on Computing , 10 (2): 270-283, doi : 10.1137 / 0210019 , MR 0615218 
3. Klinkby, Kristine Vitting; Misra, Pranabendu; Saurabh, Saket (enero de 2021), "El aumento de conectividad fuerte es FPT", Actas del Simposio ACM-SIAM sobre algoritmos discretos (SODA) de 2021 , Society for Industrial and Applied Mathematics, págs. 219-234, doi : 10.1137 / 1.9781611976465. 15
4. Raghavan, S. (2005), "Una nota sobre el algoritmo de Eswaran y Tarjan para el problema de aumento de conectividad fuerte", en Golden, Bruce; Raghavan, S .; Wasil, Edward (eds.), The Next Wave in Computing, Optimization, and Decision Technologies , Operations Research / Computer Science Interfaces Series, 29 , Springer, págs. 19-26, doi : 10.1007 / 0-387-23529-9_2
5. Graver, Jack E. (2001), "2.6 La solución al problema de la cuadrícula", Contando con marcos: Matemáticas para ayudar al diseño de estructuras rígidas , The Dolciani Mathematical Expositions, 25 , Washington, DC: Asociación Matemática de América, págs. . 50–55, ISBN 0-88385-331-0, MR  1843781
6. Baglivo, Jenny A .; Graver, Jack E. (1983), "3.10 Estructuras de arriostramiento", Incidencia y simetría en el diseño y la arquitectura , Cambridge Urban and Architectural Studies, Cambridge University Press, págs. 76–88, ISBN 9780521297844
7. Gabow, Harold N .; Jordán, Tibor (2000), "Cómo hacer rígido un entramado de rejilla cuadrada con cables", SIAM Journal on Computing , 30 (2): 649–680, doi : 10.1137 / S0097539798347189 , MR 1769375