[Rule] Vertex Cover to Ensemble Computation

Source: VERTEX COVER
Target: ENSEMBLE COMPUTATION
Motivation: Establishes NP-completeness of ENSEMBLE COMPUTATION by encoding vertex-cover selection as a sequence of disjoint-union operations, where each "a₀-augmented" vertex z_i = {a₀} ∪ {v} corresponds to including vertex v in the cover and each edge subset is built by combining the appropriate cover vertex with its non-cover neighbor.

Reference: Garey & Johnson, Computers and Intractability, Appendix Problem PO9

Reduction Algorithm

ENSEMBLE COMPUTATION
INSTANCE: A collection C of subsets of a finite set A and a positive integer J.
QUESTION: Is there a sequence

< z_1 = x_1 ∪ y_1, z_2 = x_2 ∪ y_2, . . . , z_j = x_j ∪ y_j >

of j ≤ J union operations, where each x_i and y_i is either {a} for some a ∈ A or z_k for some k < i, such that x_i and y_i are disjoint for 1 ≤ i ≤ j and such that for every subset c ∈ C there is some z_i, 1 ≤ i ≤ j, that is identical to c ?

ENSEMBLE COMPUTATION is NP-complete. (Appendix PO9)
Proof: We transform VERTEX COVER to ENSEMBLE COMPUTATION. Let the graph G = (V,E) and the positive integer K ≤ |V| constitute an arbitrary instance of VC.

The basic units of the instance of VC are the edges of G. Let a_0 be some new element not in V. The local replacement just substitutes for each edge {u,v} ∈ E the subset {a_0,u,v} ∈ C. The instance of ENSEMBLE COMPUTATION is completely specified by:
A = V ∪ {a_0}
C = {{a_0,u,v}: {u,v} ∈ E}
J = K + |E|
It is easy to see that this instance can be constructed in polynomial time. We claim that G has a vertex cover of size K or less if and only if the desired sequence of j ≤ J operations exists for C.

First, suppose V' is a vertex cover for G of size K or less. Since we can add additional vertices to V' and it will remain a vertex cover, there is no loss of generality in assuming that |V'| = K. Label the elements of V' as v_1,v_2, . . . , v_K and label the edges in E as e_1,e_2, . . . , e_m, where m = |E|. Since V' is a vertex cover, each edge e_j contains at least one element from V'. Thus we can write each e_j as e_j = {u_j,v_{r[j]}}, where r[j] is an integer satisfying 1 ≤ r[j] ≤ K. The following sequence of K + |E| = J operations is easily seen to have all the required properties:
< z_1 = {a_0} ∪ {v_1}, z_2 = {a_0} ∪ {v_2}, . . . , z_k = {a_0} ∪ {v_K},
  z_{K+1} = {u_1} ∪ z_{r[1]}, z_{K+2} = {u_2} ∪ z_{r[2]}, . . . , z_J = {u_m} ∪ z_{r[m]} >
Conversely, suppose S = < z_1 = x_1 ∪ y_1, . . . , z_j = x_j ∪ y_j > is the desired sequence of j ≤ J operations for the ENSEMBLE COMPUTATION instance. Furthermore, let us assume that S is the shortest such sequence for this instance and that, among all such minimum sequences, S contains the fewest possible operations of the form z_i = {u} ∪ {v} for u, v ∈ V. Our first claim is that S can contain no operations of this latter form. For suppose that z_i = {u} ∪ {v} with u,v ∈ V is included. Since {u,v} is not in C and since S has minimum length, we must have {u,v} ∈ E, and {a_0,u,v} = {a_0} ∪ z_i (or z_i ∪ {a_0}) must occur later in S. However, since {u,v} is a subset of only one member of C, z_i cannot be used in any other operation in this minimum length sequence. It follows that we can replace the two operations
z_i = {u} ∪ {v}  and  {a_0,u,v} = {a_0} ∪ z_i
by
z_i = {a_0} ∪ {u}  and  {a_0,u,v} = {v} ∪ z_i
thereby reducing the number of proscribed operations without lengthening the overall sequence, a contradiction to the choice of S. Hence S consists only of operations having one of the two forms, z_i = {a_0} ∪ {u} for u ∈ V or {a_0,u,v} = {v} ∪ z_i for {u,v} ∈ E (where we disregard the relative order of the two operands in each case). Because |C| = |E| and because every member of C contains three elements, S must contain exactly |E| operations of the latter form and exactly j−|E| ≤ J−|E| = K of the former. Therefore the set
V' = {u ∈ V: z_i = {a_0} ∪ {u} is an operation in S}
contains at most K vertices from V and, as can be verified easily from the construction of C, must be a vertex cover for G. ∎

Summary:
Given a MinimumVertexCover instance with graph G = (V, E), construct an EnsembleComputation instance as follows:

Universe construction: Let a₀ be a fresh element not in V. Set A = V ∪ {a₀}. The universe has |V| + 1 elements.
Collection construction: For each edge {u, v} ∈ E, add the 3-element subset {a₀, u, v} to C. Each edge becomes exactly one required subset. The collection has |C| = |E| subsets.
Budget parameter: Set the budget field J = K + |E| in the EnsembleComputation instance. The EnsembleComputation model is a decision/feasibility problem (Value = Or): it answers whether all subsets in C can be built within J union operations. The EC instance evaluates to Or(true) if and only if G has a vertex cover of size ≤ K.
Implementation note: Since MinimumVertexCover is a pure optimization problem (Value = Min<W::Sum>) with no explicit budget field K, the reduce_to() implementation uses the upper-bound budget J = num_vertices + num_edges (since K* ≤ |V| always). This ensures the EC instance is always valid and satisfiable (Or(true) for any non-trivially-covered graph). Witness extraction recovers a valid — though not necessarily minimum — vertex cover from the sequence.
Solution extraction: Given a satisfying sequence of j ≤ J operations, the cover vertices are exactly those vertices u ∈ V such that z_i = {a₀} ∪ {u} appears in the sequence. These form a valid vertex cover.

Key invariant: EC with budget J = K + |E| is satisfiable (Or(true)) iff G has a vertex cover of size ≤ K. With the upper-bound budget J = |V| + |E|, the EC instance is always satisfiable for any connected graph, but the extracted witness is a valid (not necessarily minimum) vertex cover.

Size Overhead

Symbols:

n = num_vertices of source graph G
m = num_edges of source graph G

Target metric (code name)	Polynomial (using symbols above)
`universe_size`	`num_vertices + 1`
`num_subsets`	`num_edges`

Derivation:

Universe A = V ∪ {a₀}: one element per vertex plus the fresh element a₀ → |A| = n + 1
Collection C: one 3-element subset per edge in G → |C| = m
Budget field: The budget field of EnsembleComputation is set to num_vertices + num_edges in the reduce_to() implementation (upper-bound K = num_vertices). This is a structural parameter of the target instance, not a size metric of the input data — it is not listed in the overhead table.

Validation Method

Closed-loop test: reduce a MinimumVertexCover instance to EnsembleComputation (budget = num_vertices + num_edges), solve the target with BruteForce, extract the witness vertex cover from the sequence, verify it is a valid vertex cover
Check universe_size = |V| + 1 and num_subsets = |E| for the constructed instance
Check budget = num_vertices + num_edges in the constructed EC instance
Test with the C₅ example below (5V, 5E, budget=10) — BF-tractable
For the minimum-cover property: construct EC with budget = K* + |E| where K* is known, verify it evaluates to Or(true); construct with budget = (K*-1) + |E|, verify it evaluates to Or(false)
Edge case: empty graph (no edges) → C = ∅, EC instance trivially satisfiable with any sequence

Example

Source instance (MinimumVertexCover):
Graph G = C₅ (5-cycle) with 5 vertices {0, 1, 2, 3, 4} and 5 edges:

Edges: {0,1}, {1,2}, {2,3}, {3,4}, {4,0}
Minimum vertex cover: K* = 3 (odd cycle: ⌈n/2⌉ = 3; any 2-vertex cover fails)
Example cover: V' = {0, 1, 3} covers:
- {0,1} by 0 ✓, {1,2} by 1 ✓, {2,3} by 3 ✓, {3,4} by 3 ✓, {4,0} by 0 ✓

Constructed target instance (EnsembleComputation) — using upper-bound budget J = |V| + |E| = 10:

Fresh element: a₀ (index 5)
Universe A = {0, 1, 2, 3, 4, 5} (where 5 = a₀), |A| = 6 (universe_size = 6)
Collection C = {{5,0,1}, {5,1,2}, {5,2,3}, {5,3,4}, {5,0,4}} (num_subsets = 5)
Budget budget = 10 (= num_vertices + num_edges = 5 + 5)
EC instance: EnsembleComputation::new(6, subsets, 10) — satisfiable since cover of size ≤ 5 exists

Example satisfying sequence (from cover V' = {0, 1, 3}, using only 8 of the 10 allowed operations):

Phase 1 — cover-vertex augmentations (3 operations):

z₁ = {a₀} ∪ {0} = {5, 0}
z₂ = {a₀} ∪ {1} = {5, 1}
z₃ = {a₀} ∪ {3} = {5, 3}

Phase 2 — edge-subset constructions (5 operations):

z₄ = {1} ∪ z₁ = {5,0,1} = c₁ ✓ — edge {0,1}
z₅ = {2} ∪ z₂ = {5,1,2} = c₂ ✓ — edge {1,2}
z₆ = {2} ∪ z₃ = {5,2,3} = c₃ ✓ — edge {2,3}
z₇ = {4} ∪ z₃ = {5,3,4} = c₄ ✓ — edge {3,4}
z₈ = {4} ∪ z₁ = {5,0,4} = c₅ ✓ — edge {4,0}

All 5 subsets in C appear as some z_i ✓, j = 8 ≤ 10 = J ✓, all unions involve disjoint operands ✓

Solution extraction:
The operations of the form z_i = {a₀} ∪ {u} are z₁ (u=0), z₂ (u=1), z₃ (u=3). Thus V' = {0, 1, 3} is the extracted vertex cover, |V'| = 3 = K* ✓

Budget tightness check:

EC with budget = 3 + 5 = 8: satisfiable (cover of size 3 exists) → Or(true)
EC with budget = 2 + 5 = 7: not satisfiable (no cover of size 2 exists for C₅) → Or(false)

Issue Quality Check — Rule

Check	Result	Details
Usefulness	⚠️ Warn	Target problem EnsembleComputation does not exist in the codebase; novel reduction but requires a new model first
Non-trivial	✅ Pass	Genuine structural transformation with gadget construction (a0-augmented vertices, disjoint union sequences)
Correctness	✅ Pass	Reference is Garey & Johnson (1979), Theorem 3.6 — confirmed as problem PO9 in GJ appendix; book already in project bibliography
Well-written	✅ Pass	Complete algorithm, worked example, overhead table, and validation method all present and detailed

Overall: 2 passed, 0 failed, 1 warning

Usefulness

The target problem EnsembleComputation does not currently exist in the reduction graph (pred show EnsembleComputation fails). MinimumVertexCover currently reduces to: MaximumIndependentSet, MinimumSetCovering, QUBO, and ILP. There is no existing path to EnsembleComputation, so the reduction is novel.

However, implementing this rule requires first adding EnsembleComputation as a new problem model. This is flagged as a warning rather than a failure — the reduction itself is valid, but a companion [Model] issue for EnsembleComputation should be filed or referenced.

The Motivation field explains the purpose (establishing NP-completeness of Ensemble Computation) but is marked with AI-generated warning. The motivation is adequate: it describes how vertex-cover selection maps to disjoint-union operations.

Non-trivial

The reduction involves genuine structural transformation:

A fresh element a0 is introduced (not present in the source instance)
Each edge {u,v} becomes a 3-element subset {a0, u, v} in the collection C
The budget parameter J = K + |E| encodes the vertex cover size constraint through the number of allowed union operations
The correspondence between cover vertices and "a0-augmented" operations is non-trivial — the converse direction requires an exchange argument to normalize the sequence

This is not a variable substitution, subtype coercion, or identity reduction. Pass.

Correctness

Reference: Garey & Johnson, Computers and Intractability (1979), Theorem 3.6, p.66.

The book is already in the project bibliography (garey1979 in docs/paper/references.bib).
Ensemble Computation is confirmed as problem PO9 in the GJ appendix (Program Optimization category), with Vertex Cover listed as the reduction source. This is independently corroborated by the NP-Complete Problems discussion site which tags the problem as PO9 with Vertex Cover.
The Springer paper "Finding Efficient Circuits for Ensemble Computation" also references Ensemble Computation as NP-complete from Garey & Johnson.
The issue body appears to contain a verbatim transcript of the proof from the book, including both directions of the correctness argument and the exchange argument for normalizing the sequence.

The reduction algorithm and proof are consistent with the known literature. Pass.

Well-written

Information completeness: All required sections are present and substantive:

Section	Status
Source	MinimumVertexCover (valid, exists in codebase)
Target	EnsembleComputation (valid name, but model does not yet exist)
Motivation	Present, explains the encoding purpose
Reference	Garey & Johnson (1979), Theorem 3.6, p.66 — verified
Reduction Algorithm	Complete step-by-step procedure with full proof
Size Overhead	Table with `universe_size = num_vertices + 1`, `num_subsets = num_edges`
Validation Method	Present with concrete test cases
Example	Fully worked C4 example with 4 vertices, 4 edges

Algorithm completeness: The reduction algorithm is exceptionally detailed — it includes the complete proof from the book with both the forward (cover to sequence) and converse (sequence to cover) directions. The exchange argument for eliminating {u} ∪ {v} operations is fully spelled out.

Symbol consistency: Symbols are consistently used: G = (V, E), K for cover size, a0 for the fresh element, A for universe, C for collection, J for budget. The overhead table uses code metric names (num_vertices, num_edges, universe_size, num_subsets). Note: the target metric names (universe_size, num_subsets) cannot be verified against actual getters since EnsembleComputation is not yet implemented — they should be validated when the model is created.

Example quality: The C4 (4-cycle) example is well-chosen: it has enough structure to demonstrate the reduction (4 vertices, 4 edges, cover of size 2), the sequence is fully worked out step-by-step (6 operations), and solution extraction is shown explicitly. The validation section also includes a triangle (K3) example and an unsatisfiable case.

Pass.

Recommendations

A companion [Model] issue for EnsembleComputation should be filed before this rule can be implemented. The model needs to define the problem schema, variable semantics, dims(), evaluate(), and getter methods (universe_size, num_subsets).
All sections are marked with AI-generated warnings. While the content appears accurate (it matches the known GJ proof), the contributor should verify the transcription against the original book.
The budget parameter J = K + |E| is derived from the source instance but is not listed as a target metric in the overhead table. This is correctly noted in the derivation section ("J is a parameter derived from the source instance, not a fixed overhead of target size"), but the implementation will need to handle how J is stored in the EnsembleComputation instance.

Issue Quality Check — Rule

Check	Result	Details
Usefulness	✅ Pass	Target problem EnsembleComputation does not exist in the codebase; no path exists — novel reduction
Non-trivial	✅ Pass	Genuine structural transformation: constructs universe A, collection C, and budget J from graph structure
Correctness	⚠️ Warn	Reference (Garey & Johnson, 1979) is a known textbook in the project bibliography; proof text is mathematically sound but exact page/theorem number could not be independently verified online
Well-written	⚠️ Warn	Generally thorough, but several notation and completeness issues (see details below)

Overall: 2 passed, 0 failed, 2 warnings

Usefulness

The target problem "EnsembleComputation" does not exist in the reduction graph (pred show EnsembleComputation fails). No existing path from MinimumVertexCover to EnsembleComputation exists. This is a novel reduction that would add a new node to the graph.

Note: Implementing this rule requires first adding the EnsembleComputation model. A corresponding [Model] issue should be filed (or already exist) before this rule can be implemented.

Non-trivial

The reduction performs genuine structural transformation:

Constructs a new universe A = V ∪ {a₀} with a fresh element
Transforms each edge {u,v} into a 3-element subset {a₀, u, v} in collection C
Establishes a non-trivial budget parameter J = K + |E| linking vertex cover size to operation count
The forward direction (cover → sequence) requires labeling cover vertices and constructing a specific operation ordering
The converse direction involves a non-trivial exchange argument showing minimum-length sequences must use a₀-augmented form

This is clearly not a variable relabeling, subtype coercion, or identity reduction.

Correctness

Reference: Garey & Johnson, Computers and Intractability, Theorem 3.6, p.66.

The book garey1979 is already in the project bibliography (docs/paper/references.bib).
Ensemble Computation is problem PO1 in Garey & Johnson's Appendix A (Program Optimization category).
The issue body contains what appears to be a verbatim quote from the book, including the complete bidirectional proof with the exchange argument for the converse direction.
The mathematical content of the proof is sound: the forward direction correctly constructs a valid sequence from a vertex cover, and the converse correctly extracts a vertex cover from a minimum-length sequence via the exchange argument eliminating {u}∪{v} operations.
Could not independently verify the exact theorem number (3.6) and page number (66) via online sources, as the book's full text is not freely available. However, the proof style is consistent with Chapter 3's "local replacement" technique, and the mathematical content is self-consistent.

No better algorithms or alternative reductions were discovered during search.

Well-written

4a — Information Completeness: All required template sections are present and substantive (Source, Target, Motivation, Reference, Reduction Algorithm, Size Overhead, Validation Method, Example). ✅

4b — Algorithm Completeness: The reduction algorithm is presented in full with both the construction and the bidirectional correctness proof. The summary section provides a clear 4-step procedure suitable for implementation. ✅

4c — Symbol and Notation Consistency:

⚠️ The overhead table uses code metric names universe_size and num_subsets, but these are for the target problem (EnsembleComputation) which does not yet exist. There is no way to verify these match actual getter methods via pred show. This is expected given the target is a new problem, but the implementer must ensure these field names match when implementing the model.
⚠️ The overhead table references num_vertices and num_edges as source problem fields — these correctly match MinimumVertexCover's size_fields (num_vertices, num_edges). ✅
⚠️ The budget parameter J = K + |E| is noted as "not a fixed overhead of target size" — this is correct since J depends on the input parameter K, not just graph structure. However, the issue does not clarify how J maps to the target problem's schema. If EnsembleComputation has a budget field, this should be documented as an overhead expression.

4d — Example Quality:

The example uses a 4-cycle (C₄), which is non-trivial and exercises the reduction meaningfully. ✅
The example is fully worked: shows source instance, step-by-step construction, all 6 union operations, and solution extraction. ✅
The example is brute-force verifiable. ✅
Minor: The validation section's triangle example has a small notation issue — "z₃ = {2}∪z₁" should be clarified since {2} must be disjoint from z₁ = {a₀, 0}, which it is. This is correct.

Additional notes:

Multiple  markers indicate this issue was AI-generated. The content quality is high despite this.
The Motivation section is brief but adequate — it explains the purpose (establishing NP-completeness of Ensemble Computation via encoding vertex-cover selection).

Recommendations

File a companion [Model] issue for EnsembleComputation before implementing this rule, defining the schema with fields like universe (A), collection (C), and budget (J).
Add the budget parameter J to the overhead table once the EnsembleComputation model schema is finalized.
Consider whether EnsembleComputation fits the project's trait hierarchy: it is a satisfaction problem (decision: does a valid sequence of ≤ J operations exist?), so it should implement SatisfactionProblem with Metric = bool.

Fix-issue changelog

Fixed reference: "Theorem 3.6, p.66" → "Appendix Problem PO9" (verified via web research — Ensemble Computation is PO9 in Garey & Johnson, not a Chapter 3 theorem)
Removed hallucinated "Theorem 3.6" label from proof quote header
Reframed for optimization: EnsembleComputation minimizes J (number of union operations), not a decision problem with budget input. Updated Summary, Key Invariant, Size Overhead sections.
Added optimization objective note in Size Overhead: J* = K* + |E| connects source and target optimal values
Upgraded example from C₄ (4V, 4E, K*=2) to C₅ (5V, 5E, K*=3): odd cycle forces K*=⌈n/2⌉, 3 cover vertices with asymmetric reuse, 8-step sequence, ~260K BF configs
Updated Validation Method: added ILP solver note for larger instances, updated test instance descriptions

Applied by /fix-issue.

Add plan for #204: MinimumVertexCover -> EnsembleComputation

feat: add MinimumVertexCover -> EnsembleComputation reduction (#204)

feat: add 11 Tier 1a + 1b medium-confidence reduction rules (#770) (#804

Navigation Menu

Repository navigation

[Rule] Vertex Cover to Ensemble Computation #204

Reduction Algorithm

Size Overhead

Validation Method

Example

Issue Quality Check — Rule

Usefulness

Non-trivial

Correctness

Well-written

Recommendations

Issue Quality Check — Rule

Usefulness

Non-trivial

Correctness

Well-written

Recommendations

Fix-issue changelog

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

[Rule] Vertex Cover to Ensemble Computation #204

Description

Reduction Algorithm

Size Overhead

Validation Method

Example

Activity

zazabap commented on Mar 10, 2026

Issue Quality Check — Rule

Usefulness

Non-trivial

Correctness

Well-written

Recommendations

zazabap commented on Mar 11, 2026

Issue Quality Check — Rule

Usefulness

Non-trivial

Correctness

Well-written

Recommendations

GiggleLiu commented on Mar 20, 2026

Fix-issue changelog

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions