The Path-Extremal Conjecture for Zero Forcing: Distance-Hereditary Graphs and a Split-Decomposition Reduction
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: I'm Tom.
Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.
Tom: We're looking at the paper: "The Path-Extremal Conjecture for Zero Forcing".
Jane: Here's the gist of the paper. For an n-vertex graph G, let z(G; k) denote the number of zero forcing sets of size k.
Tom: The paper proves that this path-extremal conjecture holds for distance-hereditary graphs and extends the previously known tree case to a much larger class that includes all trees and all cographs.
Jane: Path-Extremal Conjecture Statement The central conjecture asserts that the path Pn maximizes these numbers coefficientwise among all n-vertex graphs.
Tom: This is equivalent to stating that the zero forcing polynomial of every n-vertex graph should be coefficientwise dominated by that of Pn.
Paper summary: Tom: So we're looking at this paper now titled "The Path-Extremal Conjecture for Zero Forcing: Distance-Hereditary Graphs and a Split-Decomposition Reduction".
Jane: Right, Tom. Essentially the big claim here is that the path graph Pn maximizes the number of zero forcing sets of size k coefficientwise among all graphs with n vertices.
Tom: That means for any other graph we're looking at, its zero forcing polynomial should be dominated by the one from Pn >
Lu: This paper tackles that conjecture and proves it for distance-hereditary graphs one <ref:2605.10836#pg1>.
Jane: Distance-hereditary graphs are a specific class of graphs where structural properties are very well understood.
Tom: So they're using these structural properties to show that the path graph is indeed the extremal case for this counting problem.
Meng: But the paper doesn't just stop at distance-hereditary graphs though. They use something called canonical split decomposition to push the idea further out into a much bigger class of graphs <ref:2605.10836#pg3>.
Jane: That means they're trying to extend this result beyond just those distance-hereditary structures, which include all trees and all cographs.
Lalam: They establish a theorem that says if you have a fixed split-prime graph H and all of its induced subgraphs are path-extremal then every connected graph whose canonical split decomposition has a unique prime bag whose label graph is isomorphic to H is also path-extremal <ref:2605.10836#pg3>.
Tom: That sounds like they're building up from smaller, known extremal graphs to larger ones.
Jane: It’s a really interesting approach because it links the structure of the graph decomposition directly to the forcing property we are studying.
Lu: They also have a corollary that boils this down to a finite verification problem on bounded-order prime cores for each fixed size m <ref:2605.10836#pg3>.
Tom: Finite verification sounds way better than checking every single graph, which is what the original conjecture implies.
Meng: I'm curious about the mechanism they use to get from that infinite family down to a finite check, because that's where most of these structural reductions can break at scale <ref:2605.10836#pg3>.
Jane: The paper suggests that you only need to check the prime bags up to a certain size m if you verify everything below that threshold for every split-prime graph <ref:2605.10836#pg3>.
Paper summary: Lu: And they use a strategy involving twin pairs and leaf recurrence to show why distance-hereditary graphs are the natural starting point for this whole argument <ref:2605.10836#pg1>.
Tom: So it’s using those twin pairs as some kind of obstruction, and then using a recurrence based on leaves to set lower bounds on non-forcing sets <ref:2605.10836#pg1>.
Jane: And that leads to the idea that every distance-hereditary graph contains either a leaf or a twin pair, which is how they handle those obstructions <ref:2605.10836#pg8>.
Meng: I'm trying to think about deployment here. If we are building models on these structures, how does this structural property translate into something that matters for real-world performance or computational cost <ref:2605.10836#pg3>?
Tom: Well, the implication is that for these specific graph families, we have a strong upper bound on how many ways you can force things compared to a path graph.
Jane: And the paper does extend this beyond just distance-hereditary graphs to cover all trees and cographs using this split decomposition method <ref:2605.10836#pg3>.
Lu: That’s significant because it shows the structural constraints they found apply to a much wider range of graph types than previously thought.
Tom: It’s interesting that they manage to connect these counting problems with structural decompositions like split decomposition, which is a bit unusual for this kind of extremal problem.
Meng: If we were building an AI system on these graphs, we'd want the structure to be simple enough to analyze but complex enough to model real data.
Jane: The paper points out that the key structural ingredients are those twin pairs and leaf recurrences, which reappear in more general arguments involving split decomposition <ref:2605.10836#pg3>.
Lu: They show that if you have a unique prime bag, you can reduce the problem to checking only bags up to size m <ref:2605.10836#pg4>.
Tom: So the main point is this reduction: instead of checking an infinite number of possibilities for large graphs, we only need to check bounded-order prime cores if we know how big those cores can be <ref:2605.10836#pg4>.
Jane: That turns it into a finite verification problem, which is much more appealing computationally.
Meng: But what about the practical application of checking these bounded cores? If m is large, the number of possible structures we have to check might still be too big for a system to handle efficiently <ref:2605.10836#pg4>.
Paper summary: Tom: That’s a valid concern, Meng. The reduction simplifies it, but the verification itself still has complexity tied to m.
Jane: And they confirm that this reduction is combinatorially natural and algorithmically appealing because it grounds the conjecture in finite verification on bounded-order prime cores <ref:2605.10836#pg3>.
Lu: They also show how to handle the case where there's a fixed split-prime graph H and all its induced subgraphs are path-extremal, which is Theorem two <ref:2605.10836#pg3>.
Tom: I’m interested in that structural induction they use in Theorem two where if you have every induced subgraph of H being path-extremal, then every connected graph in C(H) is also path-extremal <ref:2605.10836#pg3>.
Meng: That sounds like a powerful way to handle the recursive nature of these graphs.
Jane: They use Lemma fourteen to show that removing specific structures preserves membership in D(H), which is a technical tool for this induction <ref:2605.10836#pg4>.
Lalam: I see how that machinery helps prove Theorem two especially when they use Lemma twelve to show an isomorphism between Q and the label graph of P <ref:2605.10836#pg1>.
Tom: So they're using these structural tools—the twin pairs, the leaf recurrences, and the split decomposition—to prove that the path graph is extremal for distance-hereditary graphs <ref:2605.10836#pg1>.
Jane: It’s a solid foundation for understanding this counting problem on these specific graph types.
Lu: The big picture here is that they've provided a clear structural frontier: the twin pair obstruction and leaf recurrence are the core ingredients <ref:2605.10836#pg3>.
Tom: So, for future work, it looks like the next step is to move to unique-prime-bag families, which offers a different way to tackle the extension beyond distance-hereditary graphs <ref:2605.10836#pg4>.
Meng: If that reduction works well in practice for a model designer, it means we can rely on these finite checks for complex structures without having to simulate every single possibility <ref:2605.10836#pg4>.
Jane: It sounds like the paper gives us a very concrete direction for how to attack this conjecture moving forward.
Tom: Exactly. The conjecture itself is about coefficientwise domination, and proving it for distance-hereditary graphs sets up this powerful structural reduction that leads directly to that finite verification problem on bounded-order prime cores <ref:2605.10836#pg4>.
Conclusion: Tom: So we've looked at how they proved the path graph maximizes zero forcing sets for distance-hereditary graphs, and now we're wrapping up this paper, "The Path-Extremal Conjecture for Zero Forcing: Distance-Hereditary Graphs and a Split-Decomposition Reduction."
Jane: That paper really takes this idea—that the path graph is the most efficient structure—and shows how that logic extends beyond just distance-hereditary graphs into a much wider family of structures.
Lu: The main result here is this structural reduction. They take complex graphs and break them down using something called canonical split decomposition, and they find that if you check everything up to a certain size, say m, you can prove the property for the whole graph.
Meng: So what does that mean for me when I'm actually running a model? It means instead of trying to check every single graph structure, I only have to worry about checking these bounded prime cores if those cores don't get too big.
Tom: Exactly, Meng. It turns an infinite checking problem into a finite verification problem on bounded-order prime cores, which is way more appealing computationally because it gives us a concrete limit on how complex we need to check.
Jane: They use twin pairs and leaf recurrence as the key ingredients—the twin pairs create obstructions and the leaves give us recursive lower bounds on non-forcing sets.
Lu: That combination of twin pair obstruction and leaf recurrence is what makes distance-hereditary graphs a natural starting point for this whole argument, because those mechanisms show up in more general split decomposition proofs.
Meng: I see how that works. So the next logical step then is moving from just distance-hereditary graphs to these unique prime bag families they introduce using that decomposition method.
Tom: Right. This paper sets up a really clear structural frontier for further progress, showing how the twin pair obstruction and leaf recurrence are the core ingredients we need to focus on next.
University of California, San Diego
cs.DM
Submitted: 2026-05-11
Updated: 2026-11-12
Comments: This version strengthens the split-decomposition reduction: it allows arbitrarily many prime bags of order at most six, together with at most one additional prime bag whose label graph has every induced subgraph path-extremal, whereas the previous version restricted the total number of prime bags to at most one, subject to the same condition on its label graph. Also streamlined the exposition
Journal ref: 32nd International Computing and Combinatorics Conference (COCOON 2026), Lecture Notes in Computer Science, vol. 16835, pp. 409-422, Springer (2027)
DOI: 10.1007/978-981-92-3309-0_31
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Importance score: 77/100
The gist: For an n-vertex graph G, let z(G; k) denote the number of zero forcing sets of size k.
Key concepts
- Path-Extremal Conjecture
- This conjecture posits that the path graph $P_n$ maximizes the number of zero forcing sets of size $k$ among all $n$-vertex graphs. Proving it means showing that for any other graph, the zero forcing polynomial's coefficients are dominated by those of a path.
- Distance-Hereditary Graphs
- These are graphs where every induced subgraph is also distance-hereditary. The proof leverages structural properties like twin pairs and leaves to show that these graphs naturally satisfy the path-extremal conjecture through specific counting arguments.
- Split Decomposition
- This is a structural method used to break down a graph into simpler components called prime bags. The paper uses this decomposition, along with induction, to extend the path-extremality result from distance-hereditary graphs to more general connected graphs.
- Zero Forcing Sets ($z(G; k)$)
- A zero forcing set is a subset of vertices in a graph $G$ that can force all other vertices to become 'zero' using the zero forcing rule. The paper focuses on counting how many such sets of a specific size exist for different graphs.
Terminology
Summary
For an n-vertex graph G, let z(G; k) denote the number of zero forcing sets of size k. p. 0 The paper proves that this path-extremal conjecture holds for distance-hereditary graphs and extends the previously known tree case to a much larger class that includes all trees and all cographs. p. 0
Path-Extremal Conjecture Statement
The central conjecture asserts that the path Pn maximizes these numbers coefficientwise among all n-vertex graphs. This is equivalent to stating that the zero forcing polynomial of every n-vertex graph should be coefficientwise dominated by that of Pn. p. 0 The authors prove this pathextremal conjecture for distance-hereditary graphs. p. 0
Distance-Hereditary Graphs as a Positive Class
The proof for distance-hereditary graphs relies on two counting mechanisms: fort obstructions arising from twin pairs and a leaf recurrence.
-
Twin pairs produce small forts and hence many non-forcing sets. p. 1
-
Leaves give recursive lower bounds on the number of non-forcing sets. p. 1
The paper establishes that distance-hereditary graphs are a natural positive class for this strategy because they admit a one-vertex extension characterization via pendant, false-twin, and true-twin additions. p. 1
Extension via Split Decomposition
The second main result pushes the perspective beyond distance-hereditary settings using canonical split decomposition.
-
Theorem 2 shows that if a fixed split-prime graph H and all of its induced subgraphs are path-extremal, then every connected graph whose canonical split decomposition has a unique prime bag whose label graph is isomorphic to H is also path-extremal. p. 2
-
This leads to Corollary 4, which suggests a concrete hybrid strategy: combine structural induction on split decomposition with finite verification of bounded prime bases. p. 2
Structural Reduction and Bounded Verification
The reduction in Corollary 4 simplifies the conjecture on classes C≤m to a finite verification problem on bounded-order prime cores. This is achieved by showing that if every induced subgraph of every split-prime graph on at most m vertices is path-extremal, then so is every connected graph whose canonical split decomposition has a unique prime bag of size at most m. p. 0
Conclusion and Future Directions
The results identify a natural structural frontier for further progress by combining the fort obstruction from twin pairs and the leaf recurrence. The modularity of these ingredients makes distance-hereditary graphs a natural first test case, while unique-prime-bag families form the next meaningful level of generality. p. 2 The conjecture reduces to a finite verification problem on bounded-order prime cores. p. 0 The paper concludes that this reduction is combinatorially natural and algorithmically appealing. p. 2
Corollary 2 and Remark 1
Corollary 2 states that every tree and every cograph is path-extremal. Remark 1 notes that the proof of Theorem 1 isolates two mechanisms that reappear in more general split-decomposition arguments: a small fort arising from a twin pair, and a recurrence for non-forcing sets arising from a leaf. p. 7
Theorem 2 and Corollary 4
Theorem 2 shows that the only genuinely new obstruction beyond the distance-hereditary case occurs when all non-prime bags are attached directly to the prime bag. Corollary 4 therefore reduces the path-extremal conjecture on C≤m to a finite verification problem on bounded-order split-prime bases. p. 0
Lemma 13 and Theorem 2 Proof
Lemma 13 shows that if Q is a graph such that every induced subgraph of Q is pathextremal, then G obtained from Q by attaching pendant vertices to vertices of Q is path-extremal. Theorem 2 proves that if every induced subgraph of H is path-extremal, then every graph in C(H) is path-extremal. p. 2 This completes the induction. p. 2
Lemma 9 and Corollary 3
Lemma 9 provides local consequences of the accessibility relation, such as if B is a leaf-attached star bag with at least two ordinary leaves, then G contains a twin pair. Corollary 3 states that if B has at least two ordinary leaves, then G contains a twin pair. p. 8
Lemma 14 and Theorem 2 Proof
Lemma 14 provides the technical machinery for reducing graphs in D(H) by showing that removing specific structures preserves membership in D(H). The full proof of Theorem 2 is given in Appendix A. p. 9 p. 9 p. 9 p. 9
Lemma 12 and Q Isomorphism
Lemma 12 demonstrates that for a star-centered configuration, the graph G is obtained from Q by attaching the pendant vertices x1,..., xt to the vertices c1,. p. 0.., ct, respectively. p. 2 This structure allows for an isomorphism between Q and the label graph of P. p. 1
Lemma 8 and Theorem 1 Proof
Lemma 8 shows that every distance-hereditary graph with at least two vertices contains either a leaf or a twin pair. The proof of Theorem 1 proceeds by induction, using Lemma 4 to show that if G contains a leaf x, then z′(G; k) ≥ z′(Pn; k) for all 1 ≤ k ≤ n. p. 7 The case for twin pairs follows immediately from Corollary 1. p. 7
Lemma 3 and Lemma 4 Application
The proof of Theorem 1 applies Lemma 4 to obtain z′(G; k) ≥ z′(G − x; k)+z′(G−v; k − 1) for every 1 ≤ k ≤ n. This yields the final inequality z′(G; k) ≥ z′(Pn; k) by Pascal’s identity. p. 7
Lemma 6 and Fort Obstruction
Lemma 6 establishes a basic fort obstruction: if S avoids a fort F, then S is not a zero forcing set of G. Lemma 7 shows that twin pairs form forts. p. 1 Corollary 1 uses these to prove path-extremality if G contains a twin pair. p. 6
Lemma 2 and Reducedness Constraints
Lemma 2 outlines reducedness constraints on internal edges, stating that no internal tree edge of T joins two clique bags, and no internal tree edge of T joins a star bag through a leaf-marker to a star bag through a center-marker.
Lemma 10 and Lemma 13
Lemma 10 shows that if T is not a star centered at P, there exists a non-prime leaf bag B whose unique neighbor bag is also non-prime. Lemma 13 then shows that removing such a structure preserves membership in D(H). p. 8 The proof of Lemma 12 demonstrates the isomorphism Q to the label graph of P. p. 7 The full proof of Theorem 2 is given in Appendix A.
Lemma 9 and Corollary 3 Proof
The proof of Lemma 9 for a leaf-attached star bag with exactly one ordinary leaf x and center c confirms that G contains a twin pair. This is used in the proof of Corollary 3. p. 6 p. 6
Lemma 11 Proof Sketch
The proof sketch for Lemma 11 shows that deleting x preserves membership in D(H). The proof sketch for Lemma 9 confirms that G contains a twin pair. p. 7 The full proof of Theorem 2 is given in Appendix A.
The proof of Lemma 12 demonstrates that Q is isomorphic to the label graph of P. This isomorphism is crucial for proving the final step of Theorem 2. p. 0
Lemma 13 Application
The induction in the proof of Theorem 2 relies on Lemma 4 to show that z′(G; k) ≥ z′(Pn; k) for every k ≥ 1. The case k = 0 is trivial. p. 7 p. 7 Lemma 4 is used to obtain the final inequality z′(G; k) ≥ z′(Pn; k) by Pascal’s identity. p. 7
Lemma 12 and Twin Pair Condition
In Case 2 of Theorem 2, Lemma 12 states that either G contains a twin pair, in which case G is path-extremal by Corollary 1.
Lemma 9 and Center-Attached Star Bag
Lemma 9 shows that if B is a center-attached star bag, then G contains a twin pair. This is used in the proof of Lemma 12. p. 6 p. 6
Lemma 9 and Leaf-Attached Star Bag
Corollary 3 confirms that if B is a leaf-attached star bag with at least two ordinary leaves, then G contains a twin pair. This is used in the proof of Lemma 12.
Lemma 4 and Pascal's Identity
The final step of the induction relies on applying Lemma 4 to obtain z′(G; k) ≥ z′(Pn; k) by Pascal’s identity. The case k = 0 is trivial.
Lemma 13 and Path-Extremality Preservation
Lemma 13 shows that if Q has every induced subgraph path-extremal, then G obtained from Q by attaching pendant vertices to vertices of Q is path-extremal. This is the key step in proving Theorem 2. p. 0
The proof of Lemma 9 for a leaf-attached star bag with exactly one ordinary leaf x and center c confirms that G contains a twin pair. This is used in the proof of Corollary 3.
Lemma 14 Proof
The proof of Lemma 14 demonstrates that deleting x preserves membership in D(H). The full proof of Theorem 2 is given in Appendix A.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Improved zero forcing set counting for distance-hereditary graphs by leveraging twin pairs and leaf recurrence to establish a new positive instance of the path-extremal conjecture, extending known results from trees to this larger class.
-
Improved structural analysis of non-forcing sets in graphs with unique prime bags by reducing the problem to a finite verification problem on bounded-order prime cores, allowing for algorithmic tractability.
-
Developed a hybrid strategy for future research combining structural induction on split decomposition with finite verification of bounded prime bases, providing a concrete path for solving the conjecture on classes defined by Corollary 4.
Related papers
- Low-Temperature Sampling via Equilibrium Disagreements
- An Improved Bound for Testing k-Colorability
- Temporal Cliques Admit Linear Spanners
- Multiway Partition is FPT for Connectivity Functions
- Profile and neighbourhood complexity of graphs excluding a minor and tree-structured graphs
- Constrained intersection representations and forbidden patterns