[Model] KthBestSpanningTree

[isPANN]

---

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

Motivation

Kth BEST SPANNING TREE from Garey & Johnson, A2 ND9. An NP-hard problem (marked with (*) in G&J, meaning it is not known to be in NP) that asks whether a weighted graph has K distinct spanning trees each with total weight at most B. The problem generalizes minimum spanning tree enumeration and has connections to network reliability and sensitivity analysis. It can be solved in pseudo-polynomial time via Lawler's K-best enumeration procedure (1972).

Associated reduction rules:

• As target: R30 (HAMILTONIAN PATH -> KTH BEST SPANNING TREE) -- Turing reduction establishing NP-hardness (Johnson and Kashdan, 1976).
• As source: None found in the current rule set.

Definition

Name: KthBestSpanningTree

Canonical name: K^th BEST SPANNING TREE (also: K Minimum Spanning Trees, Multiple Minimum Weight Spanning Trees)
Reference: Garey & Johnson, Computers and Intractability, A2 ND9

Mathematical definition:

INSTANCE: Graph G = (V,E), weight w(e) in Z_0^+ for each e in E, positive integers K and B.
QUESTION: Are there K distinct spanning trees for G, each having total weight B or less?

Variables

• Count: K * m = K * |E| binary variables, organized as K blocks of m edge variables each. Each block encodes one candidate spanning tree.
• Per-variable domain: {0, 1} for each edge in each block: 1 if included, 0 otherwise.
• dims() implementation: vec![2; self.k * self.graph.num_edges()] — K * m binary variables encoding K candidate spanning trees.
• Meaning: A configuration encodes K subsets of edges (one per block). The evaluate() function checks: (1) each block forms a valid spanning tree (connected, acyclic, exactly n-1 edges), (2) each spanning tree has total weight at most B, and (3) all K spanning trees are mutually distinct (i.e., no two blocks encode the same edge subset). Returns true if all three conditions hold.

Schema (data type)

Type name: KthBestSpanningTree<W>
Variants: weight type W

Field	Type	Description
graph	SimpleGraph	The undirected graph G = (V, E)
weights	Vec<W>	Edge weights w(e) for each edge in E, non-negative
k	usize	The number K of distinct spanning trees required
b	W	The weight bound B; each spanning tree must have total weight <= B

Size fields (for overhead expressions): num_vertices, num_edges, k, b

Notes:

• This is a satisfaction (decision) problem: Metric = bool, implementing SatisfactionProblem.
• Weight type W should implement WeightElement (typically i32 for non-negative integer weights).
• The problem is NOT known to be in NP (certificate may require listing K spanning trees, which could be exponential in size).
• For fixed K, the problem is polynomial-time solvable.
• No graph type parameter G is needed — the problem operates on SimpleGraph directly (no known graph-restricted variants in G&J).

Complexity

• Best known exact algorithm:
  • For variable K (part of input): NP-hard (Turing reduction from Hamiltonian Path; Johnson and Kashdan, 1976). A brute-force approach enumerates all 2^(K*m) configurations (K blocks of m edge variables), giving worst-case O(2^(num_edges * k)).
  • For fixed K: Polynomial time. Lawler's procedure (1972) finds the K best solutions to discrete optimization problems. Combined with MST algorithms, this gives polynomial-time complexity for any fixed K.
  • Eppstein (1992) improved K-best spanning tree enumeration to O(m log beta(m,n) + k^2) for general weighted graphs and O(n + k^2) for planar graphs, where beta is a slowly-growing function related to the inverse Ackermann function.
• Pseudo-polynomial time: The problem can be solved in time polynomial in |V|, K, log B, and max{log w(e)} (Lawler, 1972).
• Related enumeration: The problem of counting ALL spanning trees of weight <= B is #P-complete. However, the unweighted enumeration problem (counting all spanning trees) is polynomial via Kirchhoff's matrix tree theorem.
• NP-hardness status: NP-hard but not known to be in NP (marked (*) in G&J).

declare_variants! guidance:

crate::declare_variants! {
    KthBestSpanningTree<i32> => "2^(num_edges * k)",
}

Since K is part of the input and the problem is NP-hard, the worst-case complexity is exponential in the number of edges times K (brute-force enumeration of all K-block edge subset configurations).

• References:
  • Johnson, D.B. and Kashdan, S.D. (1976). "Lower bounds for selection in X+Y and other multisets." Penn State CS Dept. Technical Report. (Published as JACM, 1978.)
  • Lawler, E.L. (1972). "A procedure for computing the K best solutions to discrete optimization problems." Management Science 18, pp. 401-405.
  • Eppstein, D. (1992). "Finding the k Smallest Spanning Trees." BIT Numerical Mathematics 32, pp. 237-248.
  • Harary, F. and Palmer, E.M. (1973). "Graphical Enumeration." Academic Press.

Extra Remark

Full book text:

INSTANCE: Graph G = (V,E), weight w(e) in Z0+ for each e in E, positive integers K and B.
QUESTION: Are there K distinct spanning trees for G, each having total weight B or less?

Reference: [Johnson and Kashdan, 1976]. Turing reduction from HAMILTONIAN PATH.
Comment: Not known to be in NP. Can be solved in pseudo-polynomial time (polynomial in |V|, K, log B, max {log w(e): e in E}) [Lawler, 1972], and hence in polynomial time for any fixed value of K. The corresponding enumeration problem is #P-complete. However, the unweighted case of the enumeration problem is solvable in polynomial time (e.g., see [Harary and Palmer, 1973]).

How to solve

• It can be solved by (existing) bruteforce -- enumerate all possible spanning trees (subsets of n-1 edges forming a tree), count those with weight <= B, check if count >= K.
• It can be solved by reducing to integer programming -- ILP with K sets of binary edge variables, tree constraints (flow-based or subtour elimination), weight constraints, and distinctness constraints.
• Other: Lawler's K-best enumeration (1972): iteratively find the next-best spanning tree by partitioning the solution space. Eppstein's improved algorithm (1992) for faster K-best spanning tree enumeration.

Example Instance

Instance 1 (YES):
Graph G with 5 vertices {0, 1, 2, 3, 4} and 8 edges with weights:

• {0,1}: w=2, {0,2}: w=3, {1,2}: w=1, {1,3}: w=4, {2,3}: w=2, {2,4}: w=5, {3,4}: w=3, {0,4}: w=6
• K = 3, B = 12

Spanning trees (need 4 edges each, total weight <= 12):

1. MST: {1,2}(1) + {2,3}(2) + {0,1}(2) + {3,4}(3) = weight 8. Edges: {0,1},{1,2},{2,3},{3,4}.
2. 2nd best: Replace {2,3}(2) with {1,3}(4): {0,1}(2) + {1,2}(1) + {1,3}(4) + {3,4}(3) = weight 10. Edges: {0,1},{1,2},{1,3},{3,4}.
3. 3rd best: Replace {0,1}(2) with {0,2}(3) in MST: {0,2}(3) + {1,2}(1) + {2,3}(2) + {3,4}(3) = weight 9. Edges: {0,2},{1,2},{2,3},{3,4}.

All three have weight <= 12. Are they distinct? Tree 1 has edges {0,1},{1,2},{2,3},{3,4}. Tree 3 has edges {0,2},{1,2},{2,3},{3,4}. Different (edge {0,1} vs {0,2}). Tree 2 has {0,1},{1,2},{1,3},{3,4}. Different from both.

Answer: YES (3 distinct spanning trees with weight <= 12 exist).

Instance 2 (NO):
Graph G with 4 vertices {0, 1, 2, 3} forming a path: {0,1}: w=1, {1,2}: w=1, {2,3}: w=1.

• This graph is already a tree (only 3 edges = n-1).
• K = 2, B = 3.
• Only ONE spanning tree exists (the graph itself, weight 3).
• Answer: NO (need 2 distinct spanning trees, but only 1 exists).

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in reduction graph
Non-trivial	✅ Pass	Distinct feasibility constraints from all existing problems
Correctness	⚠️ Warn	Eppstein (1992) complexity bounds appear incorrectly stated; Johnson & Kashdan reference not independently verified
Well-written	⚠️ Warn	Minor issues: naming convention, complexity section accuracy, variable encoding discussion

Overall: 2 passed, 0 failed, 2 warnings

---

Usefulness

Pass. KthBestSpanningTree does not exist in the codebase. The problem is listed in Garey & Johnson (A2 ND9) and is a genuine NP-hard problem (not known to be in NP). The motivation mentions connections to network reliability and sensitivity analysis, and an associated reduction rule (Hamiltonian Path -> KthBestSpanningTree) is identified. The problem would add a new node to the reduction graph.

Non-trivial

Pass. This is a decision problem asking whether K distinct spanning trees exist with bounded total weight. Its feasibility constraints (multiple distinct spanning subgraphs, each acyclic and connected with n-1 edges, each with bounded weight) are genuinely different from all 24 existing problems in the codebase. It is not a variant or renaming of any existing problem.

Correctness

Warn. Verification results per reference:

1. Lawler (1972) — Verified. "A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem," Management Science 18(7), pp. 401-405. Confirmed via INFORMS publisher page. The claim that it enables pseudo-polynomial time solution is consistent with the paper's contribution.

2. Eppstein (1992) — Paper verified, but complexity bounds in the issue appear incorrect. The paper "Finding the k Smallest Spanning Trees" (BIT 32, pp. 237-248) is confirmed. However, the issue states:

   • Unweighted: O(m * alpha(n) + K * n^(1/2))
   • Weighted: O(m * log(m/n) + min(K*n, K^(1/2)*m))

   The actual main result from Eppstein (1992) is O(m log beta(m,n) + k^2) for general graphs and O(n + k^2) for planar graphs. The bounds cited in the issue may be from a different Eppstein paper (possibly "Finding the k Shortest Paths," 1998) or from a later improved result. This should be corrected or a precise citation to the specific theorem should be provided.

3. Johnson and Kashdan (1976) — Not independently verified. The issue cites "Lower bounds for selection in X+Y and other multisets," Penn State CS Dept. The published version appears to be in JACM (1978), not 1976. The paper's title concerns selection in multisets (X+Y), not spanning trees directly. Garey & Johnson cite this work for the Turing reduction from Hamiltonian Path establishing NP-hardness, which is plausible (K-best spanning tree enumeration relates to selection in Cartesian sums of edge weights), but the connection is indirect and cannot be fully verified without consulting G&J directly.

4. Harary and Palmer (1973) — Plausible. "Graphical Enumeration" (Academic Press) is a well-known textbook. The claim that unweighted spanning tree counting is polynomial via Kirchhoff's matrix tree theorem is a standard result.

Well-written

Warn. The issue is generally well-structured and follows the template, but has several issues:

Template completeness: All required sections (Motivation, Name, Reference, Definition, Variables, Schema, Complexity, How to solve, Example Instance) are present and substantive. Good.

Naming convention issue: The problem is a satisfaction/decision problem, so the name KthBestSpanningTree is acceptable (no Maximum/Minimum prefix needed). However, it may be more natural to call it KBestSpanningTree or KthBestSpanningTrees (plural, since the question asks about K trees). Minor point.

Complexity section issues:

• The Eppstein bounds appear incorrectly attributed (see Correctness above). This needs correction.
• The section mixes fixed-K (polynomial) and variable-K (NP-hard) cases, which is good for context, but the complexity string for declare_variants! is not specified. Since K is part of the input and the problem is NP-hard, a worst-case complexity bound for the general case should be stated explicitly.

Variable encoding discussion: The Variables section discusses K * m total variables, which is reasonable for a brute-force encoding. However, the note "though the decision problem only asks for existence" is somewhat confusing. The dims() implementation will need to be clarified — a natural encoding uses K * |E| binary variables, but this may be exponentially large for large K. The issue should clarify the intended encoding for the Problem trait implementation.

Symbol consistency: Generally good. The definition uses G = (V,E), w(e), K, B consistently across sections. The schema field b uses type W which matches the weight type.

Example quality: Two examples provided (YES and NO instances). The YES instance is well-worked with 3 spanning trees explicitly enumerated and verified. The NO instance is simple but effective (a tree graph with only one spanning tree). Good quality overall.

Recommendations

• Correct the Eppstein (1992) complexity bounds or provide the exact theorem number from the paper
• Clarify the intended dims() encoding for the Problem trait — e.g., will it enumerate subsets of edges for each of the K trees, or use a different representation?
• Add a concrete worst-case complexity string for declare_variants! (since K is part of the input, a brute-force bound like 2^num_edges or a tighter bound should be specified)
• Consider whether the Johnson & Kashdan reference year should be 1978 (JACM publication) rather than 1976 (technical report)