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.



Edge-disjoint paths avoiding some subgraphs
This seems to be an NP-complete problem. It can be shown by reduction from
3-SAT, as follows.


For a given 3-SAT formula with $p$ variables and $m$ clauses, build a graph consisting of $2p$ internally disjoint paths between vertices $s$ and $t$, each path with $m+1$ internal vertices. For each variable $x\_i$ we have two paths $P\_i, Q\_i$. 


For each $i=1,2,\dots,p$, we define $H\_i$ as the set of two vertices of $P\_i$ and $Q\_i$ adjacent to $s$. This is the variable gadget. For each $j=1,2,\dots,m$, the clause gadget $H\_{p+j}$ consists of three vertices, selected from paths corresponding to literals in the $j$th clause $C\_j$: if $x\_i$ appears without negation in $C\_j$, we select a vertex from $P\_i$. If $x\_i$ appears with negation in $C\_j$, we select a vertex from $Q\_i$.


Now there are $p$ disjoint $st$-paths subject to the constraints if and only if the given formula is satisfiable.


In fact, the paths $P\_i, Q\_i$ may have length $2$, it does not matter that some of the sets $H\_i$ will intersect.


