8.1. The Vertex Cover Problem

Consider a computer network whose traffic we want to monitor in order to protect against attacks. We are required to observe every packet sent across any link in the network. An easy way to ensure this is to place a monitoring appliance on every network node. The appliance placed on a node now monitors the packets arriving at and leaving from this node. Clearly, this ensures that we observe every packet. However, these appliances are costly and intrusive. Thus, we would like to minimize the number of appliances we install. There is no need to place appliances on all nodes; it suffices to ensure that every link has at least one endpoint with an appliance on it. This idea is formalized as follows:

Given an undirected graph \(G = (V, E)\), a vertex cover of \(G\) is a subset of vertices \(C \subseteq V\) such that every edge in \(E\) has at least one endpoint in \(C\). See Figure 8.1.

Figure 8.1: Coming soon!

Vertex cover problem: Given a graph \(G = (V, E)\),find a vertex cover of minimum size or, if the vertices have weights, of minimum weight.

This is a classical NP-hard problem, so it cannot be solved exactly in polynomial time unless \(\textrm{P} = \textrm{NP}\).