Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)

Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)

MINIMUM VERTEX K-CUT

• INSTANCE: Graph $G=\left(V,E\right)$, a set $S=\{s_1,t_1,\ldots,s_k,t_k\}$ of special vertices, and a weight function $w:V-S\rightarrow N$, and an integer k.

• SOLUTION: A vertex k-cut, i.e., a subset $C\subseteq V-S$ of vertices such that their deletion from G disconnects each $s_i$ from $t_i$ for $1\le i\le k$.

• MEASURE: The sum of the weight of the vertices in the cut, i.e., $$\sum_{v\in C} w(v)$$.

  
  

• Good News: Approximable within $O(\log \vert V\vert)$ [188].