Skip to main content
deleted 4 characters in body
Source Link
R B
  • 9.5k
  • 5
  • 35
  • 77

This problem is NP-hard.

Reduction from PARTITION:

Given a set of numbers $S=\{x_1,\ldots,x_n\}$, construct the following flow network:

$$V = \{s,v,t\}\cup \{x_1,\ldots,x_n\}$$ $$E = \{(s,x_i) | x_i\in S\} \cup \{(x_i,v)|x_i\in S\} \cup \{(v,t)\}$$ $$c((s,x_i))=c(x_i,v)=x_i\ \ \ c((v,t))=\frac{\sum_{i\in[n]}{x_i}}{2}$$$$c((s,x_i))=c((x_i,v))=x_i\ \ \ c((v,t))=\frac{\sum_{i\in[n]}{x_i}}{2}$$

$S$ is partitionable iff there exist "either saturate an"saturate edge or avoids"avoid" flow of value $c((v,t))$.

This problem is NP-hard.

Reduction from PARTITION:

Given a set of numbers $S=\{x_1,\ldots,x_n\}$, construct the following flow network:

$$V = \{s,v,t\}\cup \{x_1,\ldots,x_n\}$$ $$E = \{(s,x_i) | x_i\in S\} \cup \{(x_i,v)|x_i\in S\} \cup \{(v,t)\}$$ $$c((s,x_i))=c(x_i,v)=x_i\ \ \ c((v,t))=\frac{\sum_{i\in[n]}{x_i}}{2}$$

$S$ is partitionable iff there exist "either saturate an edge or avoids" of value $c((v,t))$.

This problem is NP-hard.

Reduction from PARTITION:

Given a set of numbers $S=\{x_1,\ldots,x_n\}$, construct the following flow network:

$$V = \{s,v,t\}\cup \{x_1,\ldots,x_n\}$$ $$E = \{(s,x_i) | x_i\in S\} \cup \{(x_i,v)|x_i\in S\} \cup \{(v,t)\}$$ $$c((s,x_i))=c((x_i,v))=x_i\ \ \ c((v,t))=\frac{\sum_{i\in[n]}{x_i}}{2}$$

$S$ is partitionable iff there exist "saturate edge or avoid" flow of value $c((v,t))$.

Source Link
R B
  • 9.5k
  • 5
  • 35
  • 77

This problem is NP-hard.

Reduction from PARTITION:

Given a set of numbers $S=\{x_1,\ldots,x_n\}$, construct the following flow network:

$$V = \{s,v,t\}\cup \{x_1,\ldots,x_n\}$$ $$E = \{(s,x_i) | x_i\in S\} \cup \{(x_i,v)|x_i\in S\} \cup \{(v,t)\}$$ $$c((s,x_i))=c(x_i,v)=x_i\ \ \ c((v,t))=\frac{\sum_{i\in[n]}{x_i}}{2}$$

$S$ is partitionable iff there exist "either saturate an edge or avoids" of value $c((v,t))$.