vertex cover

abbr: vc

functionally equivalent to: maximum matching, distance to edgeless

Definition: The minimum number of vertices that have to be removed to get an independent set.

Vertex cover is perhaps the simplest but useful parameter. Although the graph class of bounded vertex cover is small, it is often the first parameter for which we aim to design an FPT algorithm. Vertex cover can be easily 2-approximated in polynomial time.

From the definition, we see the graph of vertex cover $k$ can be partitioned into a modulator of size $k$ and an independent set. The edges here can be only between the vertices of the moduator or from the modulator to the independent set.

FPT algorithms often exploit the fact that vertices of the independent set can be partitioned into $2^k$ groups based on their neighborhood in the modulator. Now, one can either enumerate all the solutions or notice that whenever a part contains too many vertices we can ignore the vast majority of them as they do not influence the solution.

Relations

Other		Relation from	Relation to
acyclic chromatic number	red■	exclusion	upper bound
admissibility	red■	exclusion	upper bound
arboricity	red■	exclusion	upper bound
average degree	red■	exclusion	upper bound
average distance	red■	exclusion	upper bound
bandwidth	blue■	exclusion	exclusion
bipartite	blue■	unbounded	exclusion
bipartite number	blue■	exclusion	exclusion
bisection bandwidth	blue■	exclusion	exclusion
block	blue■	unbounded	exclusion
book thickness	red■	exclusion	upper bound
boolean width	red■	exclusion	upper bound
bounded components	blue■	exclusion	exclusion
bounded expansion	red■	exclusion	upper bound
boxicity	red■	exclusion	upper bound
branch width	red■	exclusion	upper bound
c-closure	blue■	exclusion	exclusion
carving-width	blue■	exclusion	exclusion
chi-bounded	red■	exclusion	upper bound
chordal	blue■	unbounded	exclusion
chordality	red■	exclusion	upper bound
chromatic number	red■	exclusion	upper bound
clique cover number	blue■	exclusion	exclusion
clique-tree-width	red■	exclusion	upper bound
clique-width	red■	exclusion	upper bound
cluster	blue■	unbounded	exclusion
co-cluster	blue■	unbounded	exclusion
cograph	blue■	unbounded	exclusion
complete	blue■	unbounded	exclusion
connected	blue■	exclusion	avoids
contraction complexity	blue■	exclusion	exclusion
cutwidth	blue■	exclusion	exclusion
cycle	cyan■	unknown to HOPS	exclusion
cycles	blue■	unbounded	exclusion
d-admissibility	red■	exclusion	upper bound
d-path-free	red■	exclusion	upper bound
degeneracy	red■	exclusion	upper bound
degree treewidth	blue■	exclusion	exclusion
diameter	red■	exclusion	upper bound
diameter+max degree	blue■	exclusion	exclusion
distance to bipartite	red■	exclusion	upper bound
distance to block	red■	exclusion	upper bound
distance to bounded components	red■	exclusion	upper bound
distance to chordal	red■	exclusion	upper bound
distance to cluster	red■	exclusion	upper bound
distance to co-cluster	red■	exclusion	upper bound
distance to cograph	red■	exclusion	upper bound
distance to complete	blue■	exclusion	exclusion
distance to edgeless	yellow■	equal	equal
distance to forest	red■	exclusion	upper bound
distance to interval	red■	exclusion	upper bound
distance to linear forest	red■	exclusion	upper bound
distance to maximum degree	red■	exclusion	upper bound
distance to outerplanar	red■	exclusion	upper bound
distance to perfect	red■	exclusion	upper bound
distance to planar	red■	exclusion	upper bound
distance to stars	red■	exclusion	upper bound
domatic number	red■	exclusion	upper bound
domination number	blue■	exclusion	exclusion
domino treewidth	blue■	exclusion	exclusion
edge clique cover number	blue■	exclusion	exclusion
edge connectivity	red■	exclusion	upper bound
edge-cut width	magenta■	exclusion	unknown to HOPS
edge-treewidth	magenta■	exclusion	unknown to HOPS
edgeless	green■	upper bound	avoids
excluded minor	magenta■	exclusion	unknown to HOPS
excluded planar minor	gray■	unknown to HOPS	unknown to HOPS
excluded top-minor	red■	exclusion	upper bound
feedback edge set	blue■	exclusion	exclusion
feedback vertex set	red■	exclusion	upper bound
flip-width	red■	exclusion	upper bound
forest	blue■	unbounded	exclusion
genus	blue■	exclusion	exclusion
grid	blue■	unbounded	exclusion
h-index	red■	exclusion	upper bound
interval	blue■	unbounded	exclusion
iterated type partitions	red■	exclusion	upper bound
linear clique-width	red■	exclusion	upper bound
linear forest	blue■	unbounded	exclusion
linear NLC-width	red■	exclusion	upper bound
linear rank-width	red■	exclusion	upper bound
maximum clique	red■	exclusion	upper bound
maximum degree	blue■	exclusion	exclusion
maximum independent set	blue■	exclusion	exclusion
maximum induced matching	red■	exclusion	upper bound
maximum leaf number	cyan■	unknown to HOPS	exclusion
maximum matching	yellow■	upper bound	tight bounds
maximum matching on bipartite graphs	green■	tight bounds	exclusion
merge-width	red■	exclusion	upper bound
mim-width	red■	exclusion	upper bound
minimum degree	red■	exclusion	upper bound
mm-width	red■	exclusion	upper bound
modular-width	red■	exclusion	upper bound
module-width	red■	exclusion	upper bound
monadically dependent	red■	exclusion	upper bound
monadically stable	red■	exclusion	upper bound
neighborhood diversity	red■	exclusion	upper bound
NLC-width	red■	exclusion	upper bound
NLCT-width	red■	exclusion	upper bound
nowhere dense	red■	exclusion	upper bound
odd cycle transversal	red■	exclusion	upper bound
outerplanar	cyan■	unknown to HOPS	exclusion
overlap treewidth	magenta■	exclusion	unknown to HOPS
path	blue■	unbounded	exclusion
pathwidth	red■	exclusion	upper bound
pathwidth+maxdegree	blue■	exclusion	exclusion
perfect	blue■	unbounded	exclusion
planar	blue■	unbounded	exclusion
radius-inf flip-width	red■	exclusion	upper bound
radius-r flip-width	red■	exclusion	upper bound
rank-width	red■	exclusion	upper bound
series-parallel	gray■	unknown to HOPS	unknown to HOPS
shrub-depth	red■	exclusion	upper bound
sim-width	red■	exclusion	upper bound
size	green■	upper bound	exclusion
slim tree-cut width	magenta■	exclusion	unknown to HOPS
sparse twin-width	red■	exclusion	upper bound
star	green■	upper bound	exclusion
stars	blue■	unbounded	exclusion
strong coloring number	red■	exclusion	upper bound
strong d-coloring number	red■	exclusion	upper bound
strong inf-coloring number	red■	exclusion	upper bound
topological bandwidth	blue■	exclusion	exclusion
tree	blue■	unbounded	exclusion
tree-cut width	magenta■	exclusion	unknown to HOPS
tree-independence number	red■	exclusion	upper bound
tree-partition-width	magenta■	exclusion	unknown to HOPS
treebandwidth	magenta■	exclusion	unknown to HOPS
treedepth	red■	exclusion	upper bound
treelength	red■	exclusion	upper bound
treespan	blue■	exclusion	exclusion
treewidth	red■	exclusion	upper bound
twin-cover number	red■	exclusion	upper bound
twin-width	red■	exclusion	upper bound
vertex connectivity	gray■	unknown to HOPS	unknown to HOPS
vertex cover	yellow■	equal	equal
vertex integrity	red■	exclusion	upper bound
weak coloring number	red■	exclusion	upper bound
weak d-coloring number	red■	exclusion	upper bound
weak inf-coloring number	red■	exclusion	upper bound
weakly sparse	red■	exclusion	upper bound
weakly sparse and merge width	red■	exclusion	upper bound

Results

2025 On a tree-based variant of bandwidth and forbidding simple topological minors by Jacob, Lochet, Paul
- page 36 : vertex cover upper and lower bounds maximum matching by a linear function – … discovered independently by Fanica Gavril and Mihalis Yannakakis. Theorem 50. In a graph $G$, we have $\mu(G) \le {\rm vc}(G) \le 2\mu(G)$, where $\mu(G)$ is the maximum matching number of $G$.
- page 36 : maximum matching upper bounds vertex cover by a linear function – … discovered independently by Fanica Gavril and Mihalis Yannakakis. Theorem 50. In a graph $G$, we have $\mu(G) \le {\rm vc}(G) \le 2\mu(G)$, where $\mu(G)$ is the maximum matching number of $G$.
2022 Expanding the Graph Parameter Hierarchy by Tran
- page 18 : vertex cover upper bounds twin-cover number by a linear function – By definition
- page 18 : graph class complete is not constant vertex cover – Note that a clique of size $n$ has … a vertex cover number of $n-1$
- page 23 : vertex cover upper bounds neighborhood diversity by an exponential function – Proposition 4.3. Vertex Cover Number strictly upper bounds Neighborhood Diversity.
- page 23 : graph classes with bounded neighborhood diversity are not bounded vertex cover – Proposition 4.3. Vertex Cover Number strictly upper bounds Neighborhood Diversity.
- page 29 : graph classes with bounded edge clique cover number are not bounded vertex cover – Proposition 4.13. Edge Clique Cover Number is incomparable to Vertex Cover Number.
- page 29 : graph classes with bounded vertex cover are not bounded edge clique cover number – Proposition 4.13. Edge Clique Cover Number is incomparable to Vertex Cover Number.
- page 34 : graph classes with bounded c-closure are not bounded vertex cover – Proposition 5.3. $c$-Closure is incomparable to Vertex Cover Number.
- page 34 : graph classes with bounded vertex cover are not bounded c-closure – Proposition 5.3. $c$-Closure is incomparable to Vertex Cover Number.
2012 Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics by Ganian
- page 263 : graph classes with bounded twin-cover number are not bounded vertex cover – The vertex cover of graphs of bounded twin-cover may be arbitrarily large.
unknown source
- maximum matching on bipartite graphs upper and lower bounds vertex cover by a linear function – Kőnig’s theorem
- vertex cover upper bounds neighborhood diversity by an exponential function
- vertex cover is equivalent to distance to edgeless
- distance to edgeless is equivalent to vertex cover
- edgeless upper bounds vertex cover by a constant
- star upper bounds vertex cover by a constant – trivially
assumed
- vertex cover upper bounds twin-cover number by a linear function – By definition
- size upper bounds vertex cover by a linear function – By definition
- vertex cover is equivalent to vertex cover – assumed
Comparing Graph Parameters by Schröder
- page 15 : graph classes with bounded vertex cover are not bounded domination number – Proposition 3.5
- page 24 : graph classes with bounded vertex cover are not bounded genus – Proposition 3.18
- page 24 : graph classes with bounded vertex cover are not bounded maximum degree – Proposition 3.19
- page 24 : graph classes with bounded vertex cover are not bounded bisection bandwidth – Proposition 3.20