People use "vertex-cut" and "vertex cut" where I am unsure whether it should be with dash or without dash. For me, it looks nicest to have "st-vertex-cut" and then "st-vertex-cut set" without dash, where "st-vertex-cut" specifies the set, but I am unsure. What are the rules for adding the dashes and how to write the set that is defined by vertex cuts disconnecting two terminals called S and T?
You are forming a compound noun. According to Oxford dictionaries,
In the past, these sorts of compounds were usually hyphenated, but the situation is different today. The tendency is now to write them as either one word or two separate words. However, the most important thing to note is that you should choose one style and stick to it within a piece of writing. Don’t refer to a playgroup in one paragraph and a play-group in another.
Your problem is that st-vertex is already hyphenated—and actually not an example of good formatting, I think using capitalized ST or dashed s-t as is done sometimes would be better. Hence, the option of making just one word, * ST-vertexcut, is ruled out. I would go for ST-vertex cut, and ST-vertex cut set (or even ST vertex cut [set]).
Btw, "vertex" is omitted in Wikipedia article, does it mean that you have a variant of what they describe or is it the same?
It all depends on what is modifying what, and how you want to encourage that reading.
You're talking about a set of vertices, which are a cut set and that is a set cutting between a source and target ('st') vertex. So, in order, it should be: st, vertex, cut, and set.
Since the 'st' can't stand alone (it's not a stand alone word), it must be st-vertex, but also it is a cut set of vertices (or vertex cut set).
So based on principles, I'd suggest 'st-vertex cut set'.
But that's logic and not necessarily what people actually do. I've seen both "vertex-cut set" and "vertex cut set"; since, it seems at free variation, it is really now your preference. For readability, I think fewer dashes the better.