Skip to content

[Rule] Vertex Cover to Ensemble Computation #204

@isPANN

Description

@isPANN

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:

  1. Universe construction: Let a₀ be a fresh element not in V. Set A = V ∪ {a₀}. The universe has |V| + 1 elements.
  2. 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.
  3. 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.
  4. 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.
  5. 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)

Metadata

Metadata

Assignees

No one assigned

    Labels

    GoodAn issue passed all checks.ruleA new reduction rule to be added.

    Type

    No type
    No fields configured for issues without a type.

    Projects

    Status
    Done

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions