Alex's Notes

❯

❯

Vertex cover

Nov 03, 20231 min read

maths
graph-theory

Vertex cover

Given an undirected graph a set is a vertex cover if for all we have or .

Graph View

Backlinks

Week 10 - Graph problem complexity
Minimum vertex cover problem is NP-hard
Minimum vertex cover problem
Vertex cover if and only if the complement is an independent set
Vertex cover of a given size is NP-complete
Vertex cover of a given size is NP
Vertex cover of a given size

Created with Quartz v4.5.1 © 2025

GitHub
Discord Community