the ancestry predicate at the beginning of the formal problem statement here is dominance, at least as applied to their rooted trees.

Because it is a rooted tree, only DFS intervals are required to determine ancestry.

You can detect whether a new blocking loop is going to be formed through online dominator maintenance/online cycle detection, etc, during optimization, rather than use a heuristic, if you wanted to.

Not sure it's practically faster, but that's at least the graph-theoretic answer.

In practice, outside of the suggested heuristic, I have to imagine you'd normally throw branch and bound at this, using some lazy-cut for the blocking loops (IE you can keep any of these edges but not all of them) and let it go to town.

The paper (at least, this paper) doesn't compare that to what they did, and i'd be shocked if someone hasn't tried this before, so not sure it's useful.

I'll also say you can get existing AI models to tell you the above, but you have to push them a bit most of the time step by step. Just handing them the whole overall problem, as described, and saying "what are the graph theoretical problems related to this" it sort of gets lost.

Probably because the LLM isn't doing a good job of predicting graph-theoretic words when the language is not graph theoretic, but if you translate it into a graph theoretic language piece by piece, and ask it about that, the prediction becomes better :)