Let $G=(V,E)$ be an undirected graph and $A,B,C\subset V$ disjoint subsets of $V$. I want to check whether or not $A$ and $B$ are separated by $C$ (i.e. every path from $A$ to $B$ passes through $C$). There are several ways to check this (via graph connectivity, DFS, brute force search over all paths, etc.).
My question is: What is the optimal computational complexity of this problem?
The actual complexity might depend on the specific input representation. A reasonable representation uses adjacency lists for the graph and lists the elements in $A$,$B$,and $C$ explicitly in any order.
Assuming this input representation you can solve your problem in linear time and is asymptotically optimal.
Simply add a new vertex $s$ and all edges $(s,a)$ for $a \in A$. Then run a breadth first search from $s$ on the resulting graph while ignoring vertices in $C$ and check whether any of the reached vertices in in $B$. This requires time $O(|V|+|E|)$.
To see that this is optimal notice that you need to spend $\Omega(|V|)$ time even when $G=(\{1,\dots,n\}, \{(1,2), (2,3)\})$, $A=\{1\}$, and $B=\{3\}$ since this amounts to checking whether $2 \in C$ and you can have $|C|=\Theta(n)$. You also need to spend $\Omega(|E|)$ time just to decide whether two vertices $a$, $b$ are connected in $G$ when $C=\emptyset$. Indeed if you spend $o(|E|)$ time then there is at least one edge from the input that is not examined and that edge might the only bridge between the connected component containing $a$ and the connected component containing $b$.
