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 CUT COVER

• INSTANCE: Graph $G=\left(V,E\right)$.
• SOLUTION: A collection $V_1, \ldots, V_m$ of cuts, i.e., a collection of subsets $V_i \subseteq V$ such that, for each edge $(u,v) \in E$, a subset $V_i$ exists such that either $u \in V_i$ and $v \not\in V_i$ or $u \not\in V_i$ and $v \in V_i$.
• MEASURE: Cardinality of the collection, i.e., m.

  
  

• Good News: Approximable within $1+(\log\vert V\vert-3\log\log\vert V\vert)/\mbox{\sl opt}(G)$ [381].
• Bad News: There is no polynomial-time algorithm with relative error less than 1.5 [381].
• Comment: The negative result is obtained by relating the problem with the coloring problem. Solvable in polynomial time for planar graphs. Observe that any graph has a cut cover of cardinality $\lceil \log\vert V\vert \rceil$.