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