Efecto de la conectividad al dividir un gráfico

Question

Tengo un gráfico conectado $G=(V,E)$ , $V$ siendo el conjunto de vértices y $E$ siendo el conjunto de bordes. Parto el gráfico en componentes $C=\{C_1,\dots,C_n\}$ de manera que todos los $C_i$ son disjuntos entre sí.

Toma dos vértices $s,t \in V$ tal que $s,t$ están conectados por un camino. ¿Existe un $O(|V|+|E|)$ para averiguar la lista de todos los $C_i \in C$ tal que si eliminamos los vértices en $C_i$ del gráfico, entonces $s$ se desconectará de $t$ .

Sé que existe la $O(|C|(|V|+|E|))$ algoritmo para hacerlo eliminando vértices en $C_i \in C$ del gráfico para todos los $1\leq i\leq n$ y luego comprobar si $s$ y $t$ están conectados.
Esto puede mejorarse un poco si tomamos todos los pesos de las aristas como 1 y calculamos el camino más corto y luego consideramos sólo los componentes cuyos vértices están presentes en el camino más corto, pero esto sigue teniendo la peor complejidad $O(|C|(|V|+|E|))$ .

Answer 1

Consideremos el problema en el que cada "componente" es un único vértice. Entonces el problema es encontrar cada $s$ - $t$ cutvertex en $O(|E|)$ tiempo, lo cual es bastante fácil (cada uno se encuentra en cada $s$ - $t$ camino).

Puedes usar esto para resolver tu problema en el caso de que cada "componente" sea una componente conectada -no estoy seguro de si querías especificar esto en primer lugar- contrayendo cada componente a un solo vértice a la manera de los menores del gráfico y resolviendo el caso en el que cada componente es un solo vértice.

Si sus componentes no están necesariamente conectados, puede ser más difícil. Tendrías que resolver el caso en el que cada $C_i$ es un conjunto independiente.