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?

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

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\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$
    – fraiser
    Apr 3, 2018 at 20:53
  • $\begingroup$ @Kek, see revised answer. $\endgroup$
    – D.W. ♦
    Apr 3, 2018 at 21:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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