[Rule] KSatisfiability to VertexCover #988
Description
Source: KSatisfiability (K3, i.e., 3-SAT)
Target: VertexCover
Motivation: Classic Garey & Johnson reduction (Theorem 3.3) proving NP-completeness of Vertex Cover from 3-SAT. This gives VertexCover its first incoming reduction and establishes the NP-hardness proof chain. The construction mirrors the existing KSatisfiability → MinimumVertexCover rule, targeting the decision version with threshold k = n + 2m.
Reference: Garey & Johnson, Computers and Intractability, 1979, Theorem 3.3, GT1; Karp (1972).
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, i.e., a subset V' ⊆ V with |V'| ≤ K such that for each edge {u,v} ∈ E at least one of u and v belongs to V'?
Reference: [Karp, 1972]. Transformation from 3-SATISFIABILITY.
Reduction Algorithm
Given a KSatisfiability<K3> instance with n variables x₁, ..., xₙ and m clauses C₁, ..., Cₘ (each with exactly 3 literals), construct a VertexCover instance (G = (V, E), k):
Step 1 — Truth-setting gadgets. For each variable xᵢ (i = 1, ..., n), create two vertices connected by an edge:
- Vertex 2(i−1): positive literal xᵢ
- Vertex 2(i−1)+1: negative literal ¬xᵢ
- Edge: {2(i−1), 2(i−1)+1}
Step 2 — Satisfaction-testing gadgets. For each clause Cⱼ (j = 1, ..., m), create a triangle:
- Vertices: 2n + 3(j−1), 2n + 3(j−1) + 1, 2n + 3(j−1) + 2
- Edges: three edges forming the triangle
Step 3 — Communication edges. For the k-th literal (k = 0, 1, 2) of clause Cⱼ, add an edge from the k-th triangle vertex to the corresponding literal vertex in the truth-setting gadget:
- If literal is xᵢ → connect to vertex 2(i−1)
- If literal is ¬xᵢ → connect to vertex 2(i−1)+1
Step 4 — Threshold. Set k = n + 2m.
Solution extraction. For variable xᵢ: if vertex 2(i−1) (positive literal) is in the cover, set xᵢ = TRUE; otherwise xᵢ = FALSE.
Correctness
(Forward) Given a satisfying assignment, include the TRUE-literal vertex from each variable pair (n vertices) and 2 triangle vertices per clause (the ones NOT connected to the satisfying literal). The satisfying literal's communication edge is covered by its truth-setting vertex. Total = n + 2m = k.
(Backward) Any cover needs ≥ 1 vertex per variable edge and ≥ 2 per triangle, totaling ≥ n + 2m. A cover of exactly k = n + 2m has exactly 1 per variable pair and exactly 2 per triangle. The excluded triangle vertex's communication edge must be covered from the truth-setting side, so the corresponding literal is TRUE.
Size Overhead
| Target metric (code name) | Expression |
|---|---|
num_vertices |
2 * num_vars + 3 * num_clauses |
num_edges |
num_vars + 6 * num_clauses |
Derivation: 2n truth-setting vertices + 3m triangle vertices. n variable edges + 3m triangle edges + 3m communication edges = n + 6m.
Implementation Note
VertexCover currently has 0 outgoing reductions. The companion rule VertexCover → MinimumVertexCover (issue #987) is required for solvability via the MinimumVertexCover → ILP chain.
Example
Source (KSatisfiability):
n = 3 variables (x₁, x₂, x₃), m = 2 clauses:
- C₁ = (x₁ ∨ x₂ ∨ x₃)
- C₂ = (¬x₁ ∨ ¬x₂ ∨ x₃)
Construction:
Truth-setting vertices and edges:
- x₁(0), ¬x₁(1), edge {0,1}
- x₂(2), ¬x₂(3), edge {2,3}
- x₃(4), ¬x₃(5), edge {4,5}
Clause 1 triangle: vertices {6, 7, 8}, edges {6,7}, {7,8}, {6,8}
Clause 1 communication: {6,0} for x₁, {7,2} for x₂, {8,4} for x₃
Clause 2 triangle: vertices {9, 10, 11}, edges {9,10}, {10,11}, {9,11}
Clause 2 communication: {9,1} for ¬x₁, {10,3} for ¬x₂, {11,4} for x₃
Target: VertexCover with 12 vertices, 15 edges, k = 7.
Satisfying assignment: x₁=F, x₂=F, x₃=T
- C₁ = (F ∨ F ∨ T) = T; C₂ = (T ∨ T ∨ T) = T
Vertex cover construction:
- Truth-setting: include ¬x₁(1), ¬x₂(3), x₃(4) — the TRUE-literal vertices
- C₁: x₃ is TRUE, vertex 8's comm edge {8,4} covered by vertex 4. Exclude vertex 8, include {6, 7}
- C₂: ¬x₁ is TRUE, vertex 9's comm edge {9,1} covered by vertex 1. Exclude vertex 9, include {10, 11}
- Cover = {1, 3, 4, 6, 7, 10, 11}, size 7 = k ✓
All 15 edges verified covered.
Non-satisfying check (x₁=F, x₂=F, x₃=F):
- C₁ = (F ∨ F ∨ F) = F. Cover must use ≥ 1 from each variable edge + ≥ 2 from each triangle = n + 2m = 7. But C₁'s triangle has all 3 communication edges going to FALSE-literal vertices, so the excluded triangle vertex's comm edge needs a third truth-setting vertex from C₁'s variable, exceeding the budget.
Validation Method
- Closed-loop test: reduce 3-SAT to VertexCover, solve via VertexCover → MinimumVertexCover → brute force, extract SAT assignment, verify all clauses satisfied
- Test with both satisfiable and unsatisfiable instances
- Verify vertex/edge counts: 2·3 + 3·2 = 12 vertices, 3 + 6·2 = 15 edges ✓
References
- Karp, R. M. (1972). "Reducibility among combinatorial problems." Complexity of Computer Computations, Plenum Press, pp. 85–103.
- Garey, M. R. & Johnson, D. S. (1979). Computers and Intractability, Theorem 3.3, GT1.