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.

  • $\begingroup$ Yes, $U$ is a $v-F$ separator! $\endgroup$ – Pål GD Mar 12 '19 at 15:59
  • $\begingroup$ @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? $\endgroup$ – einpoklum Mar 12 '19 at 17:28
  • 1
    $\begingroup$ 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. $\endgroup$ – Pål GD Mar 12 '19 at 20:39

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.