Let $G$ be a directed graph on $n$ vertices. Let $H_1$, ..., $H_k$ be marked subgraphs of $G$. (Specifically, each $H_i$ consists of a subset of the vertices of $G$ and a subset of the edges of the induced subgraph.) I am interested in an algorithm for finding the maximum number of edge-disjoint paths from $s \in V$ to $t \in V$, subject to the constraint that none of the $H_i$ is entirely contained in the union of the paths.

Without the constraint, this is a standard max flow problem. With the constraint, one could modify the Ford-Fulkerson algorithm to conform to the constraint at all steps and give a lower bound, but there's no reason to expect it to be tight.

I am primarily interested in the setting where $|H_i| = O(1)$ and $1 \ll k \ll n$. Ideally, of course, I would like an algorithm that's polynomial in all of $n$, $k$, and $\max_i |H_i|$.

I am willing to make some assumptions about the $H_i$: one natural assumption is that each $H_i$ is either a totally disconnected set of vertices, or the entire induced subgraph. I am also willing to assume that $G$ is directed acyclic. I don't know whether either of those help.