[Model] SetBasis

[isPANN]

Motivation

SET BASIS (P134) from Garey & Johnson, A3 SP7. An NP-complete problem in set/storage theory: given a collection C of subsets of a finite set S, find a minimum-size "basis" B of subsets such that every set in C can be expressed as a union of sets in B. This has applications in data compression, database schema design, and Boolean function minimization -- finding a compact representation of a family of sets. The problem is closely related to set cover but has a fundamentally different structure: instead of covering elements, we must reconstruct exact sets via unions.

Associated reduction rules:

• As target: R74 (VERTEX COVER -> SET BASIS)

Definition

Name: SetBasis
Canonical name: Set Basis Problem; also: Minimum Test Set Basis, Minimum Set Basis
Reference: Garey & Johnson, Computers and Intractability, A3 SP7

Mathematical definition:

INSTANCE: Collection C of subsets of a finite set S, positive integer K ≤ |C|.
QUESTION: Is there a collection B of subsets of S with |B| = K such that, for each c ∈ C, there is a subcollection of B whose union is exactly c?

The optimization version asks: find the minimum K such that a basis B of size K exists.

Variables

• Count: K × |S| binary variables. The K basis elements are each encoded as a binary vector of length |S|, indicating which elements of S are included in that basis set.
• Per-variable domain: binary {0, 1} — whether element j ∈ S belongs to basis set i.
• Meaning: The configuration is a K × |S| binary matrix where row i defines basis element b_i ⊆ S. The assignment is valid (returns true) if every set c ∈ C can be exactly reconstructed as a union of some subcollection of B = {b_1, ..., b_K}.
• dims() spec: vec![2; k * universe_size] — K × |S| binary variables, where variables [i*|S| .. (i+1)*|S|) encode basis element b_i.

Schema (data type)

Type name: SetBasis
Variants: none (pure set-theoretic problem)

Field	Type	Description
universe_size	usize	Size of the ground set S (=
collection	Vec<Vec<usize>>	The collection C of target subsets of S (each represented as sorted element indices)
k	usize	Maximum allowed basis size K

Size fields (for overhead expressions): universe_size (= |S|), num_sets (= |C|), basis_size (= K)

Notes:

• This is a satisfaction (decision) problem: Metric = bool, implementing SatisfactionProblem.
• Key getter methods: universe_size() (= |S|), num_sets() (= |C|), basis_size() (= K).
• Basis elements are arbitrary subsets of S (not necessarily members of C).
• Field naming follows MinimumSetCovering conventions (universe_size, not set_size).

Complexity

• Decision complexity: NP-complete (Stockmeyer, 1975; transformation from VERTEX COVER). Remains NP-complete when all c ∈ C have |c| ≤ 3, but is trivial when all |c| ≤ 2.
• Best known exact algorithm: No specialized exact exponential algorithm is known. The problem can be formulated as an ILP. For practical instances, constraint programming and SAT solvers are used.
• Complexity string: "2^(basis_size * universe_size)" (brute force over K × |S| binary variables)

declare_variants! guidance:

crate::declare_variants! {
    SetBasis => "2^(basis_size * universe_size)",
}

• References:
  • L. J. Stockmeyer (1975). "The Set Basis Problem is NP-Complete." IBM Research Report RC 5431, IBM Research Center, Yorktown Heights, NY.

Specialization

• This is a special case of: General set representation / compression problems
• Known special cases:
  • All sets in C have size ≤ 2: trivially solvable (each element is its own basis element)
  • All sets in C have size ≤ 3: still NP-complete
• Related problems: SET COVER (basis elements must cover S, not reconstruct C), EXACT COVER (disjoint union), MINIMUM EQUIVALENT EXPRESSION

Extra Remark

Full book text:

INSTANCE: Collection C of subsets of a finite set S, positive integer K ≤ |C|.
QUESTION: Is there a collection B of subsets of S with |B| = K such that, for each c ∈ C, there is a subcollection of B whose union is exactly c?
Reference: [Stockmeyer, 1975]. Transformation from VERTEX COVER.
Comment: Remains NP-complete if all c ∈ C have |c| ≤ 3, but is trivial if all c ∈ C have |c| ≤ 2.

How to solve

• It can be solved by (existing) bruteforce. Enumerate all possible collections of K subsets of S; for each collection B, check if every c ∈ C can be expressed as a union of a subcollection of B.
• It can be solved by reducing to integer programming. Binary variable x_T for each candidate subset T ⊆ S; constrain sum(x_T) = K; for each c ∈ C, add constraints ensuring that c is expressible as the union of selected basis sets.
• Other: SAT encoding; constraint programming.

Example Instance

Ground set S = {a, b, c, d} (|S| = 4), Collection C of 4 subsets, K = 3:

• c_1 = {a, b}
• c_2 = {b, c}
• c_3 = {a, c}
• c_4 = {a, b, c}

Question: Is there a basis B of 3 subsets of S such that each c_i is a union of sets in B?

Solution: B = { {a}, {b}, {c} } with |B| = 3.

• c_1 = {a, b} = {a} ∪ {b} ✓
• c_2 = {b, c} = {b} ∪ {c} ✓
• c_3 = {a, c} = {a} ∪ {c} ✓
• c_4 = {a, b, c} = {a} ∪ {b} ∪ {c} ✓

Answer for K = 3: YES.

Infeasibility for K = 2: Suppose B = {b_1, b_2}. Then c_1 = {a,b}, c_2 = {b,c}, and c_3 = {a,c} must each be either b_1, b_2, or b_1 ∪ b_2. Since b_1 ∪ b_2 can equal at most one of these three sets, the other two must each be b_1 or b_2 — but we only have two basis elements for three distinct sets. So K = 2 is infeasible.

Answer for K = 2: NO. Minimum basis size = 3.

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not in the reduction graph; planned reduction from VertexCover
Non-trivial	✅ Pass	Distinct structure: reconstruct exact sets via union, not cover elements
Correctness	✅ Pass	Stockmeyer (1975) reference verified; GJ classification correct
Well-written	⚠️ Warn	Example shows trial-and-error; variable encoding is unclear for implementation

Overall: 3 passed, 0 failed, 1 warning

---

Usefulness

SetBasis does not exist in the codebase. It is GJ problem SP7 with a planned reduction from VertexCover (R74), connecting it to the existing graph. The motivation cites concrete applications (data compression, database schema design, Boolean function minimization) and clearly distinguishes it from SET COVER.

Result: Pass

Non-trivial

SetBasis has a genuinely different feasibility constraint from existing problems. Unlike MinimumSetCovering (cover all elements), SetBasis requires exact reconstruction of each target set as a union of basis elements. Unlike MaximumSetPacking (disjoint sets), basis elements can overlap. No existing problem captures this structure.

Result: Pass

Correctness

References verified:

• L. J. Stockmeyer (1975), "The Set Basis Problem is NP-Complete," IBM Research Report RC 5431 — confirmed via IBM Research technical paper search (https://mp7.watson.ibm.com/76642e18a923fcbf8525763c004aa783.html). The NP-completeness via transformation from VERTEX COVER matches the GJ entry.
• The claim that the problem remains NP-complete for |c| <= 3 but is trivial for |c| <= 2 is consistent with the GJ book text provided.
• The W[2]-hardness claim for parameterized complexity is plausible (analogous structure to dominating set), though no specific reference is cited for this claim.

Result: Pass

Well-written

Template completeness: All required sections are present and substantive.

Issues found:

1. Example shows trial-and-error: The example section includes two failed attempts before arriving at a working instance. The narrative "So this B fails," "This B fails too," and "Revised example" reads like a draft. The final example (S = {a,b,c,d}, 4 subsets, K=3) is correct and well-verified, but the failed attempts should be removed for clarity.

2. Variable encoding is unclear: The Variables section says "2^|S| possible basis sets" as candidates, but this means the brute-force search space is C(2^|S|, K), which is doubly exponential in |S|. The dims() function needs a clear definition — how many variables, and what is each variable's domain? If each potential subset of S is a binary variable (include/exclude from basis), then num_variables() = 2^|S| which is exponential in the input size. This is unusual for the project and needs explicit discussion in the schema.

3. Missing specialized complexity: The complexity section says "no specialized exact exponential algorithm is known" and mentions "2^{2^|S|} in the worst case." This is correct but highlights that the problem has a fundamentally different variable structure than most problems in the project. The dims() implementation strategy should be discussed.

4. Schema field names vs getter methods: The schema lists num_items(), num_sets(), basis_size() as getter methods. These are reasonable but num_items is not standard in the project — num_elements or universe_size might be more consistent with MinimumSetCovering's naming.

Result: Warn — the final example is correct and well-verified, but the presentation needs cleanup and the variable encoding needs clarification.

Recommendations

• Remove the failed example attempts; present only the final working example (S = {a,b,c,d}).
• Clarify the variable encoding: explicitly state that the implementation will enumerate subsets of S as candidate basis elements, and discuss how dims() should work. Consider restricting candidates to subsets that appear in C or are "useful" subsets.
• Add a specific reference for the W[2]-hardness claim.
• Consider aligning getter method names with MinimumSetCovering conventions.

[isPANN]

Changelog (fix-issue-batch)

• Renamed set_size → universe_size (matches MinimumSetCovering conventions)
• Added Size fields line: universe_size, num_sets, basis_size
• Replaced vague dims() spec with concrete: vec![2; k * universe_size] (K × |S| binary vars)
• Added complexity string: "2^(basis_size * universe_size)" with declare_variants! guidance
• Removed unverified W[2]-hardness claim (no reference cited)