New answers tagged

0

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'...


1

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 ...


Top 50 recent answers are included