New answers tagged cc.complexity-theory
3
Let $G=(V,E)$ be an arbitrary instance of $3$-coloring.
Construct a new graph $G'=(V',E')$ as follows:
$V'$ contains all the vertices in $V$, and for every edge $e\in E$ it contains a corresponding new vertex $x(e)$.
$E'$ contains all the edges in $E$, and for every edge $e=\{u,v\}\in E$ it contains the two new edges $\{x(e),u\}$ and $\{x(e),v\}$.
Note the ...
0
The NP-complete Balanced min cut problem ($|S|< c|V|$ and $|V-S|<c|V|$ for $0<c<1$) is a special case of your problem. Hence your problem is NP-complete.
Reference: Garey, M.R., Johnson, D.S., Stockmeyer, L.J.: Some simplified NP-complete graph problems. Theor. Comput. Sci. 1, 237–267 (1976)
Top 50 recent answers are included
