2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.