5
$\begingroup$

Let $G=(V,E)$ be a finite, simple, undirected graph. A matching is a set $M\subseteq E$ of pairwise disjoint edges. A vertex cover is a set $C\subseteq V$ of vertices such that $C\cap e \neq \emptyset$ for all $e\in E$.

The matching number $\mu(G)$ of $G$ is the maximum size that a matching can have, and the vertex cover number $\tau(G)$ is the minimum size that a vertex cover can have.

If $M$ is a maximal matching with respect to $\subseteq$, then $C=\bigcup M$ is a vertex cover by maximality of $M$, and $|C|=2|M|$, so we have $\tau(G)\leq 2\cdot \mu(G)$ for all graphs $G$.

Question. What is the value of $$\inf\{c\in \mathbb{R}: \tau(G)\leq c\cdot \mu(G) \text{ for all finite graphs } G\}?$$

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

Minimum $c$ equals 2 as is seen from the complete graph on a large number $n$ of vertices: $\tau$ equals $n-1$, $\mu$ equals $[n/2]$.

Improve this answer
$\endgroup$
1
$\begingroup$

The value is 2. (This is the integrality gap of the LP relaxation of vertex cover. See Frankl–Rödl graph on Wikipedia for a graph for which the integrality gap of the SDP relaxation is still 2.)

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .