# Set of DAG vertices disconnecting a vertex from forbidden vertices

Let $$v$$ be a vertex with in-degree 0 in an (acyclic) DAG $$G$$, and let $$F$$ be a subset of $$G$$'s vertices (the "forbidden") vertices. Now suppose $$U$$ is a set of vertices such that every path from $$v$$ to $$F$$ intersects $$U$$.

Is there a commonly-used term for such sets? I was thinking about using the term "Front", but a (cursory and lazy) search tells me that's not a popular term. I can't use "cut", because that's reserved for sets of edges with the similar property (cutting off $$v$$ from $$F$$; usually $$F$$ is the subgraph of all vertices reachable from $$A$$ but not in $$A$$).

Also, suppose that $$U$$ is minimal, in the sense that for every $$u$$ in $$U$$, there's a path from $$v$$ to $$F$$ which intersects no other vertex of $$U$$. Is there a commony-used term for this kind of sets?

If it helps, I'm willing to refer to $$v$$ as a "source" and to $$F$$ as the set of "sinks".

Wikipedia says that, for an undirected graph, you can say:

• $$A$$ is the vertex separator for $$v$$ and $$F$$.
• $$A$$ is the separating set for $$v$$ and $$F$$.
• $$A$$ is the vertex cut for $$v$$ and $$F$$.

perhaps these terms are used for digraphs as well, even though "connected components" are not quite the same thing in digraphs.

edit: @PålGD suggests the variant "separator", similar to the second option.

• Yes, $U$ is a $v-F$ separator! – Pål GD Mar 12 at 15:59
• @PålGD: I'm asking whether this term is used often, not whether it fits... can you say a few words about where/when it has been used? – einpoklum - reinstate Monica Mar 12 at 17:28
• Yes, separator is standard terminology for a vertex set that breaks a graph into several components, and a $u-v$ separator is a vertex set that removes (hits) all paths from $u$ to $v$. A cut is more often used when the set you remove is a set of edges, e.g. maxflow/mincut. – Pål GD Mar 12 at 20:39