Edge-disjoint paths avoiding some subgraphs

Question

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.

Answer 1

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.