1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Why do you think of max cut? Is min cut more intuitive? $\endgroup$ – xskxzr Sep 27 at 10:54
  • $\begingroup$ @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. $\endgroup$ – Matheus Diógenes Andrade Sep 27 at 19:24
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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