[Model] RootedTreeArrangement

[isPANN]

Motivation

ROOTED TREE ARRANGEMENT (P56) from Garey & Johnson, A1.3 GT45. An NP-complete graph arrangement problem that asks whether the vertices of a given graph can be embedded one-to-one into the nodes of a rooted tree such that every edge of the graph connects two vertices on the same root-to-leaf path, and the total edge-stretch (sum of tree distances over all graph edges) is bounded by K. This generalizes OPTIMAL LINEAR ARRANGEMENT (GT43) to tree-structured layouts. Gavril (1977) proved NP-completeness via reduction from OPTIMAL LINEAR ARRANGEMENT. The problem arises in file system layout, memory hierarchy design, and data structure optimization.

Associated rules:

• R099: Rooted Tree Arrangement → Rooted Tree Storage Assignment (as source)
• Reduced from OPTIMAL LINEAR ARRANGEMENT (per GJ book text, GT43 → GT45)

Definition

Name: RootedTreeArrangement
Canonical name: ROOTED TREE ARRANGEMENT
Reference: Garey & Johnson, Computers and Intractability, A1.3 GT45

Mathematical definition:

INSTANCE: Graph G = (V, E), positive integer K.
QUESTION: Is there a rooted tree T = (U, F), with |U| = |V|, and a one-to-one function f: V -> U such that for every edge {u,v} in E there is a simple path from the root that includes both f(u) and f(v) and such that if d(x,y) is the number of edges on the path from x to y in T, then sum_{{u,v} in E} d(f(u), f(v)) <= K?

Variables

• Count: 2n variables, where n = |V|. The first n variables encode the tree topology as a parent array; the next n variables encode the bijection f.
• Per-variable domain: Each variable takes values in {0, 1, ..., n-1}.
• Encoding:
  • config[0..n] = parent array: config[i] is the parent of node i in the rooted tree T. The root r satisfies config[r] = r.
  • config[n..2n] = bijection: config[n+v] is the tree node f(v) assigned to vertex v.
• Meaning: A satisfying assignment is a (tree, mapping) pair such that (1) the parent array forms a valid rooted tree, (2) the bijection is a valid permutation, (3) for every graph edge {u,v}, f(u) and f(v) are in an ancestor-descendant relationship in T, and (4) the total tree distance sum_{{u,v} in E} d(f(u), f(v)) <= K.

Schema (data type)

Type name: RootedTreeArrangement
Variants: graph topology (graph type parameter G)

Field	Type	Description
graph	SimpleGraph	The undirected graph G = (V, E) to be arranged in a tree
bound	usize	Maximum total distance K

Size fields:

• num_vertices() — number of vertices |V|
• num_edges() — number of edges |E|

Notes:

• This is a satisfaction (decision) problem: Metric = bool, implementing SatisfactionProblem.
• No weight type is needed; edge distances are measured in the tree (hop count).
• The rooted tree T is part of the solution, not part of the instance.

Complexity

• Best known exact algorithm: No specialized exact algorithm is known. Brute-force enumerates all rooted labeled trees on n nodes (n^(n-1) by Cayley's formula) and all n! bijections, checking the ancestral path constraint and distance bound. With the parent-array encoding, the configuration space is n^(2n).
• Complexity string for declare_variants!: "2^num_vertices" (conservative NP-complete bound, matching OptimalLinearArrangement convention).
• Special cases: For trees (G is a tree), the problem can be solved in polynomial time. Adolphson and Hu (1973) gave an O(n log n) algorithm for optimal linear arrangement of trees, and similar techniques apply.
• NP-completeness: NP-complete [Gavril, 1977a], via reduction from OPTIMAL LINEAR ARRANGEMENT (GT43).
• 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.
  • M. R. Garey, D. S. Johnson, and L. Stockmeyer (1976). "Some simplified NP-complete graph problems." Theoretical Computer Science 1(3):237-267.
  • D. Adolphson and T. C. Hu (1973). "Optimal linear ordering." SIAM Journal on Applied Mathematics 25(3):403-423.

Extra Remark

Full book text:

INSTANCE: Graph G = (V,E), positive integer K.
QUESTION: Is there a rooted tree T = (U,F), with |U| = |V|, and a one-to-one function f: V -> U such that for every edge {u,v} in E there is a simple path from the root that includes both f(u) and f(v) and such that if d(x,y) is the number of edges on the path from x to y in T, then sum_{{u,v} in E} d(f(u),f(v)) <= K?

Reference: [Gavril, 1977a]. Transformation from OPTIMAL LINEAR ARRANGEMENT.

How to solve

• It can be solved by (existing) bruteforce — the parent-array + permutation encoding maps directly to the Problem trait: dims() = vec![n; 2*n] enumerates all (parent array, bijection) pairs. evaluate() checks (1) valid rooted tree, (2) valid permutation, (3) ancestral path constraint, and (4) distance bound. Most configurations are invalid (not a tree or not a permutation), but BruteForce filters these naturally via evaluate() = false.
• It can be solved by reducing to integer programming.
• Other: For special graph classes (paths, trees), polynomial-time algorithms exist. For general graphs, the problem is NP-complete.

Example Instance

Instance 1 (YES, path graph can be arranged tightly):
Graph G with 6 vertices {0, 1, 2, 3, 4, 5} and 5 edges:

• Edges: {0,1}, {1,2}, {2,3}, {3,4}, {4,5}
• (Simple path P_6)
• Bound K = 5.

Solution: Use rooted tree T as a chain 0 -> 1 -> 2 -> 3 -> 4 -> 5 (rooted at 0), with identity mapping f(v) = v.

• Each edge {i, i+1} has d(i, i+1) = 1 in T.
• Total distance = 5 * 1 = 5 <= K = 5. ✓
• Each pair f(i), f(i+1) lies on the root-to-leaf path 0->1->2->3->4->5. ✓
• Answer: YES

Instance 2 (YES, triangle + path forces chain):
Graph G with 5 vertices {0, 1, 2, 3, 4} and 5 edges:

• Edges: {0,1}, {0,2}, {1,2}, {2,3}, {3,4}
• (Triangle 0-1-2 plus path 2-3-4)
• Bound K = 7.

The triangle {0,1,2} forces all three vertices onto a single root-to-leaf path (each pair must be in ancestor-descendant relationship). Combined with edges {2,3} and {3,4}, all 5 vertices must lie on a single chain.

Solution: Chain tree 0 -> 1 -> 2 -> 3 -> 4 (rooted at 0), identity mapping f(v) = v.

• d(0,1) = 1, d(0,2) = 2, d(1,2) = 1, d(2,3) = 1, d(3,4) = 1
• Total = 1 + 2 + 1 + 1 + 1 = 6 <= K = 7. ✓
• All edges connect ancestor-descendant pairs. ✓
• Answer: YES

Suboptimal feasible arrangement [0, 2, 1, 3, 4] (swap vertices 1 and 2):

• d(0,1) = |0-2| = 2, d(0,2) = |0-1| = 1, d(1,2) = |2-1| = 1, d(2,3) = |1-3| = 2, d(3,4) = |3-4| = 1
• Total = 2 + 1 + 1 + 2 + 1 = 7 <= K = 7. ✓ (suboptimal but feasible)

Infeasible arrangement [2, 1, 0, 3, 4]:

• d(0,1) = |2-1| = 1, d(0,2) = |2-0| = 2, d(1,2) = |1-0| = 1, d(2,3) = |0-3| = 3, d(3,4) = |3-4| = 1
• Total = 1 + 2 + 1 + 3 + 1 = 8 > K = 7. ✗

Instance 3 (NO, triangle needs chain):
Graph G with 6 vertices {0, 1, 2, 3, 4, 5} and 7 edges forming two triangles connected by a path:

• Edges: {0,1}, {1,2}, {0,2}, {2,3}, {3,4}, {4,5}, {3,5}
• Bound K = 8.

In any rooted tree, the triangle {0,1,2} forces all three vertices onto a single root-to-leaf path, costing at least d(0,1) + d(1,2) + d(0,2) >= 1 + 1 + 2 = 4. Similarly {3,4,5} with edge {3,5} forces a chain costing at least 4. Plus edge {2,3} costs at least 1. Minimum total >= 4 + 4 + 1 = 9 > K = 8. Answer: NO.

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	⚠️ Warn	Novel problem, but motivation for reduction graph connectivity is weak
Non-trivial	✅ Pass	Distinct feasibility constraints (ancestral path + distance bound) from all existing problems
Correctness	⚠️ Warn	References verified but complexity section lacks a concrete best-known algorithm bound
Well-written	❌ Fail	Multiple issues: no size overhead fields, brute-force variable encoding unclear, Example 2 is self-contradictory

Overall: 1 passed, 2 warnings, 1 failed

---

Usefulness

The problem RootedTreeArrangement does not exist in the current codebase. It is a legitimate NP-complete problem from Garey & Johnson (GT45). However, the motivation section mentions associated rules (R099: Rooted Tree Arrangement → Rooted Tree Storage Assignment) and being reduced from Optimal Linear Arrangement — but neither of these problems exist in the reduction graph either. This means the problem would be an orphan node with no immediate connections. The practical applications listed (file system layout, memory hierarchy design) are plausible but vague. Warn: consider adding at least one reduction to/from an existing problem in the graph.

Non-trivial

This is a genuinely distinct problem. The feasibility constraints combine two non-trivial requirements: (1) every edge must map to an ancestor-descendant pair in the rooted tree, and (2) the total tree distance is bounded. No existing problem in the codebase captures this combination. The variable space (tree topology + bijection) is fundamentally different from all current models. Pass.

Correctness

References verified:

• Gavril (1977): "Some NP-complete problems on graphs," Proceedings of the 11th Conference on Information Sciences and Systems, Johns Hopkins University — confirmed via Semantic Scholar. The paper exists and addresses NP-completeness of graph problems. The specific claim about rooted tree arrangement NP-completeness via reduction from Optimal Linear Arrangement is consistent with Garey & Johnson's citation.
• Garey, Johnson, Stockmeyer (1976): "Some simplified NP-complete graph problems," Theoretical Computer Science 1(3):237-267 — confirmed via ScienceDirect and DBLP. This paper establishes NP-completeness of Optimal Linear Arrangement among other problems.
• Adolphson and Hu (1973): "Optimal linear ordering," SIAM Journal on Applied Mathematics 25(3):403-423 — confirmed via SIAM. The paper presents an algorithm for optimal linear ordering of trees.

Complexity concern: The issue states "No specialized exact algorithm is known" and gives O(n^n * n! * m) brute-force bound. This is not a usable complexity string for declare_variants!. The issue needs to provide a concrete best-known exact algorithm with a specific exponential base (e.g., for NP-hard problems, something like c^n with a specific constant). The current description is too vague for implementation. Warn.

Well-written

Failures:

1. Example 2 is self-contradictory: The issue first proposes a tree, discovers it fails (edge {2,3} violates ancestral constraint), then changes to a chain with K=18 instead of the original K=14. This is confusing — the example should present a single consistent instance with a known solution, not a debugging narrative. The bound K was changed mid-example without re-stating the instance clearly.

2. Variables section is imprecise: The variable encoding says "O(n) discrete choices" but the actual search space is the Catalan number of trees times n!. This does not map to the dims() function needed for Problem trait implementation. The issue should specify how the solution is encoded as a fixed-length configuration vector (e.g., Prufer sequence + permutation, giving dims() = [n; 2n-2] or similar).

3. Schema missing size fields: The Schema section does not specify getter methods (like num_vertices, num_edges) that would be needed for declare_variants! overhead expressions. These are required for the overhead system.

4. No declare_variants! complexity string: The complexity section does not provide a concrete expression suitable for the macro (e.g., "n^n * n!" or a tighter bound). This is required for implementation.

5. Brute-force solver claim is questionable: The "How to solve" section checks brute-force, but the brute-force approach requires enumerating all rooted labeled trees (n^(n-1) by Cayley's formula) AND all n! permutations. The current BruteForce solver works by iterating over dims() configurations — it is unclear how tree enumeration would be encoded in this framework.

Recommendations

• Fix Example 2 to present a single clean instance with consistent K value
• Specify the concrete variable encoding for dims() (e.g., Prufer sequence encoding)
• Add num_vertices() and num_edges() as size field getters in the Schema section
• Provide a concrete complexity string for declare_variants!
• Clarify how brute-force enumeration maps to the Problem trait's configuration space

[isPANN]

Issue Quality Check — Model (Re-check)

Previous check: 2026-03-12. Re-checking with --force. Issue body unchanged since last check.

Check	Result	Details
Usefulness	✅ Pass	Novel problem; connects to existing OptimalLinearArrangement (GT43 → GT45)
Non-trivial	✅ Pass	Unique constraints: tree topology as part of solution + ancestral path requirement
Correctness	⚠️ Warn	All 3 references verified to exist; Gavril 1977 specific reduction claim unverifiable without full text; no concrete complexity bound
Well-written	❌ Fail	Example 2 self-contradictory; missing size fields; no declare_variants! complexity string; variable encoding unclear

Overall: 2 passed, 1 warning, 1 failed

Changes from previous check: Usefulness upgraded from ⚠️ Warn to ✅ Pass (OptimalLinearArrangement now exists in codebase). All other verdicts unchanged.

---

Usefulness

RootedTreeArrangement does not exist in the codebase — novel problem. OptimalLinearArrangement (GT43) does exist, and Garey & Johnson documents the reduction GT43 → GT45. This gives a concrete planned connection to the existing graph. The issue also mentions R099 (→ RootedTreeStorageAssignment), though that target doesn't exist yet.

Pass: at least one connection to an existing problem.

Non-trivial

The problem is genuinely distinct from all 86 existing problem types. Its defining features:

• The rooted tree T is part of the solution, not the input — unlike all existing graph arrangement problems
• The ancestral path constraint (every edge must map to an ancestor-descendant pair) is unique
• The variable space (tree topology × bijection) is fundamentally different from linear arrangement

No existing problem captures this combination. Pass.

Correctness

Reference verification:

Reference	Status	Details
Gavril (1977) "Some NP-complete problems on graphs" CISS pp. 91-95	✅ Exists	Confirmed via Semantic Scholar. Cited by G&J for GT45. Full text unavailable — cannot independently verify the specific reduction from OLA
Garey, Johnson, Stockmeyer (1976) TCS 1(3):237-267	✅ Verified	All bibliographic details match. Proves NP-completeness of OLA
Adolphson & Hu (1973) SIAM J. Appl. Math 25(3):403-423	✅ Verified	All details match. O(n log n) for linear arrangement of rooted trees

Complexity concern: The issue states "No specialized exact algorithm is known" and gives O(n^n · n! · m) brute-force bound. No specialized exact algorithm was found in the literature either. However, the issue does not provide a concrete complexity string suitable for declare_variants!. For a satisfaction problem with brute-force enumeration, "2^num_vertices" or similar is needed (the current description is narrative, not a formula). Warn.

Well-written

Failures (unchanged from previous check):

1. Example 2 is self-contradictory: Starts with K=14, proposes a tree that fails the ancestral constraint on edge {2,3}, then switches to a chain with K=18. The example should present a single consistent instance — not a debugging narrative. Either fix the tree to satisfy all constraints with K=14, or restate the instance with the correct K from the start.

2. Variables section is imprecise: States "O(n) discrete choices" but the actual search space is n^(n-1) trees × n! permutations. This does not map to the dims() function. The issue should specify how the solution is encoded as a fixed-length configuration vector (e.g., Prüfer sequence + permutation → dims() = [n; 2n-2] or similar).

3. Schema missing size fields: No getter methods (num_vertices, num_edges) specified. These are required for declare_variants! overhead expressions and the overhead system.

4. No concrete declare_variants! complexity string: The complexity section provides a narrative description, not a formula like "2^num_vertices".

5. Brute-force solver mapping unclear: The BruteForce solver iterates over dims() configurations — but the issue doesn't explain how tree enumeration maps to this framework.

Recommendations

• Fix Example 2: present a single consistent instance with correct K value
• Specify concrete dims() encoding (Prüfer sequence + permutation, or alternative)
• Add num_vertices() and num_edges() as size field getters
• Provide a concrete complexity string (e.g., "num_vertices^num_vertices" or "2^num_vertices")
• Clarify how brute-force solver maps to the Problem trait's configuration space

[isPANN]

Fix-issue changelog

• Variables section: Replaced vague "O(n) discrete choices" with precise parent-array + permutation encoding (2n variables, each in [0,n))
• Schema: Added size fields num_vertices() and num_edges()
• Complexity: Added concrete declare_variants! string "2^num_vertices"
• Example 2: Replaced self-contradictory example (K changed mid-example) with clean triangle+path instance (5 vertices, K=7) showing optimal (total=6), suboptimal feasible (total=7), and infeasible (total=8) arrangements
• How to solve: Added explanation of how brute-force maps to Problem trait via dims() = vec![n; 2*n]

Applied by /fix-issue.