Name

Label

Problem

NP-hardness

Cutwidth

CUTWIDTH

Compute

$\text{MINCW}\left(G\right)=\underset{\varphi \in {\Lambda }_G}{\min }\text{CW}\left(G\mathrm{,}\varphi \right)$ , where $\text{CW}\left(G,\varphi \right)=\underset{i\in \left\{1,\cdots ,n\right\}}{\max }\theta \left(i,\varphi ,G\right)$ .

Proved in [3]

Vertex separation

VERTSEP

Compute $\text{MINVS}\left(G\right)=\underset{\varphi \in {\Lambda }_G}{\min }\text{VS}\left(G\mathrm{,}\varphi \right)$ , where $\text{VS}\left(G\mathrm{,}\varphi \right)=\underset{i\in \left\{1,\cdots ,n\right\}}{\max }\delta \left(i,\varphi ,G\right)$ .

Proved in [2]

Edge bisection

EDGEBIS

Compute $\text{MINEB}\left(G\right)=\underset{\varphi \in {\Lambda }_G}{\min }\text{EB}\left(G,\varphi \right)$ , where $\text{EB}\left(G,\varphi \right)=\theta \left(\lfloor \frac{n}{2}\rfloor ,\varphi ,G\right)$ .

Proved in [6]

Vertex bisection

VERTBIS

Compute $\text{MINVB}\left(G\right)=\underset{\varphi \in {\Lambda }_G}{\min }\text{VB}\left(G\mathrm{,}\varphi \right)$ , where $\text{VB}\left(G\mathrm{,}\varphi \right)=\delta \left(\lfloor \frac{n}{2}\rfloor \mathrm{,}\varphi \mathrm{,}G\right)$ .

Proved in [5]