[Rule] VertexCover to MinimumVertexCover

[isPANN]

Source: VertexCover
Target: MinimumVertexCover
Motivation: Provides a solvability path for VertexCover through the existing MinimumVertexCover → ILP chain. Standard reduction from a decision problem to its optimization counterpart: "does G have a vertex cover of size ≤ k?" is answered by computing the minimum vertex cover and comparing its weight to k.
Reference: Standard folklore; Garey & Johnson, Computers and Intractability, GT1.

GJ Source Entry

[GT1] VERTEX COVER
INSTANCE: Graph G = (V, E), positive integer K ≤ |V|.
QUESTION: Is there a vertex cover of size K or less for G?

The optimization version (MinimumVertexCover) finds a minimum-weight vertex cover. With unit weights, the minimum weight equals the minimum cardinality.

Reduction Algorithm

Given a VertexCover instance (G = (V, E), k), construct a MinimumVertexCover instance:

Step 1. Set G' = G (same graph — identical vertices and edges).

Step 2. Set w(v) = 1 for all v ∈ V (unit weights).

The variable mapping is the identity: source config[i] = target config[i].

Solution extraction. Given the MVC optimal configuration c* with optimal value val*:

• If val* ≤ k: return c* as the VertexCover witness (valid cover of size ≤ k)
• If val* > k: no vertex cover of size ≤ k exists (VertexCover answer is NO/false)

Correctness

(Forward) Any vertex cover of size ≤ k in G is also a unit-weight cover of weight ≤ k in G' = G. So the MVC optimum val* ≤ k, and the MVC witness is a valid VertexCover witness.

(Backward) If the MVC optimum val* > k, then no cover of cardinality ≤ k exists (since unit weights make weight = cardinality), correctly yielding NO.

Size Overhead

Target metric (code name)	Expression
num_vertices	num_vertices
num_edges	num_edges

Derivation: The graph is copied unchanged. Unit weights are added but do not affect graph size metrics.

Example

Source (VertexCover):
Graph G with 5 vertices {0, 1, 2, 3, 4}, 5 edges forming a 5-cycle:

• Edges: {0,1}, {1,2}, {2,3}, {3,4}, {0,4}
• k = 3

Target (MinimumVertexCover):
Same graph, weights = [1, 1, 1, 1, 1].

MVC optimal: Cover {0, 2, 3}, weight = 3.

• Covers: {0,1}(0✓), {1,2}(2✓), {2,3}(2✓ or 3✓), {3,4}(3✓), {0,4}(0✓). All 5 edges covered.
• val* = 3 ≤ k = 3 → VertexCover answer is YES.

Extracted config: [1, 0, 1, 1, 0] → cover {0, 2, 3}, size 3 ≤ 3 ✓

NO instance: Same 5-cycle graph with k = 2.

• MVC optimal is still 3 (a 5-cycle requires ⌈5/2⌉ = 3 vertices to cover all edges).
• val* = 3 > k = 2 → VertexCover answer is NO.

Larger YES instance: Graph with 6 vertices, edges {0,1}, {0,2}, {1,2}, {2,3}, {3,4}, {3,5}, {4,5} (two triangles sharing vertex 2–3 bridge), k = 4.

• MVC optimal: {0, 2, 3, 4}, weight = 4 ≤ k = 4 → YES.
• Covers all 7 edges: {0,1}(0✓), {0,2}(0✓ or 2✓), {1,2}(2✓), {2,3}(2✓ or 3✓), {3,4}(3✓ or 4✓), {3,5}(3✓), {4,5}(4✓).

Validation Method

• Closed-loop test: construct VertexCover instance, reduce to MinimumVertexCover, solve MVC via brute force, extract solution, verify VertexCover evaluate returns correct answer
• Test both YES instances (optimal ≤ k) and NO instances (optimal > k)
• Verify vertex/edge counts match overhead formulas (identity)

References

• Garey, M. R. & Johnson, D. S. (1979). Computers and Intractability, GT1.

[GiggleLiu]

fix-issue changelog: Rewrote issue body with identity-graph + unit-weight construction. Added YES/NO examples on 5-cycle (k=3 YES, k=2 NO) and 6-vertex two-triangle graph (k=4 YES). Solution extraction: return MVC witness if optimal ≤ k, NO otherwise. Overhead is identity (num_vertices, num_edges unchanged).