Abstract
It is easy to assume that a method guaranteed never to exceed twice the optimum is better than one with no guarantee. This paper compares two methods for vertex cover with the optimum on both random and built graphs. No new theorem or law is claimed.
First, the guarantee holds: taking edges one by one and adding both ends never exceeded twice the optimum on any of $300$ random graphs with $12$ vertices, and gave exactly twice on $6$ disjoint edges (Section 2).
Second, on ordinary graphs, unguaranteed greed wins: at edge probability $0.2$, the guaranteed method averages $\mathbf{1.680857}$ times the optimum and greed, choosing vertices with the most edges, averages $\mathbf{1.030833}$ (Section 2).
Third, and this is the core. On a built graph, greed exceeds twice: with $30$ vertices on the left and blocks of sizes $2$ to $30$ on the right, greed takes $81$ vertices against an optimum of $30$, a ratio of $\mathbf{2.700000}$ (Section 3).
Fourth, on the same graph, the guaranteed method stays at twice: $60$ vertices, a ratio of $2.000000$, within its guarantee (Section 3).
Fifth, built small, greed still wins: with $12$ vertices on the left, greed takes $23$ ($1.916667$ times) and the guaranteed method $24$ ($2.000000$ times) (Section 3).
Sixth, the separator is whether one asks about the average ratio or the worst ratio: the guarantee is a promise about the worst ratio, not about performance on ordinary inputs (Section 4).
Keywords: vertex cover, approximation ratio, greedy algorithm, maximal matching, worst-case ratio.
Scope (what is not claimed)
No new theorem or law is claimed: that finding a minimum vertex cover is generally hard, that taking both ends of a maximal matching never exceeds twice the optimum, and that greed by degree has no constant-factor guarantee, are all known. Hardness proofs are not entered: the theory of how well one can approximate is not entered. Nothing is designed, where to monitor a real network is not stated. Optima only where they can be checked: random graphs had $12$ vertices and were checked exhaustively; the built graphs’ optima were confirmed two ways, by the left vertices covering all edges and by the size of a maximum matching. Relation to earlier papers: Paper 348 showed that on the same graph connecting is cheap and ordering is not, and in its scope note did not enter approximation ratios. This paper takes that seat (no one has taken it before), counting approximation ratios not for touring but for vertex cover. Paper 633 showed that paying largest coins first uses the fewest coins in yen but one too many at 48 pence in old British coins. This paper stands beside it too. There, one input where greed loses was shown. Here, greed wins on average and exceeds twice on a built input. What is added is comparing the averages and maxima of both methods with the optimum on $300$ random graphs, measuring greed at $2.700000$ times on a built graph, confirming the optimum two ways, and placing the separator on average ratio versus worst ratio.
1. Notation and the Question
Setting: a set of vertices containing at least one end of every edge is a vertex cover. We want as few vertices as possible. Two methods are compared.
$$\text{guaranteed}:\ \text{take an edge with neither end chosen, add both ends},\qquad \text{greedy}:\ \text{add the vertex with the most remaining edges}$$In the former, the chosen edges share no ends, so every cover contains one end of each, and the result never exceeds twice the optimum. The latter has no such guarantee. The ratio is the number of chosen vertices divided by the optimum.
Question: is a method guaranteed within twice better than one without a guarantee?
2. Random Graphs
Computation 2.1: with $12$ vertices and varying edge probability, $100$ graphs each were made, the optimum found exhaustively, and both methods’ ratios computed.
| edge probability | guaranteed mean | guaranteed max | greedy mean | greedy max |
|---|---|---|---|---|
| $0.2$ | $1.680857$ | $2.000000$ | $1.030833$ | $1.250000$ |
| $0.35$ | $1.442643$ | $2.000000$ | $1.028857$ | $1.400000$ |
| $0.5$ | $1.386786$ | $1.714286$ | $1.019464$ | $1.142857$ |
Observation 2.2 on ordinary graphs, unguaranteed greed wins. At edge probability $0.2$, the guaranteed method averages $1.680857$ and greed $1.030833$: the guaranteed method never exceeded twice on any of $300$ graphs, and its maximum reached exactly $2.000000$. On $6$ disjoint edges it takes $12$ vertices against an optimum of $6$, exactly twice.
3. A Built Graph
Computation 3.1: $k$ vertices were placed on the left, and for each size $i=2,\dots,k$, $\lfloor k/i\rfloor$ right vertices were each joined to $i$ left vertices. The $k$ left vertices cover every edge and a maximum matching has $k$ edges, so the optimum is $k$.
| $k$ | vertices | edges | optimum | greedy | guaranteed |
|---|---|---|---|---|---|
| $12$ | $35$ | $115$ | $12$ | $23$ ($1.916667$) | $24$ ($2.000000$) |
| $30$ | $111$ | $732$ | $30$ | $81$ ($2.700000$) | $60$ ($2.000000$) |
Observation 3.2 this is the core. On a built graph, greed exceeds twice. At $k=30$, greed chooses $81$ vertices, $2.700000$ times the optimum: a right vertex in a large block always has more remaining edges than any left vertex, so greed keeps choosing right vertices and fills with them what $30$ left vertices would have covered. On the same graph, the guaranteed method takes $60$, within its guarantee.
Observation 3.3 built small, greed still wins. At $k=12$, greed takes $23$ and the guaranteed method $24$, greed one fewer: with the same construction, greed overtakes the guaranteed method only once the blocks are made larger.
4. The Separator
Observation 4.1 the separator is whether one asks about the average ratio or the worst ratio. The guaranteed method promises about the worst case: no input makes it exceed twice. It promises nothing about how good it is on ordinary inputs. Greed has no worst-case promise, yet averages $1.030833$ on random graphs, close to optimal. Which is better switches depending on whether one asks about the average or the worst.
Observation 4.2 taking the seat of Paper 348, and placed beside Paper 633. 348 did not enter approximation ratios in its scope note. Here, approximation ratios for vertex cover are counted, setting guaranteed ratios beside actual ones. 633 showed that paying largest coins first uses one coin too many at $48$ pence in old British coins. Here, greed wins on average and exceeds twice on a built graph.
Observation 4.3 what is not said. Hardness of approximation, how to monitor real networks, and optima of random graphs with $13$ or more vertices are not treated. What is shown is that the average ratio and the worst ratio are different quantities, and they switch which method wins.
5. Census and Closing
- guaranteed within $2$ times (Section 1): chosen edges share no ends.
- all $300$ within twice (Observation 2.2): the guarantee holds.
- exactly twice on $6$ disjoint edges (Observation 2.2): $12$ against $6$.
- guaranteed mean $\mathbf{1.680857}$ (Computation 2.1): edge probability $0.2$.
- greedy mean $\mathbf{1.030833}$ (Computation 2.1): close to optimal.
- greed takes $81$ on the built graph (Computation 3.1): optimum $30$.
- ratio $\mathbf{2.700000}$ (Observation 3.2): the core.
- guaranteed takes $60$ on the same graph (Computation 3.1): twice.
- $23$ against $24$ at $k=12$ (Observation 3.3): greed still wins.
- average ratio, or worst ratio (Observation 4.1): the separator; the seat of Paper 348; Paper 633.
Closing: For vertex cover, the method guaranteed within twice loses to greed on ordinary graphs, and greed exceeds twice on a built graph. On random graphs with $12$ vertices and edge probability $0.2$, the guaranteed method averages $1.680857$ and greed by most edges averages $1.030833$, because the guaranteed method always adds both ends of an edge, including ends that one alone would have covered. On a graph with $30$ vertices on the left and blocks of different sizes on the right, greed takes $81$ vertices against an optimum of $30$ ($2.700000$ times), while the guaranteed method stays at $60$: the guarantee is a promise about the worst ratio, not about average performance. Placed among the earlier papers: we took the approximation-ratio seat left open in Paper 348’s scope note with vertex cover, and placed beside Paper 633’s greed an example where average and worst switch the winner. To be honest: random graphs had only $12$ vertices, and only one construction was built.
References
- Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman.
- Vazirani, V. V. (2001). Approximation Algorithms. Springer.
- Yamagishi, Y. (2026). On the Same Graph, Connecting Is Cheap and Ordering Is Not [Paper 348]. YOI: https://www.yamagishiyuuki.com/yoi/348; DOI: 10.5281/zenodo.22683555
- Yamagishi, Y. (2026). Paying Largest Coins First Always Uses the Fewest Coins in Yen, but One Too Many at 48 Pence in Old British Coins [Paper 633]. YOI: https://www.yamagishiyuuki.com/yoi/633; DOI: 10.5281/zenodo.23014568
Reference
Yamagishi, Y. (2026). For Vertex Cover, the Twice-Guaranteed Method Loses to Greed on Ordinary Graphs, and Greed Exceeds Twice on a Built One [Paper 875]. YOI: https://www.yamagishiyuuki.com/yoi/875
ORCID: 0009-0006-8587-3450
PDF (English) · PDF (Japanese) · Date proof of the English PDF (OpenTimestamps .ots) · SHA256SUMS
The record page for this paper (in Japanese, with the PDFs in each language and the date proof): YOI 875. This paper is a preprint and has not been peer reviewed.