[nickponline]

I think this problem is called the maximum-weight closure and can be solved as max flow. You want to find a cut between source (horse) so they were no out-going edges not in the cut (escape routes).

[emil-lp]

It's not the same problem. First, it's not directed, second it's a vertex separation problem.

[nickponline]

Ah yes quite right.