Algorithm to create "approximate" or "simplified" graph? I would like to create an 'approximate' or 'simplified' graph $G'$ from a source graph $G$.

*

*Tag a subset of the vertices of $G$ as 'special'

*Copy them to $G'$

*Each pair of vertices of $G'$ have an edge between them only if there is a path between them in $G$ that does not go through any other special vertices of $G$
Is there an algorithm to do this quickly?
Or just brute force the algorithm described above?
(I'm sorry for the layperson's terminology. Part of the reason I ask the question is because I don't know the technical jargon to search for!)
 A: First, consider the subgraph with only "non-special vertices", and find its connected components (call these $C_1, C_2, \dots, C_k$). This can be done quickly using, say, depth-first search.
If there is a path between two special vertices using only non-special vertices, then the interior of that path stays entirely with some connected component $C_i$. (Conversely, if two special vertices have neighbors in the same $C_i$, then there is a path between them through $C_i$.) So to find which of these paths exist, we do two things:

*

*For each $i$, compute $S_i$, the set of special vertices with a neighbor in $C_i$. (Computationally, this is easier to do in reverse: for each special vertex $v$, look at each of its neighbors, and if that neighbor is in $C_i$ for some $i$, add $v$ to $S_i$.)

*Now we are ready to build the simplified graph. For $i=1, 2, \dots, k$, the simplified graph should have an edge between every pair of vertices in $S_i$: in other words, it should have a clique whose vertex set is $S_i$.

For the most part, the simplified graph will be the union of these cliques, with one exception: if two special vertices have an edge between them in $G$, they should still have an edge between them in the simplified graph. (We can detect these edges in the process of computing $S_1, \dots, S_k$.)
