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

Question

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.

Answer 1

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.