-1

Note: this question is not a duplicate of the following questions: How to remove vertices from a graph that are not coverable by cliques? How to remove vertices from a graph while preserving clique coverage of specific vertices? This question is with respect to removing vertices that are not reachable from a set of vertices, regardless of clique membership.

How can I remove vertices from a graph that are not reachable from a given set of vertices?

Here is a toy example and solution:

In the graph below, I want to remove the vertices that are not reachable from any vertex with an "x". The orange vertices are the vertices to be removed.

toy example graph image

The current approach is doing depth-first search from each of the vertices marked with an "x", and keeping track of which vertices are visited. All vertices from the graph that are not in that set of visited vertices are removed from the graph. However, this could take a while if the graph is large, so I was wondering if there is a faster way of doing this.

thunderbird30
  • 37
  • 3

1 Answers1

1

This is a slight variation of your previous question.

  • Do a BFS from any vertex marked X, marking each node reached inX

  • set Xconnected TRUE

  • LOOP V over vertices marked X

    • IF V in NOT marked inX

      - set Xconnected FALSE

- BREAK from LOOP V

ENDLOOP V

  • IF Xconnected TRUE

    • Choose W as any vertex marked X

    • Do a BFS to find all vertices reachable from W

    • Remove any vertices that were not reached in the BFS

  • ELSE

    • LOOP W over vertices marked X

      • Do a BFS to find all vertices reachable from W

      • Remove vertices that were not reached in the BFS AND not marked X

      • Remove vertices that were reachable from W AND are marked X

    • ENDLOOP W

ravenspoint
  • 19,093
  • 6
  • 57
  • 103
  • 1
    There's no guarantee that the X vertices are connected. Run BFS from the set of X vertices or create a dummy vertex adjacent to all of them and start from it. – Dave Aug 30 '23 at 22:48
  • @Dave in the OP's other, very similar questions, the X vertices are in a clique, so it was reasonable that they were also in this question. The OP has since declared ( in a comment ) that the Xs may not be connected, so I have updated my answer accordingly, – ravenspoint Aug 31 '23 at 19:55