[Model] ComparativeContainment

[isPANN]

Motivation

COMPARATIVE CONTAINMENT (P137) from Garey & Johnson, A3 SP10. A classical NP-complete problem in weighted set selection: given two weighted collections of subsets over a common universe, decide whether a subset of the universe can be chosen so that the total weight of sets in the first collection containing the chosen subset meets or exceeds the total weight of sets in the second collection containing it. Introduced by Plaisted (1976), who proved its NP-completeness via reduction from VERTEX COVER. The problem captures a fundamental comparison principle over containment relations and serves as a gateway to further reductions (e.g., to COMPARATIVE VECTOR INEQUALITIES).

Associated reduction rules:

• As target: R76 (VERTEX COVER to COMPARATIVE CONTAINMENT)
• As source: R163 (COMPARATIVE CONTAINMENT (with equal weights) to COMPARATIVE VECTOR INEQUALITIES)

Definition

Name: ComparativeContainment

Canonical name: Comparative Containment
Reference: Garey & Johnson, Computers and Intractability, A3 SP10

Mathematical definition:

INSTANCE: Two collections R = {R_1,R_2,...,R_k} and S = {S_1,S_2,...,S_l} of subsets of a finite set X, weights w(R_i) in Z^+, 1 <= i <= k, and w(S_j) in Z^+, 1 <= j <= l.
QUESTION: Is there a subset Y <= X such that
Sum_{Y <= R_i} w(R_i) >= Sum_{Y <= S_j} w(S_j) ?

(Here Y <= R_i means Y is contained in R_i.)

Variables

• Count: n = |X| (one binary variable per element of the universe X)
• Per-variable domain: {0, 1} -- 0 means element is not in Y, 1 means element is in Y
• Meaning: x_i = 1 if element x_i is included in the chosen subset Y. The problem asks whether there exists an assignment such that Sum_{j: Y <= R_j} w(R_j) >= Sum_{j: Y <= S_j} w(S_j), where the containment Y <= R_j is checked by verifying that every element in Y is also in R_j.

Schema (data type)

Type name: ComparativeContainment
Variants: weight type

Field	Type	Description
universe_size	usize	Size of the finite set X
r_sets	Vec<Vec<usize>>	Collection R: each inner Vec lists element indices in the subset
s_sets	Vec<Vec<usize>>	Collection S: each inner Vec lists element indices in the subset
r_weights	Vec<W>	Positive integer weight for each set in R
s_weights	Vec<W>	Positive integer weight for each set in S

Size fields (for overhead expressions): universe_size (= |X|), num_r_sets (= |R|), num_s_sets (= |S|)

Notes:

• This is a satisfaction (decision) problem: Metric = bool, implementing SatisfactionProblem.
• Parameterized by weight type W: WeightElement (e.g., i32).
• Key getter methods: universe_size(), num_r_sets(), num_s_sets().
• dims() spec: vec![2; universe_size] — one binary variable per element of X.

Complexity

• Decision complexity: NP-complete (Plaisted, 1976; transformation from VERTEX COVER). Remains NP-complete even with all weights equal to 1.
• Best known exact algorithm: Brute-force enumeration over all 2^n subsets Y of X, checking containment against all sets in R and S. Time complexity O(2^n * (k + l) * n). No specialized exact algorithm is known beyond general satisfaction techniques.
• Complexity string: "2^universe_size" (search space is 2^|X| subsets of X)

declare_variants! guidance:

crate::declare_variants! {
    ComparativeContainment<i32> => "2^universe_size",
}

Specialization

• The unit-weight case (all w(R_i) = w(S_j) = 1) remains NP-complete.
• When |R| = 0, the answer is trivially YES (choose Y = X or any Y such that no S_j contains Y; in the degenerate case, the LHS sum is 0 and the problem reduces to asking if the RHS sum can also be 0).

Extra Remark

Full book text:

INSTANCE: Two collections R = {R_1,R_2,...,R_k} and S = {S_1,S_2,...,S_l} of subsets of a finite set X, weights w(R_i) in Z^+, 1 <= i <= k, and w(S_j) in Z^+, 1 <= j <= l.
QUESTION: Is there a subset Y <= X such that
Sum_{Y <= R_i} w(R_i) >= Sum_{Y <= S_j} w(S_j) ?
Reference: [Plaisted, 1976]. Transformation from VERTEX COVER.
Comment: Remains NP-complete even if all subsets in R and S have weight 1 [Garey and Johnson, ----].

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all 2^n subsets Y of X; for each, compute containment sums and compare.)
• It can be solved by reducing to integer programming. (Binary variables y_i for each element; indicator constraints for containment; maximize or constrain the difference of weighted containment counts.)
• Other: (TBD)

Example Instance

Instance 1 (YES):
X = {0, 1, 2, 3}

R = { R_1 = {0, 1, 2, 3}, R_2 = {0, 1} }, w(R_1) = 2, w(R_2) = 5
S = { S_1 = {0, 1, 2, 3}, S_2 = {2, 3} }, w(S_1) = 3, w(S_2) = 6

Note: Y = ∅ gives R-total = 7, S-total = 9 (7 < 9, fails). So the empty set doesn't work — we need a non-trivial Y.

Choose Y = {0}:

• R: Y ⊆ R_1 = {0,1,2,3}? YES (w=2). Y ⊆ R_2 = {0,1}? YES (w=5). R-total = 7.
• S: Y ⊆ S_1 = {0,1,2,3}? YES (w=3). Y ⊆ S_2 = {2,3}? NO (0 ∉ S_2). S-total = 3.
• 7 ≥ 3? YES. Y = {0} excludes the heavy S_2 while keeping both R sets.

Contrast with Y = {2}: R_1 yes (2), R_2 no. R=2. S_1 yes (3), S_2 yes (6). S=9. 2 < 9, fails.

Instance 2 (NO):
X = {0, 1}

R = { R_1 = {0}, R_2 = {1} }, w(R_1) = 1, w(R_2) = 1
S = { S_1 = {0, 1} }, w(S_1) = 3

Exhaustive check:

• Y = ∅: R = 1+1 = 2, S = 3. 2 < 3, fails.
• Y = {0}: R_1 yes (1), R_2 no. R = 1. S_1 yes (3). 1 < 3, fails.
• Y = {1}: R_1 no, R_2 yes (1). R = 1. S_1 yes (3). 1 < 3, fails.
• Y = {0,1}: R_1 no ({0,1} ⊄ {0}), R_2 no. R = 0. S_1 yes (3). 0 < 3, fails.
• Answer: NO — every Y gives R-weight < S-weight.

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem; planned reductions from VertexCover and to ComparativeVectorInequalities
Non-trivial	✅ Pass	Distinct containment-based comparison structure unlike any existing problem
Correctness	⚠️ Warn	Plaisted (1976) reference not independently verifiable (technical report); GJ attribution trusted
Well-written	✅ Pass	Clean example, complete template, clear variable encoding

Overall: 3 passed, 0 failed, 1 warning

---

Usefulness

ComparativeContainment does not exist in the codebase. It is GJ problem SP10 with two planned reduction connections: as target from VertexCover (R76) and as source to ComparativeVectorInequalities (R163). This provides good graph connectivity. The motivation clearly explains the problem's role as a "comparison principle over containment relations."

Result: Pass

Non-trivial

ComparativeContainment has a genuinely unique structure: it compares weighted sums over two set families based on containment of a chosen subset Y. This is fundamentally different from MinimumSetCovering (cover elements), MaximumSetPacking (select disjoint sets), or any other existing problem. The feasibility constraint involves comparing two containment-weighted sums, which is not captured by any current model.

Result: Pass

Correctness

References:

• Plaisted (1976): This is cited as a technical report without a journal publication. The reference could not be independently verified via web search — no digital copy or abstract was found. However, Garey & Johnson cite it as the source for the NP-completeness result (transformation from VERTEX COVER), and GJ is a highly reliable source. The book text provided in the issue matches the expected GJ format.
• The claim that the problem remains NP-complete with unit weights is attributed to "Garey and Johnson, ----" in the book text (the dashes suggest an unpublished result by GJ themselves), which is consistent.

Complexity: The brute-force bound of O(2^n * (k+l) * n) is correct — enumerate all subsets Y of X, check containment against all sets.

Result: Warn — the primary reference cannot be independently verified, but the GJ attribution is trusted.

Well-written

Template completeness: All required sections are present and substantive.

Strengths:

• The example is clean, correct, and fully worked with explicit containment checks for both R and S collections. No trial-and-error.
• The variable encoding is clear: n = |X| binary variables, one per element.
• The mathematical definition is precise and matches the GJ book text exactly.
• The schema design is reasonable with clear field descriptions.

Minor observations (not failures):

• The schema uses u64 for weights instead of a generic weight type W. The project typically parameterizes weight types (e.g., i32, f64, One). Consider using a generic weight parameter for consistency.
• The Specialization section's degenerate case analysis (|R| = 0) is a bit hand-wavy but not incorrect.

Result: Pass

Recommendations

• Consider parameterizing the weight type as W: WeightElement for consistency with other models.
• If implementing, verify the Plaisted reference via a university library or interlibrary loan, since it is a technical report not widely available online.

[isPANN]

Changelog (fix-issue-batch)

• Added Size fields line: universe_size, num_r_sets, num_s_sets
• Added Notes section with SatisfactionProblem, weight type, getter methods, and dims() spec
• Added complexity string "2^universe_size" with declare_variants! guidance
• Added decision complexity line (NP-complete, Plaisted 1976)