# Tag Info

Your problem is NP-hard. With the extra constraint, it is at least as hard as max independent set. In particular, suppose we have an undirected graph $G$. Let there be one object per vertex in $G$. For each edge in $G$, we'll have a constraint saying that at most one of the two endpoints of that edge can be assigned (using your new constraint type). We'...
First, compute the minimum cut value $c$ of the network. Second, remove edge $e_1$ and increase the capacity of $e_2$ to infinity, then compute the minimum cut value $c_1$ of the new network. Third, remove edge $e_2$ and increase the capacity of $e_1$ to infinity, then compute the minimum cut value $c_2$ of the new network. Now you can check if $c-c_1\ge ... 1 Replace each undirected edge$(u,v)$by two directed edges, one in each direction:$u\to v$and$v\to u$. That gives you a graph with only directed edges. Then the max-flow on that graph is the same as the max-flow on your original graph. 0 Orlin's algorithm can solve max flow in sparse graphs in$O(|V| |E|)\$ time. See Max flows in O(nm) time, or better. James B. Orlin. STOC 2013. You'll have to decide whether the potential speedup is worth the time to implement it, as I believe the algorithm is quite complex. I don't know whether the algorithm is better in practice. Perhaps someone else ...