2
$\begingroup$

Given a graph $G=(V,E)$ and $k < |E|$, identify $E' \subset E$ such that $|E'| = k$, so that the max flow in the graph $(V, E')$ is as large as possible.

Is this possible in polynomial time? Is any NP-hardness or approximations for this known?

Note. I see many references for ensuring that the max flow in $(V, E')$ is as small as possible. i.e., to identify the most disruptive change. Here, I am looking to identify the least disruptive change.

$\endgroup$
1

2 Answers 2

2
$\begingroup$

There is a polynomial solution for a case of unit edge capacities. At the same time the problem is NP-hard for arbitrary edge capacities.


Suppose that every edge has capacity $1$. Here is a scheme of polynomial solution.

  1. Give each edge cost $1$.
  2. Using minimum-cost flow algorithm find the maximum capacity $f$ of a flow with cost at most $k$.
  3. Take as $E'$ all edges of the minimum cost flow of capacity $f$.
  4. Add any other edges of $G$ if you need to have exactly $k$ edges.

Note that all costs are $1$ so you don't need a strongly polynomial algorithm for minimum-cost flow problem. A weakly polynomial one would be enough.

Also not every minimum-cost flow algorithm iteratively increments flow value by $1$. In such case you may use binary search on flow value.


Now let's consider case of arbitrary edge capacities.

Let's reduce Set Cover problem, which decision version comes among Karp's 21 NP-complete problems, to this one. Given set of $m$ subsets $S_1, S_2, \ldots, S_m$ of universe $[n] = \{\,1, 2, \ldots, n\,\}$ we need to find a minimum subset $\{\,i_1, i_2, \ldots, i_{\ell}\,\}$ of indices such that $$S_{i_1} \cup S_{i_2} \cup \cdots \cup S_{i_{\ell}} = [n] = S_1 \cup S_2 \cup \cdots \cup S_m.$$ In the decision version we need to check for given $\ell$ that there exists such a subset of $\ell$ indices.

Let's build the following network $G = (V, E)$. A source vertex $s$ is connected by a single edge of capacity $n$ to every vertex $v_1, v_2, \ldots, v_m$ corresponding to sets $S_1, S_2, \ldots, S_m$. Every vertex $u_1, u_2, \ldots, u_n$ is connected by a single edge of unit capacity to a sink vertex $t$. Each $v_i$ is connected to all vertices $u_j$ such that $j \in S_i$ by a single edge of unit capacity. Let $k = 2n + \ell$. Then subset $E'$ of edges of cardinality $k$ such that flow value in $G' = (V, E')$ is $k$ exists if and only if there exists a subset of $\ell$ indices such that corresponding sets union equals to the universe.

This is rather easy to see. If such set of indices exists then include into $E'$ the following edges:

  • between $s$ and corresponding $v_{i_x}$'s ($\ell$ edges);
  • between $t$ and every $u_j$ ($n$ edges);
  • for every number $j$ select a single set containing this element $S_{i_y}$, and keep the corresponding edge $\{\,v_{i_y}, u_j\,\}$ ($n$ edges). Then the flow value in $G'$ is $n$.

If flow value in $G'$ is $n$ then every edge between $t$ and $v_j$ belongs to $E'$. Also at least one edge $\{\,v_i, u_j\,\}$ belongs to $E'$ for each $j$. So there are at most $k - 2n = \ell$ edges $\{\,s, v_i\,\}$ belong to $E'$. At the same time union of corresponding sets $S_i$ equals to the universe.

The proof is finished by an observation that this reduction is polynomial.

$\endgroup$
3
  • $\begingroup$ If 2 units of flow goes through some edge E, then the cost along that edge will be 2 and not 1. I am not sure, if this algorithm will work hence? $\endgroup$
    – Sriram
    Commented May 23 at 6:08
  • $\begingroup$ @Sriram you are right, it is valid for the case of unit capacities only $\endgroup$
    – Smylic
    Commented May 23 at 14:50
  • $\begingroup$ @Sriram I've updated my answer $\endgroup$
    – Smylic
    Commented May 23 at 16:53
1
$\begingroup$

The paper Finding k most influential edges on flow graphs should show that this is NP-complete and inapproximable.

Petrie Wong, Cliz Sun, Eric Lo, Man Lung Yiu, Xiaowei Wu, Zhichao Zhao, T.-H. Hubert Chan, Ben Kao,

Finding k most influential edges on flow graphs.

Information Systems, Volume 65, 2017.

Ps, there is a preprint available on one of the authors' homepage.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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