[Model] IsomorphicSpanningTree

[isPANN]

---

name: Problem
about: Propose a new problem type
title: "[Model] IsomorphicSpanningTree"
labels: model
assignees: ''

Motivation

ISOMORPHIC SPANNING TREE (P84) from Garey & Johnson, A2 ND8. A classical NP-complete problem that generalizes the Hamiltonian path problem: finding a Hamiltonian path is equivalent to finding a spanning tree isomorphic to the path graph P_n. The problem remains NP-complete even for restricted tree types (paths, full binary trees, 3-stars).

Associated reduction rules:

• As target: R29 (HAMILTONIAN PATH -> ISOMORPHIC SPANNING TREE) -- the NP-completeness proof referenced in G&J (A2 ND8).
• As source: None found in the current rule set.

Definition

Name: IsomorphicSpanningTree
Canonical name: ISOMORPHIC SPANNING TREE (also: Spanning Tree Isomorphism, Spanning Subgraph Isomorphic to Tree)
Reference: Garey & Johnson, Computers and Intractability, A2 ND8

Mathematical definition:

INSTANCE: Graph G = (V,E), tree T = (VT,ET).
QUESTION: Does G contain a spanning tree isomorphic to T?

Variables

• Count: n = |V| = |VT| variables, encoding a bijection (permutation) from VT to V.
• Per-variable domain: Each variable maps a tree vertex to a graph vertex, domain = {0, 1, ..., n-1}.
• Meaning: The variable assignment defines a bijection pi: VT -> V such that for every edge {u,v} in ET, {pi(u), pi(v)} is an edge in E. A valid assignment witnesses a spanning subgraph of G that is isomorphic to T.

Schema (data type)

Type name: IsomorphicSpanningTree<G>
Variants: graph type parameter G

Field	Type	Description
graph	G	The host graph G in which a spanning tree is sought
tree	G	The target tree T that the spanning tree must be isomorphic to

Size fields: num_vertices() (= |V(G)|)

Notes:

• This is a satisfaction (decision) problem: Metric = bool, implementing SatisfactionProblem.
• Precondition: |V(G)| = |V(T)| and T must be a tree (connected, |VT|-1 edges).
• No weight type is needed (the question is purely structural).
• The tree field stores T as a graph; a runtime check or type-level guarantee ensures it is indeed a tree.

Complexity

• Best known exact algorithm: The general case reduces to subgraph isomorphism, which can be solved in O*(2^n) time by brute-force enumeration of all permutations. This is the naive upper bound; no faster algorithm is known for arbitrary target trees. For the special case where T is a path (Hamiltonian Path), the best algorithm is Bjorklund's randomized O*(1.657^n) time.
• Special cases:
  • T = path: equivalent to Hamiltonian Path, O*(1.657^n) randomized (Bjorklund, 2014).
  • T = full binary tree: NP-complete (Papadimitriou and Yannakakis, 1982).
  • T = 3-star: NP-complete (Garey and Johnson).
  • T = 2-star: polynomial time via graph matching.
• NP-completeness: NP-complete (Garey and Johnson, 1979, ND8). Transformation from HAMILTONIAN PATH.
• declare_variants! complexity string: "2^num_vertices" (brute-force permutation enumeration over all n! bijections, bounded by 2^n).
• References:
  • Garey, M.R. and Johnson, D.S. (1979). Computers and Intractability. W.H. Freeman.
  • Papadimitriou, C.H. and Yannakakis, M. (1982). "The complexity of restricted spanning tree problems". Journal of the ACM 29(2):285–309.
  • Bjorklund, A. (2014). "Determinant Sums for Undirected Hamiltonicity". SIAM J. Computing 43(1):280-299.

Extra Remark

Full book text:

INSTANCE: Graph G = (V,E), tree T = (VT,ET).
QUESTION: Does G contain a spanning tree isomorphic to T?

Reference: Transformation from HAMILTONIAN PATH.
Comment: Remains NP-complete even if (a) T is a path, (b) T is a full binary tree [Papadimitriou and Yannakakis, 1982], or if (c) T is a 3-star (that is, VT = {v0} union {ui,vi,wi: 1 <= i <= n}, ET = {{v0,ui},{ui,vi},{vi,wi}: 1 <= i <= n}) [Garey and Johnson, ----]. Solvable in polynomial time by graph matching if G is a 2-star. For a classification of the complexity of this problem for other types of trees, see [Papadimitriou and Yannakakis, 1982].

How to solve

• It can be solved by (existing) bruteforce -- enumerate all permutations pi: VT -> V and check if the induced edge set is a subset of E.
• It can be solved by reducing to integer programming.
• Other: For T = path, use Held-Karp DP in O(n^2 * 2^n). For general T, use backtracking with constraint propagation (prune based on degree sequence compatibility).

Example Instance

Instance 1 (YES, tree = caterpillar):
Graph G with 7 vertices {0, 1, 2, 3, 4, 5, 6} and 12 edges:

• Edges: {0,1}, {0,2}, {0,3}, {1,2}, {1,4}, {2,3}, {2,5}, {3,6}, {4,5}, {4,6}, {5,6}, {1,3}
• Tree T (caterpillar): vertices {a, b, c, d, e, f, g}, edges {a,b}, {b,c}, {c,d}, {d,e}, {b,f}, {c,g}
  • Degree sequence of T: a:1, b:3, c:3, d:2, e:1, f:1, g:1
• Solution: pi: a→0, b→1, c→2, d→3, e→6, f→4, g→5.
  • {a,b} → {0,1} ✓, {b,c} → {1,2} ✓, {c,d} → {2,3} ✓, {d,e} → {3,6} ✓, {b,f} → {1,4} ✓, {c,g} → {2,5} ✓.
  • All 6 tree edges map to graph edges. All 7 vertices used. Valid.
• Answer: YES.

Instance 2 (NO, tree = star K_{1,6}):
Graph G with 7 vertices {0, 1, 2, 3, 4, 5, 6} and 9 edges:

• Edges: {0,1}, {1,2}, {2,3}, {3,4}, {4,5}, {5,6}, {0,6}, {0,3}, {3,6}
• Tree T = K_{1,6} (star with center and 6 leaves): center c, leaves l1..l6. Edges: {c,l1}, ..., {c,l6}.
  • T requires a vertex of degree 6. In G, maximum degree is: 0 has degree 3 ({0,1},{0,6},{0,3}), 3 has degree 4 ({2,3},{3,4},{0,3},{3,6}). No vertex has degree >= 6.
• Answer: NO (no vertex has sufficient degree to serve as the star center).

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in reduction graph; connects to Hamiltonian Path
Non-trivial	✅ Pass	Distinct satisfaction problem with unique two-graph input structure
Correctness	⚠️ Warn	Papadimitriou & Yannakakis reference has wrong year and title; complexity bound loosely stated
Well-written	⚠️ Warn	Example 1 solution mapping initially has errors (self-corrected); variable encoding section is ambiguous between two formulations

Overall: 2 passed, 0 failed, 2 warnings

---

Usefulness

Pass. The problem IsomorphicSpanningTree does not exist in the current reduction graph (confirmed via pred show). It is a classical NP-complete problem (Garey & Johnson ND8) that generalizes Hamiltonian Path — finding a Hamiltonian path is equivalent to finding a spanning tree isomorphic to the path graph P_n. The issue identifies a concrete incoming reduction (Hamiltonian Path → Isomorphic Spanning Tree) which would connect it to the existing graph. No outgoing reductions are proposed yet, but the problem is general enough that future reductions are plausible.

Non-trivial

Pass. This is a genuinely distinct problem from everything currently implemented. It requires two graph inputs (host graph G and target tree T) and asks whether G contains a spanning tree isomorphic to T. No existing problem in the codebase has this two-graph satisfaction structure. It is not a variant of any existing problem — it is a proper generalization of Hamiltonian Path (which is itself not yet implemented) and involves subgraph isomorphism constraints that are structurally different from all 24 current problem types.

Correctness

Warn. Several reference issues found (none fatal, but should be corrected):

1. Papadimitriou & Yannakakis citation: wrong year and title. The issue cites: "Papadimitriou, C.H. and Yannakakis, M. (1978). 'On the complexity of minimum spanning tree problems'." The actual paper is: "The complexity of restricted spanning tree problems", published in Journal of the ACM, Volume 29, Issue 2, pages 285–309, 1982 (not 1978). There may have been a 1977–1978 conference/manuscript version, but the published year is 1982 and the title is different from what is cited.

2. Bjorklund reference: confirmed. "Determinant Sums for Undirected Hamiltonicity", SIAM J. Computing 43(1):280–299, 2014. The O*(1.657^n) randomized bound for Hamiltonian cycle/path is correct.

3. Garey & Johnson ND8: confirmed. The problem definition (instance: graph G, tree T; question: does G have a spanning tree isomorphic to T?) matches the standard G&J formulation.

4. General complexity claim is loose. The issue states "no improvement over O*(2^n) is known for arbitrary trees" for the general isomorphic spanning tree problem. This is plausible but not backed by a specific citation. The O*(2^n) bound from brute-force subgraph isomorphism is a reasonable upper bound, but it would be stronger to cite a specific reference or note this is simply the naive bound.

Well-written

Warn. The issue is mostly complete and well-structured, but has some issues:

4a: Information Completeness

All required sections are present and substantive. The Definition, Schema, Complexity, How to solve, and Example Instance sections are all filled in. Good.

4b: Definition Completeness

The formal definition is clear and follows the standard G&J formulation. The feasibility constraint (spanning tree of G isomorphic to T) and the satisfaction nature (Metric = bool) are correctly identified. Good.

4c: Symbol and Notation Consistency

• The Variables section presents two different encodings (permutation-based and edge-selection-based) without clearly committing to one. The Schema section implies the implementation will use the two-graph representation, but the variable encoding needs to be pinned down for implementation. This ambiguity should be resolved.
• The tree field is stored as SimpleGraph — the issue correctly notes a runtime check is needed to ensure it is actually a tree, which is reasonable.

4d: Example Quality

• Example 1 (YES): The worked example has a false start ("Map b->2, c->1, d->4, a->3, e->5, f->0, g->3...") which is self-corrected to the valid mapping pi: a→0, b→1, c→2, d→3, e→6, f→4, g→5. The final verification is correct — all 6 tree edges map to graph edges. However, the false start with "g->3" (duplicate vertex) in the text is sloppy and should be cleaned up.
• Example 2 (NO): Clean and correct. The degree argument (no vertex has degree ≥ 6, so K_{1,6} cannot be embedded) is valid and easy to verify.

Recommendations

• Fix the Papadimitriou & Yannakakis citation to: "The complexity of restricted spanning tree problems", JACM 29(2):285–309, 1982.
• Remove the false-start mapping text in Example 1, keeping only the correct solution.
• Commit to one variable encoding (permutation-based is more natural for this problem) and clarify the dims/domain accordingly.
• Consider adding a complexity string for declare_variants! — for general trees, "2^num_vertices" is the naive bound. Note that no better bound is known for the general case (only for T = path via Bjorklund).