1
$\begingroup$

Given an undirected, weighted graph $G=(V,E)$ and two nodes $s,t \in V$ and weight function $w: E \rightarrow \mathbb{N}$. The weight of a (s,t)-cut $ (U, U^C)$ is given by:

$$ w(U,U^C) := \sum_{\{i,j\}\in V :i\in U \land j\in U^C} w(\{i,j\}) $$

Reduce $$ MinCUT:= \{<G,c,s,t,k>\mid \text{There is a (s,t)-cut with weight} \leq k\} $$ to $$ BinaryProgram:= \{<A,b> \mid \text{There is a vector } y\in\{0,1\}^* \text{ such that } Ay \leq b \} $$

I know i have to find a matrix $A$ and a vector $b$ which implement the following constraints:

  • The weight of the edges which cross the sets of the cut must be $\leq k$
  • Node $s$ must be in set $U$ and node $t$ must be in set $U^C$
  • Every node must either be in $U$ or $U^C$

Can somebody give me a hint how implement these constraints into a matrix ?

$\endgroup$
  • 2
    $\begingroup$ Hello! We discourage posts that simply state a problem out of context, and expect the community to solve it. What have you tried? Where did you get stuck? We do not want to just do your exercise for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. You might want to review your textbook and cs.stackexchange.com/q/12102/755. $\endgroup$ – D.W. Jan 3 '16 at 20:38
1
$\begingroup$

Hint: Let's try to encode the constraints using two types of variables: $a_v$ for each vertex $v$, and $b_{uv}$ for each edge $u,v$. The variable $a_v$ encodes which part of the cut vertex $v$ belongs to. The variables $b_{uv}$ equals 1 if the edge $(u,v)$ is cut.

We want to enforce the following constraints:

  • $a_s = 0$ and $a_t = 1$.
  • $b_{uv} = 1$ if $a_u = 1$ and $a_v = 0$ or if $a_u = 0$ and $a_v = 1$.
  • $\sum_{uv \in E} w(u,v) b_{uv} \leq k$.

Try to encode all these constraints as inequality constraints.

$\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.