Isolationsprobleme

Isolationsprobleme, in graph-theoretic context often called the isolation problem, concerns finding a smallest set of vertices whose removal leaves a graph with no edges. The resulting remaining vertices are all isolated. The size of such a set is called the isolation number i(G). This quantity is equivalent to the size of a minimum vertex cover τ(G), because removing a vertex cover eliminates every edge, leaving an edgeless graph. Thus the isolationsproblem is largely a reformulation of the classical vertex cover problem.

Formal definition: Given a simple graph G = (V,E), determine a subset S ⊆ V of minimum cardinality such that G − S has no edges. Equivalently, S touches every edge of G.

Variants of the problem may ask to isolate a specific subset of vertices, or to optimize related objectives in directed or weighted graphs. In some contexts, researchers study bounds, exact values for special graph classes, and how the isolation number relates to other graph invariants such as domination, matching, or independence numbers.

Computational aspects: The isolationsproblem is NP-hard in general graphs because it is equivalent to minimum vertex cover. It is solvable in polynomial time for bipartite graphs via maximum matching, and linear-time solvable on trees by dynamic programming. In practice, practitioners use exact methods (branch-and-bound, integer programming) and fixed-parameter tractable algorithms with the isolation number as the parameter, as well as approximation and kernelization techniques.

Applications include network reliability and rescue planning, facility placement, and models of containment or quarantine, where isolating nodes effectively disconnects interactions and limits spread. See also vertex cover, edge cover, and domination.