Name | Label | Problem | NP-hardness |
Cutwidth | CUTWIDTH | Compute , where . | Proved in [3] |
Vertex separation | VERTSEP | Compute , where . | Proved in [2] |
Edge bisection | EDGEBIS | Compute , where . | Proved in [6] |
Vertex bisection | VERTBIS | Compute , where . | Proved in [5] |