0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – D.W. Apr 3 '18 at 20:39
  • $\begingroup$ The graph is not represented in any way, I can pick the representation that works most optimally for me. $\endgroup$ – picotard Apr 3 '18 at 20:43
  • $\begingroup$ OK. Thanks for the clarifications to the question and the edits. $\endgroup$ – D.W. Apr 3 '18 at 20:47
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$)? $\endgroup$ – picotard Apr 3 '18 at 20:53
  • $\begingroup$ @Kek, see revised answer. $\endgroup$ – D.W. Apr 3 '18 at 21:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.