Minimum Number of Managers

Initializing live version
Download to Desktop

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.

A group of workers (labeled 1 to ) interact in pairs, as shown by a line between them. Any worker can be a manager, and for each red line, at least one must be a manager. The task is to find a minimum number of managers. Try this heuristic: at each stage, choose a person with a maximal number of links. The special case is provided to show that this heuristic does not always work.

Contributed by: Izidor Hafner (March 2013)
Open content licensed under CC BY-NC-SA



In graph theory, this is known as the minimum vertex cover problem.


[1] S. Permmaraju and S. Skiena, Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica, New York: Cambridge University Press, 2003 pp. 317–318.

Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.