[Model] MaximumLeafSpanningTree

[isPANN]

Motivation

MAXIMUM LEAF SPANNING TREE (ND2) from Garey & Johnson, A2. Given a graph G, find a spanning tree that maximizes the number of leaves (degree-1 vertices). NP-hard even for regular degree-4 graphs and planar graphs with maximum degree 4. Dual to degree-constrained spanning tree problems. The non-leaf vertices of a maximum-leaf spanning tree form a minimum connected dominating set. Applications in network broadcast optimization where leaf nodes represent endpoints.

Definition

Name: MaximumLeafSpanningTree
Reference: Garey & Johnson, Computers and Intractability, A2 ND2

Mathematical definition:

INSTANCE: Graph G = (V, E).
OBJECTIVE: Find a spanning tree T for G that maximizes the number of leaves (vertices of degree 1).

Variables

• Count: m = |E| (one binary variable per edge)
• Per-variable domain: {0, 1}
• Meaning: Whether each edge is included in the spanning tree. The selected edges must form a spanning tree, and the objective is to maximize the number of degree-1 vertices in the tree.

Schema

Type name: MaximumLeafSpanningTree
Variants: graph: SimpleGraph

Field	Type	Description
graph	SimpleGraph	The input graph G = (V, E)

Complexity

• Best known exact algorithm: O*(1.8966^n) by Fernau, Kneis, Kratsch, Langer, Liedloff, Raible, and Rossmanith (Theoretical Computer Science, vol. 412, pp. 6290–6302, 2011). NP-hard even for graphs that are regular of degree 4 or planar with maximum degree 4 (Garey and Johnson). Approximation: 2-approximation by Solis-Oba (ESA 1998). Connected graphs with minimum degree ≥ 3 have spanning trees with at least n/4 + 2 leaves.
• Special cases:
  • Star graph K_{1,n-1}: always has n-1 leaves.
  • Path graph P_n: every spanning tree is P_n itself, with 2 leaves.

Extra Remark

Full book text:

INSTANCE: Graph G = (V, E), positive integer K <= |V|.
QUESTION: Is there a spanning tree for G that has K or more leaves?

Reference: [Garey and Johnson, ----].
Comment: NP-complete even for graphs that are regular of degree 4 or planar and have maximum degree 4.

Note: The original G&J formulation is a decision problem with threshold K. We use the equivalent optimization formulation: maximize the number of leaves in a spanning tree.

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all spanning trees of G; count degree-1 vertices in each; return the maximum.)
• It can be solved by reducing to integer programming. (ILP with binary edge variables for tree selection, binary vertex variables for leaf indicators, subtour elimination, degree-leaf linking constraints; maximize leaf count.) See companion issue [Rule] MaximumLeafSpanningTree to ILP #965.
• Other:

Reduction Rule Crossref

• [Rule] MaximumLeafSpanningTree to ILP #965 — [Rule] MaximumLeafSpanningTree to ILP (direct ILP formulation)

Example Instance

Input:
Graph G with V = {v0, v1, v2, v3, v4, v5} (n = 6) and 9 edges:
E = {(v0,v1), (v0,v2), (v0,v3), (v1,v4), (v2,v4), (v2,v5), (v3,v5), (v4,v5), (v1,v3)}

Optimal spanning tree T: edges {(v0,v1), (v0,v2), (v0,v3), (v2,v4), (v2,v5)}

• v0: degree 3 (connected to v1, v2, v3) — internal
• v1: degree 1 — leaf ✓
• v2: degree 3 (connected to v0, v4, v5) — internal
• v3: degree 1 — leaf ✓
• v4: degree 1 — leaf ✓
• v5: degree 1 — leaf ✓

This is a "double star" tree with hubs at v0 and v2. Leaves: {v1, v3, v4, v5} = 4 leaves.

Suboptimal tree T2: edges {(v0,v1), (v1,v4), (v4,v5), (v5,v2), (v2,v3)} — a path

• All internal vertices have degree 2; only endpoints v0 and v3 are leaves = 2 leaves.

Why 5 leaves is impossible: A spanning tree on 6 vertices has 5 edges. If 5 vertices were leaves (degree 1), the remaining vertex would need degree 5. But the maximum degree in G is 4 (at v0: edges to v1, v2, v3 only — degree 3). So at most 4 leaves are achievable.

Expected Outcome

Optimal value: Max(4) — the maximum number of leaves in any spanning tree is 4. The graph has 75 spanning trees with 3 distinct leaf counts: 30 trees with 2 leaves, 42 trees with 3 leaves, and 3 trees with 4 leaves.

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	❌ Fail	No planned reduction connecting this problem to the existing graph
Non-trivial	✅ Pass	Distinct feasibility constraints (spanning tree + leaf count) from all existing problems
Correctness	❌ Fail	Multiple incorrect literature claims (see details)
Well-written	❌ Fail	Broken example, missing Expected Outcome, inconsistent decision-vs-optimization framing

Overall: 1 passed, 0 warnings, 3 failed

---

Usefulness

The problem MaximumLeafSpanningTree does not exist in the codebase. However, the issue does not mention any planned reduction rule connecting this problem to the existing reduction graph. A problem without any planned reduction to/from an existing problem is an orphan node with no value in the reduction graph. At least one concrete reduction (e.g., to/from Connected Dominating Set, or to ILP) must be specified.

Non-trivial

This is a genuinely distinct problem. The feasibility constraint (subset of edges must form a spanning tree) combined with the leaf-count objective is not equivalent to any existing problem in the codebase. The related problems (BoundedComponentSpanningForest, SteinerTree, IsomorphicSpanningTree, etc.) have different objectives and constraints.

Correctness

Several factual errors in the Complexity section:

1. Complexity string "2^num_vertices" is too conservative. The best known exact algorithm runs in O*(1.8966^n) time, by Fernau, Kneis, Kratsch, Langer, Liedloff, Raible, and Rossmanith (Theoretical Computer Science, vol. 412, pp. 6290-6302, 2011). The complexity string should be "1.8966^num_vertices".

2. Wrong attribution for O*(6.75^k) FPT algorithm. The issue claims "Fernau et al. (2011) give an O*(6.75^k) FPT algorithm parameterized by the number of internal (non-leaf) vertices." The O*(6.75^k) bound is attributed to Bonsma and Zickfeld, not Fernau et al. Fernau et al. (2011) gave the O*(1.8966^n) exact algorithm. Later FPT improvements include Daligault et al. achieving O*(3.72^k).

3. Wrong attribution for 2-approximation. The issue claims "2-approximation by Lu and Ravi (1998)." The 2-approximation is by Solis-Oba (1998), published at ESA 1998. Lu and Ravi (1998) gave a 3-approximation running in near-linear time.

4. Thomasse (2001) attribution is unclear. The bound l(n,3) >= n/4 + 2 for connected graphs with minimum degree >= 3 is a known result, but the attribution to "Thomasse (2001)" specifically could not be verified. Earlier work by Griggs and Wu may be the original source. This is a minor concern but should be cited precisely.

Well-written

Multiple issues:

1. Missing "Expected Outcome" section. The template requires a concrete optimal solution and optimal objective value. The issue has no Expected Outcome section at all.

2. Broken example. The example is incoherent — the author tries multiple spanning trees, fails to achieve K=4, and concludes K=3 is the maximum without providing a clear, fully-worked instance. The example should present one clean instance with a definitive optimal solution. As written, it reads like debugging notes rather than a worked example.

3. Decision vs. optimization inconsistency. The Definition section frames this as a decision problem ("QUESTION: Is there a spanning tree... with at least K leaves?") but the Variables section says "The objective is to maximize the number of leaves" and the name uses Maximum prefix (optimization). The issue must pick one framing consistently. Given the Maximum prefix and the codebase conventions, this should be an optimization problem with Value = Max<i64>.

4. num_leaves field semantics unclear. The Schema has a field num_leaves described as "The minimum number of required leaves K", but for an optimization problem the threshold K is not needed — the problem should maximize the leaf count over all spanning trees. If this is a decision problem, the name should not start with Maximum.

5. No planned reductions mentioned. The Motivation section mentions "dual to degree-constrained spanning tree problems" and "applications in network broadcast optimization" but never names a concrete reduction to/from an existing problem.

6. Example is not round-trip testable. Even after fixing the broken example, an instance with only 3 leaves as optimal (on 6 vertices) may be too simple for meaningful round-trip testing. The example should have multiple spanning trees with different leaf counts to validate that the correct optimum is found.

Recommendations

• The Maximum Leaf Spanning Tree problem is equivalent to the Minimum Connected Dominating Set problem (complement: non-leaf vertices form a connected dominating set). Consider mentioning this equivalence and planning a reduction between them.
• Use the Fernau et al. (2011) complexity of "1.8966^num_vertices" for the complexity string.
• Correct the 2-approximation attribution to Solis-Oba (1998).
• Reframe consistently as an optimization problem: remove the num_leaves threshold field, use Value = Max<i64>, and state the problem as "find a spanning tree maximizing the number of degree-1 vertices."
• Provide a clean example with 7-8 vertices where the optimal leaf count is unambiguous and at least 2-3 suboptimal spanning trees exist.

[isPANN]

Converted from decision to optimization framing: removed bound K, objective is now to maximize the number of leaves in a spanning tree. Removed num_leaves field from schema. Updated example to show optimal value rather than yes/no answer.