[Rule] VertexCover to MinimumVertexCover

[isPANN]

Source

VertexCover (proposed in #986)

Target

MinimumVertexCover

Motivation

Provides a solvability path for VertexCover through the existing MinimumVertexCover → ILP chain. This is the standard reduction from a decision problem to its optimization counterpart.

Reference

Standard folklore reduction between decision and optimization versions of Vertex Cover.

Reduction Algorithm

Notation:

• Source: VertexCover instance with graph G = (V, E) and threshold k
• Target: MinimumVertexCover instance with graph G' = (V', E') and weights w

Construction:

1. Set G' = G (same graph, same vertices and edges).
2. Set w(v) = 1 for all v ∈ V (unit weights).
3. The variable mapping is the identity: source variable x_i maps to target variable x_i.

Correctness: MinimumVertexCover finds a minimum-weight vertex cover. With unit weights, the minimum weight equals the minimum cardinality. VertexCover's evaluate function checks both "is a valid cover" and "size ≤ k", so a minimum cover of size > k correctly yields NO.

Size Overhead

Target metric	Formula
num_vertices	num_vertices
num_edges	num_edges

Validation Method

Closed-loop test: construct VertexCover instance, reduce to MinimumVertexCover, solve MVC via brute force, extract solution, verify VertexCover evaluate returns correct answer for both YES and NO instances.

Example

1. Source instance: VertexCover on graph with 4 vertices {0,1,2,3}, edges {0,1},{1,2},{0,2},{2,3}, k=2.

2. Construction: MinimumVertexCover on the same graph with weights [1,1,1,1].

3. Target instance: MinimumVertexCover with 4 vertices, 4 edges, unit weights.

   • MVC optimal solution: {0, 2}, weight = 2.
   • Extracted VertexCover config: [1, 0, 1, 0] → cover {0, 2}, size 2 ≤ k=2 → YES.

BibTeX

@book{GareyJohnson1979,
  author    = {Michael R. Garey and David S. Johnson},
  title     = {Computers and Intractability: A Guide to the Theory of NP-Completeness},
  publisher = {W.H. Freeman},
  year      = {1979},
}