# Removing vertices that belong to a given set from a graph

If I'm given a graph $G$ with the set of vertices $V$ and a set $B \subseteq V$, can I remove all the vertices $\in B$ from $G$, as well as all edges that connect any other vertex to a vertex $\in B$ in linear time ($O(V + E)$)? It can be assumed that checking if a vertex $\in B$ is $O(1)$.

My thoughts on this are- If I represent $G$ as an adjacency list, this is not possible as I'd have to loop over all vertices and the vertices that they're connected to. So worst case would be $O(n^2)$.

In case I have an adjacency matrix, I feel like this would be possible in $O(n)$ as I could zero out the entire row and column of the vertices in $B$. However, actually getting rid of the vertices themselves would require shifting elements of the array so overall $O(n^2)$.

My end goal is to be able to perform graph traversals (specifically, finding strongly connected components in the set $G - B$) over the leftover subset in a directed graph. Would simply ignoring any edges leading to vertices in $B$ and ignoring any vertices in $B$ work just fine?

• Can you edit your question to define what you mean by linear time? Linear in what, specifically? Linear time in a graph often means $O(|V|+|E|)$ time. Is that what you mean? Or did you mean a running time that is linear in $|B|$? Linear in $|B|$ + the number of edges removed? Also, how is the graph $G$ given to you? In other words, what representation is it stored in?
– D.W.
Apr 3 '18 at 20:39
• The graph is not represented in any way, I can pick the representation that works most optimally for me. Apr 3 '18 at 20:43
• OK. Thanks for the clarifications to the question and the edits.
– D.W.
Apr 3 '18 at 20:47

Yes, this can be done on an adjacency list representation in $O(|V|+|E|)$ time. Looping over all the edges can be done in $O(|V|+|E|)$ time. As you look at an edge, you can check both endpoints; if either one is in $B$, you can delete it. Afterwards, you can iterate through the vertices and remove the vertices in $B$ (their adjacency lists will be empty, so no need to do anything with their adjacency lists); this takes $O(|V|)$ time. The entire process takes $O(|V|+|E|)$ time.
• If you have a vertex not in $B$ that has an edge to a vertex in $B$ (this is a directed graph), the vertex in $B$ to which it has an edge would show up in the edge list of the vertex not in $B$. How would I delete that edge without looping over the edges in the rest of the graph (ie vertices that are not in $B$)? Apr 3 '18 at 20:53