4. Задача о наименьшем покрытии
Пусть А — транспонированная матрица смежности графа 
с единичными диагональными элементами. Задача определения наименьшего доминирующего множества графа 
эквивалентна задаче нахождения такого наименьшего множества столбцов в матрице А, что каждая строка матрицы содержит единицу хотя бы в одном из выбранных столбцов. Эта последняя задача о поиске наименьшего множества столбцов, «покрывающих» все строки, изучалась довольно интенсивно под названием задачи о наименьшем покрытии (ЗНП).
В общей ЗНП матрица, состоящая из 
и 1, не обязательно является квадратной. Кроме того, каждому столбцу 
(в нашем случае каждой вершине 
сопоставляется некоторая стоимость 
и требуется выбрать покрытие (или, в другой терминологии — для случая графов — доминирующее множество вершин) с наименьшей общей стоимостью. Поскольку задача построения наименьшего доминирующего множества вершин является весьма частной задачей о покрытии с 
для всех 
то на первый взгляд кажется, что нахождение такого множества осуществляется на деле значительно проще, чем решение общей ЗНП. Однако это, вообще говоря, не так. Поэтому в данном разделе мы начнем с решения общей ЗНП.
4.1. Постановка задачи
ЗНП своим названием обязана следующей теоретико-множественной интерпретации. Даны множество 
и семейство 
множеств 
Любое подсемейство 
семейства 
, такое, что
называется покрытием множества 
а множества 
называются покрывающими множествами. Если в дополнение к соотношению (3.12) удовлетворяет условию
т. е. множества 
попарно не пересекаются, то 
называется разбиением множества 
Если каждому 
поставлена в соответствие (положительная) стоимость 
то ЗНП формулируется так: найти покрытие множества 
имеющее наименьшую стоимость, причем стоимость семейства — 
определяется как 
Аналогично формулируется и задача о наименьшем разбиении (ЗНР).
В матричной форме, упомянутой ранее, когда строки 
-матрицы 
состоящей из нулей и единиц, покрываются столбцами, ЗНП может быть сформулирована как задача линейного программирования:
при ограничениях 
где
и
Для ЗНР неравенства (3.14) обращаются в равенства
