Число вершинного покрытия

Число вершинного покрытия графа ${\displaystyle G}$ — размер наименьшего вершинного покрытия в нём.

Поскольку задача о вершинном покрытии является NP-полной, то, к сожалению, неизвестны алгоритмы определения числа вершинного покрытия в произвольном графе, работающие за полиномиальное время.

В любом графе ${\displaystyle G=(V,E)}$ число вершинного покрытия ${\displaystyle \tau (G)}$ связано с числом независимости ${\displaystyle \alpha (G)}$ первым тождеством Галлаи: ${\displaystyle \alpha (G)+\tau (G)=|V|}$, более того, дополнение к наименьшему вершинному покрытию является наибольшим независимым множеством вершин.

В любом графе ${\displaystyle G}$ также справедливо неравенство ${\displaystyle \tau (G)\geq \nu (G)}$, где ${\displaystyle \nu (G)}$ — число паросочетания графа ${\displaystyle G}$. В двудольном графе ${\displaystyle G}$, вследствие Теоремы Кёнига, ${\displaystyle \tau (G)=\nu (G)}$. Поэтому в двудольных графах задача определения ${\displaystyle \tau (G)}$ решается за полиномиальное время.