Exact and Approximate Algorithms for Polytree Learning

Juha Harviainen, Frank Sommer, Manuel Sorge · 2026

Read Exact and Approximate Algorithms for Polytree Learning by Juha Harviainen, Frank Sommer, Manuel Sorge (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-03622.txt.

Introduction

Juha Harviainen, Frank Sommer, and Manuel Sorge study how to learn polytrees, a simple class of Bayesian networks where the dependency graph forms a directed forest. Polytrees allow efficient inference and are easy to interpret, but finding the best one is NP-hard. The authors ask which restrictions make the problem tractable.

They give an algorithm that finds the optimal polytree faster than the best previously known method, for any constant bound on in-degree. They also give polynomial-time approximation algorithms whose scores stay within a proven factor of optimal, with a tighter factor for additive scores. Nearly tight lower bounds accompany many of the results, showing where the limits of improvement lie.

Catalog record

CREATORJuha Harviainen, Frank Sommer, Manuel Sorge
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE46 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.03622

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Exact and Approximate Algorithms for Polytree Learning Juha Harviainen, Frank Sommer, Manuel Sorge Abstract Polytrees are a subclass of Bayesian networks that seek to capture the conditional dependencies between a set of n 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 𝒪 ⁡ ( ( 2 + ϵ ) n ) \mathcal{O}\big((2+\epsilon)^{n}\big) for arbitrarily small ϵ > 0 \epsilon>0 and any constant in-degree bound k k , improving over the fastest previously known algorithm of time complexity 𝒪 ⁡ ( 3 n ) \mathcal{O}\big(3^{n}\big) . We further give polynomial-time algorithms for finding a polytree whose score is within a factor of k k from the optimal one for arbitrary scores and a factor of 2 2 for additive ones. Many of the results are complemented by (nearly) tight lower bounds for either the time complexity or the approximation factors. † † affiliationnotice: Equal contribution 1 Introduction Bayesian networks (BNs) are probabilistic graphical models that represent the set of variables and their conditional independencies as a directed acyclic graph (DAG). Widely adopted score-based approaches for learning an optimal structure for the network from data make simplifying assumptions that decompose the posterior probabilities of structures into a product of node-wise local scores that depend only on the node and its set of parents in the DAG. Even with these assumptions, however, structure learning remains NP-hard ( Chickering 1995 ) . Further, performing inference is \# P-hard ( Roth 1996 ) in general. Hence, in practice often heuristics are used. One prominent heuristic is K2 ( Cooper & Herskovits 1992 ) : we are given a node ordering, and for each node in that ordering the highest scoring parent set is added while acyclicity is preserved. These obstacles have motivated studies of constrained classes of BNs that provide a trade-off between the expressiveness and the efficiency of computation. Polytrees are BNs whose underlying undirected graph is a forest that are more interpretable and inference takes only polynomial time ( Pearl 1989 ) . In terms of applications, polytrees are used in image-segmentation for microscopy data ( Fehri et al. 2019 ) . However, structure learning remains NP-hard for them even when the nodes can have only 2 parents ( Dasgupta 1999 ) , with the fastest known algorithms taking exponential time in the number of nodes ( Grüttemeier et al. 2021a ) except for the special case of branchings where each node is allowed a single parent ( Edmonds 1967 ) . We discover a novel dynamic-programming algorithm for learning the optimal polytree with dynamic programming in time 3^{n}n^{\mathcal{O}(1)} under mild assumptions, matching the time complexity of Grüttemeier et al. 2021a . However, under any constant in-degree bound, we show that the running time can be improved to \mathcal{O}\big((2+\epsilon)^{n}\big) for arbitrarily small \epsilon>0 by characterizing a subset of dynamic programming states that are sufficient for identifying the optimal structure. We further prove the time complexity to be near-optimal under the set cover conjecture (SCC) of Cygan et al. 2016 . Because of the inherent hardness of learning the structure of an optimal polytree, the rest of the paper focuses in studying the hardness of approximating it, inspired by recent works on approximation algorithms for general BNs ( Kundu et al. 2024a ; Ziegler 2008 ) . More precisely, Kundu et al. 2024a provide so-called FPT-approximations for learning BNs, and Ziegler 2008 studies learning BNs with a maximal parent set size k . Interestingly, the algorithm of Ziegler 2008 is a variant of the K2 heuristic: there in each step the highest scoring parent set without violating acyclicity is added (hence no node ordering is used). We show that without any further assumptions about problem instances, no non-trivial polynomial-time approximation guarantee for polytree learning is possible unless P = NP. However, if the in-degree of the polytree is again bounded by a constant k , then we can get a (k+1) -approximation of the optimal structure, which we also prove to be optimal up to logarithmic factors in k under the Unique Games Conjecture (UG) of Khot 2002 . This is somewhat surprising since, as mention above, learning BNs with in-degree bound also admits a factor k approximation ( Ziegler 2008 ) . One could have hoped that the much simpler structure of polytrees allows for a better approximation guarantee. We show, however, that this is not possible. Interestingly, our algorithm is very similar to the one of ( Ziegler 2008 ) : in each step we add the highest scoring parent set, but now we ensure that the underlying graph is acyclic while Ziegler 2008 ensured acyclicity of the directed graph. Another simplifying assumption motivated by heuristics for BNs ( Ganian & Korchemna 2021 ; Scanagatta et al. 2016 ) that we study are additive local scores for which each possible arc has a score and the score of a DAG is the sum of the arc-wise scores. Recently Ganian & Korchemna 2026 showed that Polytree Learning with additive scores can be done in polynomial time. Nonetheless we achieve a 2 -approximation of the optimal polytree in that case with the same simple greedy algorithm which always adds the best remaining parent set without violating the polytree constraint. We believe that this result is interesting despite the fact that an optimal solution can be computed in polynomial time since this shows that this simple greedy algorithm can achieve much better approximation guarantees than k if we impose additional constraints on the polytree. In other words, we believe there are scoring functions which are more general than being additive such that this simple greedy algorithm (or a slight adaption of it) yields a constant factor approximation. Finally, we provide a 2q -approximation for the variant PT {}_{\textup{comp}} in which each component is only allowed to have at most q arcs. For a summary of our algorithms and lower bounds, see Table 1 . Table 1 : Summary of our algorithms for running time and approximation factors for polytree learning (PT). The subscript ‘ \leq ’ means that we have an in-degree bound k , the superscript ‘ + ’ means additive local scores, and ‘ comp ’ means component size bounded by q . Problem Time Approximation factor Theorem Comments PT 3^{n}|\mathcal{I}|^{\mathcal{O}(1)} Exact Theorem 3.1 Same complexity as Grüttemeier et al. 2021a PT ≤ (2+\epsilon)^{n}|\mathcal{I}|^{\mathcal{O}(1)} Exact Theorem 3.3 Any \epsilon>0 , near-optimal complexity under SCC PT ≤ |\mathcal{I}|^{\mathcal{O}(1)} k+1 Theorem 4.1 Optimal up to logarithmic factors in k under UG PT {}_{\leq}^{+} |\mathcal{I}|^{\mathcal{O}(1)} 2 Theorem 4.2 Proven to be in P ( Ganian & Korchemna 2026 ) PT {}_{\textup{comp}} |\mathcal{I}|^{\mathcal{O}(1)} 2q Theorem 4.3 Optimal up to logarithmic factors in q under UG Related work. A closely related optimization problem of minimizing the sum of conditional entropies over the nodes was studied by Dasgupta 1999 . Their approximability results, however, do not generalize to the score-based structure learning

Read the complete text