Yamagishi Complexity Torus Lab | 山岸勇輝ラボ

論文875 の記録のページです。住所（YOI）は https://www.yamagishiyuuki.com/yoi/875 で、論文の本文は下の PDF にあります。ファイルは自分で用意した置き場所（https://yamagishi.sakuraweb.com）に置き、日付の証拠（.ots）を添えています。

本文はサイトの記事でも読めます（2026年10月7日 16:50 に公開します）。

@misc{yamagishi2026yoi875,
  author = {Yamagishi, Yuuki},
  title = {For Vertex Cover, the Twice-Guaranteed Method Loses to Greed on Ordinary Graphs, and Greed Exceeds Twice on a Built One},
  year = {2026},
  howpublished = {YOI: https://www.yamagishiyuuki.com/yoi/875},
  note = {Preprint, edition 1}
}

日付の証拠（OpenTimestamps）

2026年10月1日に、2 本の PDF の指紋（SHA-256）をまとめて OpenTimestamps に送り、ビットコインのブロック 969440・969456・969461 に記録されました（2026年10月01日 19:28（日本時間））。この .ots があれば、PDF がその時点で存在したことを、このサイトや運営者を信用しなくても、誰でも確かめられます。

書誌

要旨

最適の二倍を超えないと保証された方法は、保証の無い方法より良い、と思いやすい。本稿は、頂点被覆で二つの方法を、無作為なグラフと作ったグラフの両方で最適と比べる。新しい定理も法則も主張しない。

第一に、保証は守られる。辺を一本ずつ取って両端を入れる方法は、点 $12$ 個の無作為なグラフ $300$ 個のどれでも最適の $2$ 倍を超えず、互いに離れた $6$ 本の辺ではちょうど $2$ 倍になった（第2節）。

第二に、ふつうのグラフでは、保証の無い貪欲が勝つ。辺の確率 $0.2$ で、二倍を保証する方法は平均 $\mathbf{1.680857}$ 倍、辺の多い点から選ぶ貪欲は平均 $\mathbf{1.030833}$ 倍である（第2節）。

第三に、これが本稿の芯である。作ったグラフでは、貪欲が二倍を超える。左に $30$ 点、右に大きさ $2$ から $30$ の塊を並べたグラフで、最適 $30$ 点に対して貪欲は $81$ 点、比 $\mathbf{2.700000}$ である（第3節）。

第四に、同じグラフで、二倍を保証する方法は $2$ 倍にとどまる。$60$ 点、比 $2.000000$ で、保証の範囲に入る（第3節）。

第五に、小さく作ると、まだ貪欲が勝つ。同じ作り方で左を $12$ 点にすると、貪欲は $23$ 点（$1.916667$ 倍）、二倍を保証する方法は $24$ 点（$2.000000$ 倍）である（第3節）。

第六に、分離子は、平均の比を問うか、最悪の比を問うかである。保証は最悪の比についての約束で、ふつうの入力での出来は約束していない（第4節）。

キーワード：頂点被覆、近似比、貪欲法、極大マッチング、最悪の比

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

版の記録

ここの PDF（倉庫の v1）は第1版（2026年9月）の原稿から作りました。ファイルは版ごとに分けて置いています（/yoi/875/v1/ の下）。中身を直すときは、このファイルを書き換えず、新しい版を足します（住所 https://www.yamagishiyuuki.com/yoi/875 はいつも最新の版を指します）。

YOI の一覧へ