[Model] RootedTreeStorageAssignment

[isPANN]

Motivation

ROOTED TREE STORAGE ASSIGNMENT (P153) from Garey & Johnson, A4 SR5. An NP-complete problem from the Storage and Retrieval category. Given a finite set X and a collection of subsets of X, the goal is to find a directed rooted tree on X and extend each subset (by adding extra elements) so that each extended subset forms a directed path in the tree, while minimizing the total number of added elements. This models the problem of organizing data in a hierarchical (tree-structured) storage system where related data items (subsets) must be stored along contiguous paths in the hierarchy. NP-completeness is proved by Gavril (1977) via reduction from ROOTED TREE ARRANGEMENT.

Associated rules:

• R099: Rooted Tree Arrangement → Rooted Tree Storage Assignment (as target)

Definition

Name: RootedTreeStorageAssignment
Canonical name: ROOTED TREE STORAGE ASSIGNMENT
Reference: Garey & Johnson, Computers and Intractability, A4 SR5, p.227

Mathematical definition:

INSTANCE: Finite set X, collection C = {X_1, X_2, ..., X_n} of subsets of X, positive integer K.
QUESTION: Is there a collection C' = {X_1', X_2', ..., X_n'} of subsets of X such that X_i is a subset of X_i' for 1 <= i <= n, such that sum_{i=1}^{n} |X_i' - X_i| <= K, and such that there is a directed rooted tree T = (X, A) in which the elements of each X_i', 1 <= i <= n, form a directed path?

Variables

• Count: |X| variables (one per element of X), encoding the tree topology as a parent array.
• Per-variable domain: Each variable takes values in {0, 1, ..., |X|-1}.
• Encoding: config[i] = parent of node i in the rooted tree T. The root r satisfies config[r] = r. This gives dims() = vec![universe_size; universe_size].
• Meaning: The variable assignment encodes a hierarchical storage layout (the rooted tree T). Once the tree is fixed, the optimal extensions for each subset are determined greedily: for each subset X_i, find the shortest directed path in T containing all elements of X_i. The extension cost |X_i' - X_i| equals the number of intermediate nodes added. The evaluate() function checks: (1) the parent array forms a valid rooted tree, (2) for each subset, all elements lie on a common root-to-descendant path, (3) the total extension cost (sum of intermediate nodes across all subsets) does not exceed K. If the parent array is not a valid rooted tree (e.g., contains cycles or multiple roots), evaluate returns false.

Schema (data type)

Type name: RootedTreeStorageAssignment
Variants: none (no type parameters)

Field	Type	Description
universe_size	usize	Size of the finite set X (elements labeled 0..
subsets	Vec<Vec<usize>>	Collection C of subsets of X (each subset is a Vec of element indices)
bound	usize	Maximum total extension cost K

Size fields:

• universe_size() — number of elements |X|
• num_subsets() — number of subsets |C|

Notes:

• This is a satisfaction (decision) problem: Metric = bool, implementing SatisfactionProblem.
• A "directed path" in T means a sequence of nodes x_1, x_2, ..., x_k where each x_{i+1} is a child of x_i (i.e., the path goes from ancestor to descendant along the tree).
• The tree T is part of the solution, not the instance. The solver must find T; extensions are computed deterministically once T is fixed.

Complexity

• Best known exact algorithm: No specialized sub-exponential exact algorithm is known. Brute-force enumerates all parent-array configurations (|X|^|X| total), filters valid rooted trees, and for each valid tree computes the greedy extension cost.
• Complexity string for declare_variants!: "universe_size^universe_size"
• NP-completeness: NP-complete [Gavril, 1977a], via reduction from ROOTED TREE ARRANGEMENT (GT45).
• Special cases: If all subsets have size <= 2 (pairs), the problem relates directly to tree arrangement. If the tree T is given as part of the input, finding optimal extensions can be done in polynomial time.
• References:
  • F. Gavril (1977). "Some NP-complete problems on graphs." In: Proceedings of the 11th Conference on Information Sciences and Systems, pp. 91-95. Johns Hopkins University.

Extra Remark

Full book text:

INSTANCE: Finite set X, collection C = {X_1, X_2, ..., X_n} of subsets of X, positive integer K.
QUESTION: Is there a collection C' = {X_1', X_2', ..., X_n'} of subsets of X such that X_i is a subset of X_i' for 1 <= i <= n, such that sum_{i=1}^{n} |X_i' - X_i| <= K, and such that there is a directed rooted tree T = (X, A) in which the elements of each X_i', 1 <= i <= n, form a directed path?
Reference: [Gavril, 1977a]. Transformation from ROOTED TREE ARRANGEMENT.

How to solve

• It can be solved by (existing) bruteforce — the parent-array encoding maps directly to the Problem trait: dims() = vec![universe_size; universe_size] enumerates all parent arrays. evaluate() checks (1) valid rooted tree, (2) computes greedy extension costs per subset, (3) checks total ≤ bound. Most configurations are invalid trees, but BruteForce filters these naturally via evaluate() = false.
• It can be solved by reducing to integer programming.
• Other: When the tree T is fixed (given as input), the extension problem for each subset reduces to finding the shortest directed path in T that contains all elements of the subset. This is solvable in O(|X|) per subset by finding the lowest common ancestor and verifying that all subset elements lie on the path from the LCA to the deepest element.

Example Instance

Instance 1 (YES):
Universe X = {0, 1, 2, 3, 4} (|X| = 5).
Collection C:

• X_1 = {0, 2}
• X_2 = {1, 3}
• X_3 = {0, 4}
• X_4 = {2, 4}

Bound K = 1.

Solution: Use tree T rooted at 0 with children 1 and 2; node 1 has child 3; node 2 has child 4:

      0
     / \
    1   2
    |   |
    3   4

Extended subsets (each must form a directed path in T):

• X_1' = {0, 2}: path 0→2. No extension needed. Cost = 0.
• X_2' = {1, 3}: path 1→3. No extension needed. Cost = 0.
• X_3' = {0, 2, 4}: path 0→2→4, extending {0, 4} by adding {2}. Cost = 1.
• X_4' = {2, 4}: path 2→4. No extension needed. Cost = 0.
• Total cost = 0 + 0 + 1 + 0 = 1 ≤ K = 1. ✓

Alternative satisfying tree: Root at 0, child 2; node 2 has children 1 and 4; node 1 has child 3:

      0
      |
      2
     / \
    1   4
    |
    3

• X_1' = {0, 2}: path 0→2. Cost = 0.
• X_2' = {2, 1, 3}: path 2→1→3, extending {1, 3} by adding {2}. Cost = 1.
• X_3' = {0, 2, 4}: path 0→2→4, extending {0, 4} by adding {2}. Cost = 1.
• X_4' = {2, 4}: path 2→4. Cost = 0.
• Total cost = 0 + 1 + 1 + 0 = 2 > K = 1. ✗ (This tree does NOT satisfy the bound.)

Non-satisfying configuration: Chain tree 0→1→2→3→4:

• X_1' = {0, 1, 2}: extend {0, 2} by adding {1}. Cost = 1.
• X_2' = {1, 2, 3}: extend {1, 3} by adding {2}. Cost = 1.
• X_3' = {0, 1, 2, 3, 4}: extend {0, 4} by adding {1, 2, 3}. Cost = 3.
• X_4' = {2, 3, 4}: extend {2, 4} by adding {3}. Cost = 1.
• Total cost = 1 + 1 + 3 + 1 = 6 > K = 1. ✗

Infeasible tree: Star tree (root 0, children 1, 2, 3, 4):

• X_2 = {1, 3}: nodes 1 and 3 are siblings (both children of 0). No directed path in the tree contains both 1 and 3, since directed paths go strictly from ancestor to descendant. No extension of {1, 3} can form a directed path in a star tree. This tree is infeasible regardless of K.

Instance 2 (NO):
Universe X = {0, 1, 2, 3, 4} (|X| = 5).
Same collection C = {{0, 2}, {1, 3}, {0, 4}, {2, 4}}.
Bound K = 0.

For K = 0, every subset must already form a directed path with no extensions (X_i' = X_i). This means each pair of elements in a subset must be in a parent-child relationship in T. The subsets {0, 2}, {0, 4}, and {2, 4} require edges 0–2, 0–4, and 2–4 in the tree. These three edges form a triangle (3-cycle), but a tree is acyclic — it cannot contain a cycle. Therefore no rooted tree satisfies all constraints with K = 0. Answer: NO.

Expected Outcome

• Instance 1: Satisfying. The tree rooted at 0 with edges 0→1, 0→2, 1→3, 2→4 achieves total extension cost 1 ≤ K = 1.
• Instance 2: Not satisfying. No tree can achieve extension cost 0 due to the triangle constraint among {0, 2, 4}.

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	⚠️ Warn	Novel problem, but orphan node — depends on RootedTreeArrangement (#407) which also does not exist
Non-trivial	✅ Pass	Distinct problem combining tree construction with subset path extension minimization
Correctness	✅ Pass	Reference verified; NP-completeness claim consistent with Garey & Johnson
Well-written	❌ Fail	Examples are self-contradictory (bounds changed mid-example); variable encoding unimplementable; missing size fields

Overall: 2 passed, 1 warning, 1 failed

---

Usefulness

The problem RootedTreeStorageAssignment does not exist in the current codebase. It is a legitimate NP-complete problem from Garey & Johnson (SR5, p.227). However, the only associated rule is R099: RootedTreeArrangement -> RootedTreeStorageAssignment, and RootedTreeArrangement (#407) also does not exist in the codebase. This creates a chain of two orphan problems with no connection to the existing reduction graph. Warn: this problem would need at least one reduction to/from an existing codebase problem to be useful.

Non-trivial

This is a genuinely distinct problem. The input structure (universe + collection of subsets + bound) superficially resembles MinimumSetCovering or MaximumSetPacking, but the objective is fundamentally different: finding a tree topology such that subsets can be extended to directed paths with minimum total extension cost. No existing problem combines tree construction with subset path extension. Pass.

Correctness

References verified:

• Gavril (1977): "Some NP-complete problems on graphs," Proceedings of the 11th Conference on Information Sciences and Systems, pp. 91-95, Johns Hopkins University — previously verified in issue [Model] RootedTreeArrangement #407 check. The paper exists and is cited by Garey & Johnson for this problem.
• NP-completeness claim: The issue states NP-complete via reduction from Rooted Tree Arrangement (GT45), which is consistent with the Garey & Johnson entry.

Pass.

Well-written

Failures:

1. Example 1 is self-contradictory: The instance starts with K=8 but the solution yields cost 10, so the answer is NO with K=8. The issue then changes K to 10 mid-example. An example should present a single consistent instance — not a debugging narrative. Either start with K=10, or pick a tree that achieves cost <= 8.

2. Example 2 is self-contradictory: Same pattern — starts with K=2, the first tree fails, tries a second tree with cost 4, then changes K to 4. This makes two examples that demonstrate failed attempts rather than clean solutions.

3. Example 3 NO instance is hand-wavy: The argument "a rooted tree on 6 nodes has at most 5 ancestor-descendant pairs (parent-child edges)" is incorrect — a chain on 6 nodes has C(6,2)=15 ancestor-descendant pairs. The stated reasoning is wrong, even if the conclusion (NO for K=0) may be correct for other reasons.

4. Variable encoding is unimplementable: The Variables section describes the search space as "choosing both the tree structure and n path extensions" but does not map this to a concrete dims() vector. The Problem trait requires dims() -> Vec<usize> returning a fixed-length vector with per-variable domain sizes. The current description does not explain how to encode the combinatorial tree+extension space into this format.

5. Missing size field getters: The Schema does not specify getter methods for declare_variants!. Should include universe_size(), num_subsets() at minimum.

6. Missing complexity string: No concrete expression for declare_variants!.

7. Brute-force solver feasibility: The issue claims brute-force works by enumerating all rooted trees, but the BruteForce solver iterates over dims() configurations. Without a clear encoding into a configuration vector, the brute-force claim is not implementable with the existing solver framework.

Recommendations

• Rewrite all three examples with consistent bounds (set K first, then show whether the solution satisfies it)
• Fix the mathematical error in Example 3's NO argument
• Define a concrete dims() encoding (e.g., Prufer sequence for the tree + assignment vector)
• Add universe_size() and num_subsets() getters
• Provide a concrete complexity string

[isPANN]

Issue Quality Check — Model (Re-check)

Check	Result	Details
Usefulness	⚠️ Warn	Novel problem; orphan until RootedTreeArrangement (#407, now "Good") is implemented
Non-trivial	✅ Pass	Distinct problem combining tree construction with subset path extension minimization
Correctness	✅ Pass	Gavril 1977 verified on Semantic Scholar; NP-completeness claim consistent with Garey & Johnson SR5
Well-written	❌ Fail	Examples self-contradictory; variable encoding unimplementable; missing complexity string and size getters

Overall: 2 passed, 1 warning, 1 failed

Previously (2026-03-12): 2 passed, 1 warning, 1 failed → No change (issue body appears unchanged).

---

Usefulness

RootedTreeStorageAssignment does not exist in the codebase. The only planned reduction is R099: RootedTreeArrangement → RootedTreeStorageAssignment. RootedTreeArrangement (#407) now has the "Good" label (passed quality checks) but is not yet implemented, so this problem remains an orphan with no connection to the existing reduction graph. Warn: needs RootedTreeArrangement to be implemented first, and ideally an additional reduction to/from an existing codebase problem.

Non-trivial

Genuinely distinct problem. While the input structure (universe + subsets + bound) superficially resembles MinimumSetCovering or MaximumSetPacking, the objective is fundamentally different: finding a tree topology such that subsets can be extended to directed paths with minimum total extension cost. No existing problem in the codebase combines tree construction with subset path extension. Pass.

Correctness

Reference verified:

• Gavril (1977): "Some NP-complete problems on graphs," Proceedings of the 11th Conference on Information Sciences and Systems, pp. 91-95, Johns Hopkins University — found on Semantic Scholar. Paper exists with matching title, author, and venue.
• NP-completeness claim: Consistent with Garey & Johnson A4 SR5, p.227. Reduction from Rooted Tree Arrangement (GT45).
• No better algorithms found: No specialized sub-exponential exact algorithm discovered in literature search.

Pass.

Well-written

Failures (unchanged from previous check):

1. Example 1 is self-contradictory: Starts with K=8, computes total cost = 10 > K, then changes K to 10 mid-example. An example should present a single consistent instance.

2. Example 2 is self-contradictory: Starts with K=2, first tree fails, tries a second tree with cost 4, then changes K to 4. Same debugging-narrative pattern.

3. Example 3 NO-instance reasoning is incorrect: Claims "a rooted tree on 6 nodes has at most 5 ancestor-descendant pairs (parent-child edges)" — this is wrong. A chain on 6 nodes has C(6,2) = 15 ancestor-descendant pairs. The stated reasoning does not support the conclusion, even if K=0 may indeed be unsatisfiable for other reasons.

4. Variable encoding unimplementable: The Variables section describes "choosing both the tree structure and n path extensions" but does not map this to a concrete dims() -> Vec<usize> vector. The Problem trait requires a fixed-length vector with per-variable domain sizes. Without this mapping, the brute-force solver claim is not implementable.

5. Missing size field getters: The Schema does not specify getter methods for declare_variants!. Should include at least universe_size() and num_subsets().

6. Missing concrete complexity string: No expression suitable for declare_variants! (e.g., "universe_size^universe_size * num_subsets" or similar).

7. Brute-force solver feasibility: The BruteForce solver iterates over dims() configurations. Without a clear encoding into a configuration vector, the brute-force solver claim is unverifiable.

Recommendations

• Rewrite all three examples with consistent bounds — set K first, then show whether the solution satisfies it
• Fix the mathematical error in Example 3's NO argument (or provide a correct proof)
• Define a concrete dims() encoding (e.g., Prüfer sequence for the tree + extension assignment vector)
• Add universe_size() and num_subsets() getters to the Schema section
• Provide a concrete complexity string for declare_variants!

[isPANN]

Fix-issue changelog

• Variables: Replaced vague description with concrete parent-array encoding (dims() = vec![universe_size; universe_size], config[i] = parent of node i, root has config[root] = root)
• Schema: Added size field getters universe_size() and num_subsets()
• Complexity: Added complexity string "universe_size^universe_size" for declare_variants!
• How to solve: Updated brute-force explanation to reference parent-array encoding and dims()
• Examples: Replaced 3 self-contradictory examples with 2 clean instances (5 elements, 4 subsets): YES (K=1, optimal tree cost 1, plus alternative/chain/star comparisons) and NO (K=0, triangle acyclicity argument)
• Added Expected Outcome section with concrete satisfying/non-satisfying solutions
• Schema notes: Clarified that extensions are computed deterministically once T is fixed

Applied by /fix-issue.