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

Число вершинного покриття графа $G$ — розмір найменшого вершинного покриття в ньому.

Оскільки задача вершинного покриття є NP-повною, то невідомі алгоритми визначення числа вершинного покриття в довільному графі, що працюють за поліноміальний час.

У будь-якому графі $G=(V,E)$ число вершинного покриття $\tau (G)$ пов'язане з числом незалежності $\alpha (G)$ першою тотожністю Галлаї: $\alpha (G)+\tau (G)=|V|$, більш того, доповнення до найменшого вершинного покриття є найбільшою незалежною множиною вершин.

У будь-якому графі $G$ також виконується нерівність $\tau (G)\geq \nu (G)$, де $\nu (G)$ — число парування графа $G$. У двочастковому графі $G$, внаслідок теореми Кеніга, $\tau (G)=\nu (G)$. Тому в двочасткових графах задача визначення $\tau (G)$ розв'язується за поліноміальний час.

Посилання

• László Lovász, Michael D. Plummer. Matching Theory. — North-Holland, 1986. — ISBN 0-444-87916-1.