As a natural generalization of min-cut, the following problem seems interesting to me,

Alternatively, one can consider a closely related version of Problem 1,

This problem can be called the “vertex connectivity interdiction”. One can also consider the “algebraic connectivity interdiction” (the second smallest eigen value of the Laplacian matrix).

In fact, I think Problem 2 is not well motivated. I am interested in it since there may be connections between breaking vertex connectivity and breaking combinatorial rigidity. However, it seems strange to consider interdiction problems on edge set for vertex connectivity. For vertex removal, this problem is easy (by splitting vertex and finding mincut).

1 Checking $k$-vertex connectivity

Checking if a given graph is $k$-vertex connected can be done in polynomial time. By Menger’s theorem we need to check if for every vertex pair $(s,t)$ there are at least $k$ vertex disjoint paths (excluding $s$ and $t$) connecting $s$ and $t$. The number of vertex disjoint paths between $s$ and $t$ can be easily computed through max flow. We replace every internal vertex $v$ with two copies $v_{in}$ and $v_{out}$ and add directed edges from $N(v)$ to $v_{in}$ and from $v_{out}$ to $N(v)$ with capacity 1. The integral max flow is the number of internally disjoint paths between $s$ and $t$. Since the constraint matrix of flow problems is TU, maximizing the flow gives us the vertex connectivity.

Instead of computing the flow for every pair, if we want one flow that gets the demand for every vertex pair $(i<j)$, the problem becomes much harder. This is Multi-commodity flow problem.

Currently the fastest algorithm for computing vertex connectivity is [1] https://dl.acm.org/doi/10.1145/3406325.3451088. There is a nice table for a summary of connectivity related algorithms.

[1] appears in the last line. The conference version was published on FOCS96.

1.1 Minimum cut for edge connectivity

Finding the minimum edge set whose removal breaks the $k$-edge connectivity is “easy”. It is known that the global min-cut is the edge connectivity number. Thus we can simply compute the min-cut and remove any number of the edges as needed. — which is not true! For unit edge weights this problem is indeed that easy. However, for general weights edge-connectivity cut is not as easy as min-cut. This problem is actually the unit cost version of connectivity interdiction. See next section for more details.

1.2 Minimum cut for vertex connectivity

With the knowledge of how to compute vertex connectivity, we try to compute the minimum cut for $k$-vertex connectivity in a similar way. First we can find the vertex pair $(s,t)$ with the smallest number of internally disjoint paths. Note that we are dealing with the modified graph when computing the vertex connectivity number with flow. Hence the min-cut may contain edges that are not in the original graph, i.e., the edges connecting $v_{in}$ and $v_{out}$. For example, consider a graph where every edge has multiplicities 2. The min-cut reported by the flow algorithm should only contain edges between $v_{in}$ and $v_{out}$.

There is a list of open problems on vertex(node) connectivity. I guess Problem 1 is NP-hard but cannot prove it. However, the capacitated version of Problem 2 and Problem 1 is hard. Given a graph $G=(V,E)$ and edge weights $w:E\to {\mathbb{Z}}_{\ge 0}$ and costs $c:E\to {\mathbb{Z}}_{\ge 0}$ and a budget $b\ge 0$, find edge set $F\subset E$ such that $c(F)\le b$ and such that removing $F$ minimizes the vertex connectivity of $G-F$. Similar to the edge connectivity case (which will be shown in the next section), if the cost $c$ is nontrivial then kanpsack is a special case of this problem. (Consider $G=K_n$ for some large $k$. Pick a $K_{n-1}$ in $G$ and set the cost of edges in $K_{n-1}$ to infinity.) How hard is Problem 2 if costs are trivial?

2 (Edge) Connectivity interdiction

Connectivity interdiction is first studied by Zenklusen [2].

A recent paper [3] gives an FPTAS for the problem. Here I try to develop the intuition since I have never seen an algorithm based on reweighting edges this complicated and ingenious.

First one can see that the optimal solution can always be a subset of edges in a cut of $G$. This is because if the optimal solution $R^{\ast }$ contains any edge not in the cut, we can safely delete it from $R^{\ast }$. Thus the optimal solution is indeed a pair $(C^{\ast },R^{\ast }\subset C^{\ast })$. The authors call this problem the $b$-free min-cut problem ($b$ is the budget and we are allowed to pick edges for free in the “mincut” with total weight at most $b$).

So the goal is to find a FPTAS for the $b$-free mincut problem. The problem is hard since it contains knapsack as a special case. (Consider a graph with many parallel edges and only 2 vertices.) However, it is known that there is a FPTAS for knapsack. If we know part of the optimal solution, i.e., $C^{\ast }$, we can use the FPTAS for knapsack to find the optimal $R^{\ast }$.

At this stage, if there is a hint suggesting reweighting the edges, I would guess that $C^{\ast }$ is exactly (or close to) the min-cut of the re-weighted graph. Based on this idea I would also guess that, although the connectivity interdiction problem ($b$-free min-cut) is NP-hard, $C^{\ast }$ can be computed in polynomial time. In other words, the intractable part is solving the knapsack in $C^{\ast }$. This statement seems reasonable, since this problem is know to be in P for unit costs and in that case the kanpsack is trivial. Let’s assume that my guess is correct and work on the reweighting part.

2.1 Reweighting

There is a chapter on reweighting in Sariel Har-Peled’s gemetric approximation book(not quite the same as the reweighting technique in [3]). Is reweighting a common technique for designing approximation algorithms?

One possible weight function is setting $w(e)=0$ for all $e\in R^{\ast }$… However, this is cheating since we assume that $R^{\ast }$ is the hard part. So now we need to find a weight function such that the following holds,

1. The min-cut of the re-weighted graph is close to $C^{\ast }$.
2. Computing the weight function takes polynomial time.

From the “cheating” example we can see that knowing $R^{\ast }$ does help but computing $R^{\ast }$ is hard. So maybe we can find a slightly worse weight function which is a lot easier to compute. So it seems like we are making a trade-off between how close the global min-cut of the re-weighted graph is to $C^{\ast }$, and how much time is needed to compute this weight function. This paper indeed does a great job in finding such a balance. I sent an email to one of the authors to ask for the intuition behind the reweighting but did not get a real answer. They suggested reading [2]. Zenklusen did almost the same thought experiment as above. Instead of using reweighting, he indirectly enumerated $R^{\ast }$. Consider the unit cost case for example. If the optimal cut $C^{\ast }$ is given, the interdicted edges $R^{\ast }$ will be those $b$ edges in $C^{\ast }$ with heaviest weights. We cannot directly enumerate $R^{\ast }$ since it still takes exponential time. What we can enumerate is a lowerbound of the weight of edges in $R^{\ast }$. Set all edges with weights exceeding this lowerbound to be in $R^{\ast }$ and find global min-cut with additional budget constraint on these edges. Then we have only $m$ lowerbound to enumerate and the budgeted min-cut can be computed fast. For general costs, he enumerated the set of $1/\epsilon$ edges with heaviest weights in $C^{\ast }$.

The plan is to figure out how did the authors come up with the weight function in [3] and if it is possible to find a better weight function.

The key part is the following new problem called normilized min-cut,

I have been thinking for a while how this problem is involved but have no clue. However, it indeed works… The weight function is defined based on an estimation of Problem 4. The authors claim that the optimal solution to b-free min-cut problem is a 2-approximate min-cut of the reweighted graph. Then they enumerate all 2-approximate min-cut of the reweighted graph and run the FPTAS for knapsack on each cut.

2.2 More on normalized min-cut

If one slightly modifies lemmas in section 2 in [3], there are some interesting properties. Let $\tau$ be the value of the optimal normalized min-cut (in [3] $\tau$ is an estimation of the optimum) and define ${\tilde{w}}_{\tau }$ accordingly. Then one can prove that the global min cut in $(G,{\tilde{w}}_{\tau })$ is exactly the optimal cut in the normalized min-cut of $(G,w)$ (slightly modify lemma3 to see this). Also the value of min-cut in $(G,{\tilde{w}}_{\tau })$ is $\tau (b+1)$.

For unit cost, the optimum of normalized min-cut can be computed using the same complexity as connectivity interdiction (ignoring polylog factors) [4]. Consider the sequence $\left\{{\lambda }_i=\frac{{\min }_{|F|\le i}w(C\setminus F)}{b+1-i}\right\}$. If this is unimodal, $O(\log b)$ calls of connectivity interdiction algorithm should be sufficient. (Note that $b$ is at most $m$ since costs are unit.) However, one can easily see that this sequence is not unimodal. Thus I don’t quite believe this claim.

2.3 Comments on [3]

References