# How to find a cut in a graph with additional constraints?

I have a complete undirected graph $$G=(V,E)$$ with positive non-null rational weights $$c:E \to \mathbb{Q}^+_{*}$$ on the edges, such that $$c(v,v) = 0$$ for all $$v$$, and a subset $$C \subset V$$.

I would like to find (if it exists) a subset $$S \subset V$$ such that $$\delta(S) < 2$$, $$S$$ contains at least one vertex of $$C$$, and $$S \ne C$$. Here $$\delta(S)$$ represents the sum of the weights of the edges that cross the cut $$(S, V \setminus S)$$.

Is there a polynomial-time algorithm for this problem?

I have thought of two possible approaches:

1. Create a new graph $$G'$$ using as edge weights $$c'(v,w) = -c(v,w)$$ and adapt (by updating some LP formulation or DP approach) the max-cut optimization version to this case;
2. Reduce this problem in the problem of partitioning $$V$$ into two vertex sets $$X,Y$$ so that the sum of the weights of the edges crossing the cut is < 2, and $$X$$ and $$Y$$ each contain at least one vertex of $$C$$. However, I couldn't think of any approach to solve this problem, yet.

I know the max-cut problem is hard, which makes me wonder whether there is a polynomial-time algorithm for this problem.

Remark: The proposed solution does not need to follow the presented approaches, they are presented just to help the reader.

I am facing this problem in a fractional separation routine of a routing MILP formulation.

• Why do you think of max cut? Is min cut more intuitive? – xskxzr Sep 27 '20 at 10:54
• @xskxzr well, I've tried the min-cut approach, however, there are cases in which it fails. Regarding the max-cut, note that as -c'(u,v) increases, the c(u,v) decreases. – Matheus Diógenes Andrade Sep 27 '20 at 19:24

The problem can be solved in polynomial time. Here is one algorithm:

• For each $$s \in C$$ and each $$t \in V \setminus C$$ such that $$s \neq t$$:

• Find the minimum-cost $$(s,t)$$-cut. By the max-flow min-cut theorem, this can be done in polynomial time using any maximum flow algorithm.

• If the cost of this cut is < 2, output it and halt.

• For each $$s_0 \in C$$ and each $$s_1 \in V \setminus C$$ and each $$t \in V \setminus \{s_0,s_1\}$$:

• Find the minimum-cost cut that contains both $$s_0$$ and $$s_1$$ in the left part and $$t$$ in the right part. This can be done in polynomial time by modifying the graph to merge the two vertices $$s_0,s_1$$ into a new vertex $$s'$$, then finding a minimum $$(s',t)$$-cut in the modified graph.

• If the cost of this cut is < 2, output it (replacing $$s'$$ with $$s_0,s_1$$) and halt.

• If you reach this point without halting, output that no such cut exists.

There may be more efficient algorithms by modifying algorithms for min-cut instead of min $$(s,t)$$-cut. I don't know. However, this suffices to show that the problem can be solved in polynomial time.

Proof of correctness: Suppose a cut $$(S,V \setminus S)$$ of the desired form exists. Then there are only two ways we can have $$S \ne C$$:

• Case 1: $$C \setminus S \ne \emptyset$$: In this case, pick any vertex in $$C \cap S$$ and call it $$s^*$$ (this can be done since $$C \cap S \ne \emptyset$$) and pick any vertex in $$C \setminus S$$ and call it $$t^*$$ (this can be done since $$C \setminus S \ne \emptyset$$). Consider the minimum-cost $$(s^*,t^*)$$-cut, $$(S^*,T^*)$$. By construction, $$S^*$$ has at least one element of $$C$$ (since $$s^* \in S^*$$) and $$S^* \ne C$$ (since $$t^* \notin S^*$$) and $$\delta(S^*) \le \delta(S) < 2$$, so $$(S^*,T^*)$$ is a valid solution to your problem. Moreover, it will be found by one of the iterations of the first for-loop, namely, when $$s=s^*$$ and $$t=t^*$$, so the algorithm will correctly find a solution.

• Case 2: $$S \setminus C \ne \emptyset$$: In this case pick any vertex in $$S \setminus C$$ and call it $$s^*_1$$ (this can be done since $$S \setminus C \ne \emptyset$$), pick any vertex in $$S \cap C$$ and call it $$s^*_0$$ (this can be done since $$S \cap C \ne \emptyset$$), and pick any vertex in $$V \setminus S$$ and call it $$t^*$$ (this can be done since $$S \ne V$$). Consider the minimum-cost cut $$(S^*,T^*)$$ such that $$s^*_0 \in S^*$$, $$s^*_1 \in S^*$$, and $$t^* \in T^*$$. By construction, $$S^*$$ has at least one element of $$C$$ (since $$s^*_0 \in S^*$$) and $$S^* \ne C$$ (since $$s^*_1 \in S^*$$) and $$\delta(S^*) \le \delta(S) < 2$$, so $$(S^*,T^*)$$ is a valid solution to your problem. Moreover, it will be found by one of the iterations of the second for-loop, namely, when $$s_0=s^*_0$$ and $$s_1=s^*_1$$ and $$t=t^*$$, so the algorithm will correctly find a solution.

We see that in either case, if a solution exists, the algorithm will successfully output a valid solution; and those are the only two cases that can occur if a solution exists.

Conversely, if no valid solution exists, it is easy to see that the algorithm will correctly output that no cut exists.