arxiv: 2605.03622 · v1 · submitted 2026-05-05 · 💻 cs.DS · cs.CC· cs.LG

Recognition: unknown

Exact and Approximate Algorithms for Polytree Learning

Frank Sommer, Juha Harviainen, Manuel Sorge

Pith reviewed 2026-05-07 14:08 UTC · model grok-4.3

classification 💻 cs.DS cs.CCcs.LG

keywords polytree learningBayesian networksexact algorithmsapproximation algorithmsNP-hardnessin-degree bounds

0 comments

The pith

An algorithm finds the optimal polytree in O((2+ε)^n) time for any small ε when the maximum in-degree is a fixed constant, improving on the prior O(3^n) bound.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper focuses on learning polytrees, which are directed acyclic graphs representing conditional dependencies among n variables as a forest, a task that is NP-hard in general. It establishes that fixing the maximum in-degree k to a constant allows an exact algorithm running in time O((2+ε)^n) for arbitrarily small ε, which is faster than previous methods. It also supplies polynomial-time approximation algorithms that return a polytree whose score is at most k times the optimal for general scores or twice the optimal for additive scores. These upper bounds are paired with nearly tight lower bounds on time complexity and approximation ratios.

Core claim

We devise an algorithm that finds the optimal polytree in time O((2+ε)^n) for arbitrarily small ε > 0 and any constant in-degree bound k, improving over the fastest previously known algorithm of time complexity O(3^n). We further give polynomial-time algorithms for finding a polytree whose score is within a factor of k from the optimal one for arbitrary scores and a factor of 2 for additive ones. Many of the results are complemented by (nearly) tight lower bounds for either the time complexity or the approximation factors.

What carries the argument

An exponential-time enumeration procedure refined by the constant in-degree bound k that reduces the search space over possible directed forests while scoring each candidate polytree.

If this is right

Exact optimal polytrees become searchable in time only slightly above 2^n rather than 3^n when in-degree is bounded by a constant.
Polynomial-time algorithms exist that return a polytree scoring within factor k of optimal for any score function.
For additive score functions the approximation guarantee improves to a factor of 2 while remaining polynomial-time.
Nearly matching lower bounds show that the stated time and approximation ratios cannot be improved substantially without new techniques.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

These bounds suggest that bounded-degree polytree learning could become feasible for moderate numbers of variables in settings where exact optimality matters.
The separation between general and additive scores points to a potential avenue for better approximations when the score function has additive structure.
The results may extend to other restricted Bayesian network classes if similar degree or structural bounds can be imposed.
Without the constant in-degree assumption the problem stays NP-hard, so degree bounds appear essential for sub-3^n exact algorithms.

Load-bearing premise

The maximum in-degree k must be a fixed constant that does not grow with the number of variables n.

What would settle it

A concrete family of polytree-learning instances with fixed constant k where every exact algorithm requires Ω(3^n) time or where no polynomial-time algorithm can guarantee an approximation factor better than k for arbitrary scores.

Figures

Figures reproduced from arXiv: 2605.03622 by Frank Sommer, Juha Harviainen, Manuel Sorge.

**Figure 1.** Figure 1: A schematic visualization of the reduction provided in Theorem 3.5. Assume that 1/ϵ = 2. Then the choice node s2 gets a parent set of S 1/ϵ = S 2 which consists of the connecting node p and the two sets {u1, u2} (in red) and {u3, un′} (in blue) of the k ′ -SET PARTITIONING instance and this gives score 2. The k ′ -SET PARTITIONING problem similarly asks if one can find t disjoint subsets whose union is the… view at source ↗

**Figure 2.** Figure 2: An example for a bad local optima where k = 5. The polytree T consisting of the black arcs with score 10 is found by the greedy algorithm which always adds the parent set with largest score while preserving acyclicity. The polytree T ⋆ consisting of the red arcs has a score of 54 and non of the arcs of T ⋆ can be added to T. 9 9 10 view at source ↗

**Figure 3.** Figure 3: An example for a bad local optima where k = 1. The polytree T consisting of the black arc with score 10 is found by the greedy algorithm which always adds the edge with largest score while preserving acyclicity and maximum in-degree 1. The polytree T ⋆ consisting of the red arcs has a score of 18 and non of the arcs of T ⋆ can be added to T. Proof. We proceed almost analogously to Theorem 4.1, but instead … view at source ↗

**Figure 4.** Figure 4: An example for a bad local optima for the where q = 3. The polytree T consisting of the black arcs with score 10 is found by the greedy algorithm behind Theorem 4.1 which always adds the edge with largest score while preserving acyclicity and maximum component size 3. The polytree T ⋆ consisting of the red arcs has a score of 108 and non of the arcs of T ⋆ can be added to T. connected component of the poly… view at source ↗

**Figure 5.** Figure 5: An example for a bad local optima where k = 2. The polytree T consisting of the black arcs with score 10 is found by the greedy algorithm which always adds the parent set Dv which maximizes fv(Dv)/|Dv| while preserving acyclicity and the size k restriction for each component. The red numbers represent the number fv(Dv)/|Dv|. The polytree T ⋆ consisting of the red arcs has a score of 36 and non of the two … view at source ↗

**Figure 6.** Figure 6: Visualization of the reduction of Theorem 5.3. An MAXIMUM INDEPENDENT SET instance is shown in a) where a n independent set of size 3 is shown in red. Moreover, b) shows the constructed PT instance where only the nodes corresponding to the independent set have a non-empty parent set. For an example where the approximation factor of 2k occurs, we refer to view at source ↗

read the original abstract

Polytrees are a subclass of Bayesian networks that seek to capture the conditional dependencies between a set of $n$ variables as a directed forest and are motivated by their more efficient inference and improved interpretability. Since the problem of learning the best polytree is NP-hard, we study which restrictions make it more tractable by considering for example in-degree bounds, properties of score functions measuring the quality of a polytree, and approximation algorithms. We devise an algorithm that finds the optimal polytree in time $O((2+\epsilon)^n)$ for arbitrarily small $\epsilon > 0$ and any constant in-degree bound $k$, improving over the fastest previously known algorithm of time complexity $O(3^n)$. We further give polynomial-time algorithms for finding a polytree whose score is within a factor of $k$ from the optimal one for arbitrary scores and a factor of $2$ for additive ones. Many of the results are complemented by (nearly) tight lower bounds for either the time complexity or the approximation factors.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Faster exact algorithm for constant in-degree polytree learning to O((2+ε)^n) plus k- and 2-approximations with nearly tight lower bounds.

read the letter

The main thing to know is that the authors improve the exact algorithm for optimal polytree learning with constant in-degree to O((2+ε)^n) time and provide polynomial-time approximation algorithms with factors k and 2, backed by nearly tight lower bounds. This is new because the previous best exact time was O(3^n), and the approximations with explicit factors and matching lower bounds go beyond what was available. The paper does well by handling both exact and approximate cases in one framework, using the in-degree bound to get the speedups and guarantees. The separation into arbitrary scores for the k-approx and additive for the 2-approx shows careful attention to different score types common in the literature. The soft spots are minor. Everything depends on k being a fixed constant, which is stated upfront but does narrow the scope since real data might have higher degrees. Without full access to the proofs, it's hard to verify the DP details or if there are hidden assumptions on score decomposability, but the abstract presents the results without obvious gaps. The lower bounds are a strength here, as they make the claims more robust. This paper is for people working on structure learning algorithms for probabilistic graphical models, especially those focused on tractable subclasses like polytrees. Readers interested in exponential-time algorithms or approximation schemes for NP-hard graph problems will get value from the concrete bounds. It has clear algorithmic contributions and complexity analysis, so it deserves a serious referee. I recommend putting it through peer review.

Referee Report

0 major / 0 minor

Summary. The manuscript presents exact and approximate algorithms for learning optimal polytrees (a subclass of Bayesian networks) under bounded in-degree. It claims an O((2+ε)^n)-time exact algorithm for any fixed constant in-degree bound k (improving on the prior O(3^n) bound), polynomial-time approximation algorithms achieving a factor-k guarantee for arbitrary scores and a factor-2 guarantee for additive scores, and nearly tight lower bounds on time complexity and approximation factors.

Significance. If the results hold, the work advances the algorithmic foundations of Bayesian network structure learning by improving exact solvability for polytrees under natural restrictions and supplying practical approximation guarantees that distinguish arbitrary versus additive scores. The matching lower bounds add value by clarifying optimality.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of our work and for recommending acceptance. The report contains no major comments requiring a point-by-point response.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper presents new algorithmic constructions for exact and approximate polytree learning under constant in-degree bounds, along with matching lower bounds. These rely on standard dynamic programming over subsets, graph-theoretic reductions, and NP-hardness arguments that are independent of the target results. No self-definitional equations, fitted parameters renamed as predictions, or load-bearing self-citations appear in the derivation chain; the O((2+ε)^n) bound and approximation factors are derived from explicit algorithmic designs rather than by construction from prior outputs or assumptions internal to the paper.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on standard assumptions from computational complexity and graph algorithms. No free parameters or new postulated entities are introduced; all contributions are algorithmic improvements under the bounded in-degree restriction.

axioms (2)

domain assumption Learning the optimal polytree is NP-hard
Invoked to justify studying restricted cases such as bounded in-degree.
standard math Polytrees admit efficient dynamic-programming or search techniques when in-degree is bounded
Underlying the design of both the exact and approximation algorithms.

pith-pipeline@v0.9.0 · 5479 in / 1395 out tokens · 99091 ms · 2026-05-07T14:08:39.187601+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Reference graph

Works this paper leans on

23 extracted references · 1 canonical work pages

[1]

Inapproximability of vertex cover and independent set in bounded degree graphs

Austrin, P., Khot, S., and Safra, M. Inapproximability of vertex cover and independent set in bounded degree graphs. In Proceedings of the 24th Annual IEEE Conference on Computational Complexity (CCC 2009), pp.\ 74--80, 2009

2009
[2]

Chickering, D. M. Learning B ayesian networks is NP -complete. In Learning from Data: Artificial Intelligence and Statistics V (AISTATS 1995), pp.\ 121--130. Springer, 1995

1995
[3]

Cooper, G. F. and Herskovits, E. A B ayesian method for the induction of probabilistic networks from data. Mach. Learn., 9: 0 309--347, 1992

1992
[4]

On problems as hard as CNF-SAT

Cygan, M., Dell, H., Lokshtanov, D., Marx, D., Nederlof, J., Okamoto, Y., Paturi, R., Saurabh, S., and Wahlstr \" o m, M. On problems as hard as CNF-SAT . ACM Trans. Algorithms , 12 0 (3): 0 41:1--41:24, 2016

2016
[5]

Learning polytrees

Dasgupta, S. Learning polytrees. In Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence ( UAI 1999) , pp.\ 134--141. Morgan Kaufmann, 1999

1999
[6]

Optimum branchings

Edmonds, J. Optimum branchings. J. Res. Natl. Bur. Stand. B, 71 0 (4): 0 233--240, 1967

1967
[7]

A., and Frangi, A

Fehri, H., Gooya, A., Lu, Y., Meijering, E., Johnston, S. A., and Frangi, A. F. Bayesian polytrees with learned deep features for multi-class cell segmentation. IEEE Trans. Image Process. , 28 0 (7): 0 3246--3260, 2019

2019
[8]

Parameterized complexity in machine learning

Ganian, R. Parameterized complexity in machine learning. Comput. Sci. Rev., 59: 0 100836, 2026

2026
[9]

and Korchemna, V

Ganian, R. and Korchemna, V. The complexity of B ayesian N etwork L earning: R evisiting the superstructure. In Proceedings of the 35th Annual Conference on Neural Information Processing Systems ( NeurIPS 2021) , pp.\ 430--442, 2021

2021
[10]

and Korchemna, V

Ganian, R. and Korchemna, V. The complexity of B ayesian N etwork L earning: R evisiting the superstructure. CoRR, abs/2602.10253, 2026

work page arXiv 2026
[11]

On finding optimal polytrees

Gaspers, S., Koivisto, M., Liedloff, M., Ordyniak, S., and Szeider, S. On finding optimal polytrees. Theor. Comput. Sci., 592: 0 49--58, 2015

2015
[12]

and Komusiewicz, C

Gr \" u ttemeier, N. and Komusiewicz, C. Learning B ayesian networks under sparsity constraints: A parameterized complexity analysis. J. Artif. Intell. Res., 74: 0 1225--1267, 2022

2022
[13]

On the parameterized complexity of polytree learning

Gr \" u ttemeier, N., Komusiewicz, C., and Morawietz, N. On the parameterized complexity of polytree learning. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence ( IJCAI 2021) , pp.\ 4221--4227. ijcai.org, 2021 a

2021
[14]

Efficient B ayesian network structure learning via parameterized local search on topological orderings

Gr \" u ttemeier, N., Komusiewicz, C., and Morawietz, N. Efficient B ayesian network structure learning via parameterized local search on topological orderings. In Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence ( AAAI 2021) , pp.\ 12328--12335. AAAI Press, 2021 b

2021
[15]

Clique is hard to approximate within n^ 1-

H stad, J. Clique is hard to approximate within n^ 1- . In Proceedings of the 37th Annual Symposium on Foundations of Computer Science ( FOCS 1996) , pp.\ 627--636. IEEE Computer Society, 1996

1996
[16]

On the power of unique 2-prover 1-round games

Khot, S. On the power of unique 2-prover 1-round games. In Proceedings of the 17th Annual IEEE Conference on Computational Complexity (CCC 2002) , pp.\ 25. IEEE Computer Society, 2002

2002
[17]

Time--approximation trade-offs for learning B ayesian networks

Kundu, M., Parviainen, P., and Saurabh, S. Time--approximation trade-offs for learning B ayesian networks. In Proceedings of The 12th International Conference on Probabilistic Graphical Models (PGM 2024), volume 246 of Proceedings of Machine Learning Research, pp.\ 486--497. PMLR, 2024 a

2024
[18]

Discovering B ayesian networks when few variables matter

Kundu, M., Parviainen, P., and Saurabh, S. Discovering B ayesian networks when few variables matter. In Proceedings of the 27th European Conference on Artificial Intelligence ( ECAI 2024) , volume 392 of Frontiers in Artificial Intelligence and Applications, pp.\ 3047--3054. IOS Press, 2024 b

2024
[19]

and Szeider, S

Ordyniak, S. and Szeider, S. Parameterized complexity results for exact B ayesian network structure learning. J. Artif. Intell. Res., 46: 0 263--302, 2013

2013
[20]

Probabilistic reasoning in intelligent systems - networks of plausible inference

Pearl, J. Probabilistic reasoning in intelligent systems - networks of plausible inference. Morgan K aufmann series in representation and reasoning. Morgan Kaufmann, 1989

1989
[21]

On the hardness of approximate reasoning

Roth, D. On the hardness of approximate reasoning. Artif. Intell., 82 0 (1-2): 0 273--302, 1996

1996
[22]

P., and Zaffalon, M

Scanagatta, M., Corani, G., de Campos, C. P., and Zaffalon, M. Learning treewidth-bounded bayesian networks with thousands of variables. In Advances in Neural Information Processing Systems 29 (NeurIPS 2016), pp.\ 1462--1470, 2016

2016
[23]

Approximation algorithms for restricted B ayesian network structures

Ziegler, V. Approximation algorithms for restricted B ayesian network structures. Inf. Process. Lett., 108 0 (2): 0 60--63, 2008

2008