2
$\begingroup$

I have a randomly generated directed graph with 3 types of vertices: input, output, and the rest (I'll call them hidden).

A useless vertex is a hidden vertex which:

  • can't be reached from an input vertex, OR
  • can't reach an output vertex.

For example:

  • input = yellow/green
  • output = blue
  • hidden = white
  • useless = red border

Sample Graph

Note that:

  • cycles and self-loops are allowed
  • the graph may be disjoint
  • inputs and output nodes are known (i.e. you can determine what type of node an edge connects to and from)

So what do you call this type of problem? Is there any algorithm for this?

I'm looking for more information about this. I have a python script which seems to work. I'm just not sure if it will work for all cases since I don't fully understand it myself. It was a mix of DFS, trial-and-error, manual hand-checking, and a bunch of if statements.

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ Using DFS/BFS, you can find all vertices reachable from some set $S$ (in your case, the inputs). Reversing the direction of the edges, you can find all vertices which can reach a set $T$ (in your case, the outputs). Take the intersection to find all useful vertices. $\endgroup$
    – Yuval Filmus
    Apr 11, 2020 at 21:54

1 Answer 1

Reset to default
4
$\begingroup$

Let $n$ and $m$ be the number of vertices and edges of your input graph $G = (V,E)$, respectively. You can find all useless vertices in time $O(n+m)$.

You can discover the set $S$ all vertices reachable by at least one source in $O(n + m)$ overall time.

You do this by either:

  • running one visit from each of the input vertices, marking discovered vertices as visited, and taking care of not revisiting already visited vertices; or
  • adding a dummy "super-source" vertex $s$ with an outgoing edge towards every input vertex in $G$, and then running a visit from $s$.

By using the same technique on the reversed graph $G^R$, you can find the set $T$ of all vertices that are reachable from an output vertex in $G^R$. In other words a vertex $v$ can reach an output vertex in $G$ iff $v \in T$.

The set you are looking for is then $V \setminus (S \cap T)$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Uhmm.. A vertex $v$ is defined to be useless if $v$ is not reachable from and input vertex OR $v$ cannot reach an output vertex. If at least one of these two conditions happens then $v$ won't be in both $S$ and $T$, i.e., $v \not\in S \cap T$. Therefore $v \in V \setminus (S \cap T)$. On the other hand, if none of the above conditions is true then $v$ is in both $S$ and $T$, i.e., $v \in S cap T$, showing that $v \not\in V \setminus (S \cap T)$. $\endgroup$
    – Steven
    Apr 12, 2020 at 10:20

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.