PaperlayerView exact revision on arXiv

Source-linked AI summary

The Complexity of Bayesian Network Learning: Revisiting the Superstructure

Robert Ganian, Viktoriia Korchemna

arXiv:2602.10253v1cs.DScs.AI

TL;DR

The paper studies the parameterized complexity of BNSL under superstructure parameters and different score representations. It proves tractability for feedback-edge parameters and, with additive scores, for treewidth, while extending the analysis to Polytree Learning. These results complement hardness results and provide a broad complexity classification.

  • Problem

    BNSL is hard under several superstructure parameterizations, including treewidth and vertex cover, leaving open which structural restrictions yield fixed-parameter tractability.

  • Method

    The paper analyzes edge-deletion parameters, localized feedback-edge distance, treecut width, additive score representations, and corresponding Polytree Learning variants.

  • Results

    Feedback edge number and local feedback edge number yield FPT for BNSL; additive scores yield FPT under treewidth, while treecut width remains W[1]-hard and Polytree Learning becomes polynomial-time tractable with additive scores.

  • Takeaways & Limitations

    The results substantially refine the complexity map of BNSL and Polytree Learning across commonly studied superstructure parameters and input representations.

  • Takeaways & Limitations

    The work claims no immediate practical applications, though its polynomial-time reduction procedure might potentially be adapted to speed existing heuristics.

Abstract

from arXiv · show

We investigate the parameterized complexity of Bayesian Network Structure Learning (BNSL), a classical problem that has received significant attention in empirical but also purely theoretical studies. We follow up on previous works that have analyzed the complexity of BNSL w.r.t. the so-called superstructure of the input. While known results imply that BNSL is unlikely to be fixed-parameter tractable even when parameterized by the size of a vertex cover in the superstructure, here we show that a different kind of parameterization - notably by the size of a feedback edge set - yields fixed-parameter tractability. We proceed by showing that this result can be strengthened to a localized version of the feedback edge set, and provide corresponding lower bounds that complement previous results to provide a complexity classification of BNSL w.r.t. virtually all well-studied graph parameters. We then analyze how the complexity of BNSL depends on the representation of the input. In particular, while the bulk of past theoretical work on the topic assumed the use of the so-called non-zero representation, here we prove that if an additive representation can be used instead then BNSL becomes fixed-parameter tractable even under significantly milder restrictions to the superstructure, notably when parameterized by the treewidth alone. Last but not least, we show how our results can be extended to the closely related problem of Polytree Learning.

1 Introduction

BNSL asks whether a directed acyclic network over variables can achieve a target score, but remains hard under several classical and superstructure-based parameterizations. This paper identifies tractable parameterizations based on feedback-edge distance and additive score representations, and extends its results to Polytree Learning.

  • Problem setting: BNSL seeks a directed acyclic graph over variables whose total score reaches a specified target.The decision formulation is used for complexity analysis, while the algorithms can construct a witnessing network.
  • Problem setting: Parameterized complexity measures BNSL using input size and a numerical parameter, distinguishing FPT from W[1]-hardness.FPT algorithms run in f(k) · nO(1) time, whereas W[1]-hardness rules out FPT under standard assumptions.
  • Prior complexity landscape: BNSL remains W[1]-hard when parameterized by superstructure treewidth, despite treewidth yielding XP-tractability.Earlier work also established hardness for vertex-cover parameterization and motivated restrictions on the superstructure.
  • Contributions: Feedback edge number yields FPT algorithms for unrestricted BNSL and a polynomial-time kernel with a number of variables linear in that parameter.The parameter is the minimum number of edges whose deletion makes the superstructure acyclic.
  • Contributions: Localized feedback edge number also gives FPT, while treecut width remains W[1]-hard and localized parameterization lacks an analogous polynomial-time preprocessing procedure.The local parameter measures the maximum edge-deletion distance to acyclicity among cycles intersecting a particular vertex.
  • Contributions: Under additive score representation, BNSL is FPT parameterized by superstructure treewidth, with a parent bound q supported when included as an additional parameter.Without q as a parameter, the paper rules out fixed-parameter tractability; the results are also adapted to Polytree Learning.

2 Preliminaries

This section defines BNSL and PL, their score representations and superstructure, and the parameterized-complexity framework used to analyze them. It also introduces feedback-edge parameters and their relationships to treecut width.

  • Problem definitions: BNSL asks whether an acyclic digraph on the input vertices achieves score at least ℓ.The score sums each vertex's local score for its chosen parent set.
  • Problem definitions: PL is the analogous problem with the additional requirement that the solution digraph is a polytree.A polytree has a forest as its underlying undirected skeleton.
  • Input representations: The non-zero representation stores only local parent-set scores that differ from zero, inducing a superstructure edge whenever two variables occur in one another's candidate parent sets.This representation can still encode exponentially large score-function families.
  • Input representations: The additive representation decomposes each parent-set score into the sum of singleton-parent scores and therefore uses at most |V| entries per local score function.The associated superstructure is defined from variables with non-zero singleton scores.
  • Graph parameters: For disconnected superstructures, the maximum score can be computed independently on each connected component and then combined.Algorithmic results may therefore assume the superstructure is connected without loss of generality.
  • Parameterized complexity: Parameterized complexity studies running time as a function of input size n and parameter k; FPT algorithms run in time f(k) · n^O(1).The parameter is intended to confine the combinatorial explosion to a structural part of the instance.
  • Graph parameters: The feedback edge number is the minimum number of edges whose deletion makes a graph acyclic, while the local feedback edge number measures this distance around individual vertices.The paper also shows that lfen is bounded between treecut width and fen, and that lfen can be computed in FPT time with a spanning-tree witness.

3 Solving BNSL̸=0 with Parameters Based on Edge Cuts.

For BNSL̸=0, edge-cut parameters yield both kernelization and fixed-parameter algorithms, while related lower bounds delimit the approach. Feedback edge number supports a polynomial-size kernel, whereas local feedback edge number supports FPT via dynamic programming but not polynomial kernelization under standard assumptions.

  • Feedback edge number: Theorem 3 outputs an equivalent BNSL̸=0 instance with at most 16k vertices in O(|I|^2) time when the superstructure has feedback edge number k.The reduction rules safely remove leaves and replace sufficiently long degree-2 paths.
  • Feedback edge number: Kernelization immediately gives a BNSL̸=0 algorithm running in time n^O(1) + 2^O(k) for feedback edge number k.The reduced instance can be solved by exhaustive branching over possible DAGs.
  • Feedback edge number: The feedback-edge-number kernel marks at most 4k vertices and replaces each of at most 4k marked-vertex paths with three vertices.Together, these bounds yield 4k + 4k · 3 = 16k vertices.
  • Local feedback edge number: BNSL̸=0 is fixed-parameter tractable when parameterized by local feedback edge number, using dynamic programming rather than the feedback-edge-number kernelization approach.Given a suitable spanning tree, the algorithm runs in time 2^O(k^3)·n^3.
  • Local feedback edge number: Local feedback edge number covers a strictly larger class of tractable instances, but its locality prevents an equivalent polynomial-size kernel under standard complexity assumptions.The local parameter does not increase under disjoint unions, and no polynomial kernel exists unless NP ⊆ co-NP/poly.
  • Lower bounds: The lower-bound results show that BNSL̸=0 remains W[1]-hard under treecut width and vertex cover, even when vertices outside the vertex cover have degree at most 2.The local feedback edge number also does not admit a polynomial kernel under the stated assumption.

4 Additive Scores and Treewidth

The additive representation preserves NP-hardness in the classical setting but enables fixed-parameter algorithms for BNSL under treewidth-based parameterizations. A leaf-to-root dynamic program over a nice tree decomposition yields the main tractability result, while related variants retain parameterized hardness.

  • BNSL+ remains NP-hard, and its related bounded-parent variant is also shown NP-hard.
  • Theorem 13 establishes that BNSL+ is FPT when parameterized by the treewidth of the superstructure.
  • The bounded-parent variant is FPT when parameterized by q plus the superstructure treewidth, with runtime 2^O(k^2) · q^O(k).
  • The algorithm computes records in a leaf-to-root dynamic program, storing bag arcs, connectivity, partial scores, and parent-set sizes.
  • For BNSL+, disregarding parent-count entries and explicit in-degree bounds gives runtime 2^O(k^2) · n.
  • The resulting classification resolves the parameterized complexity of BNSL+ for all parameters depicted in Figure 1, while the bounded-parent variant remains unresolved for treewidth alone.
  • The bounded-parent variant is W[1]-hard when parameterized by the treewidth of the superstructure.

5 Implications for Polytree Learning

The paper adapts its BNSL tractability results to Polytree Learning, using redesigned reductions and dynamic programming while preserving polytree structure. It establishes fixed-parameter tractability for feedback-edge parameters and treewidth-based additive representations, while PL+ is polynomial-time tractable.

  • 5 Implications for Polytree Learning: Polytree Learning requires the learned network to be a polytree, and the paper adapts its BNSL results to this setting.Some adaptations require non-trivial modifications.
  • 5 Implications for Polytree Learning: An O(|I|^2) reduction produces an equivalent PL non-zero instance with at most 24k vertices when the superstructure has feedback edge number k.The reduction preserves the existence of solutions while replacing long paths with constant-size gadgets.
  • 5 Implications for Polytree Learning: The path reduction preserves whether endpoints are connected, using eight endpoint and connectivity configurations encoded by the replacement gadget.The parent sets and scores of the gadget vertex cover the possible configurations of the original path.
  • 5 Implications for Polytree Learning: PL is fixed-parameter tractable when parameterized by the local feedback edge number of the superstructure.The algorithm uses dynamic programming on a spanning tree and stores boundary connectivity and incoming-arc information.
  • 5 Implications for Polytree Learning: The treewidth-and-parent-set-size algorithm for additive BNSL extends to PL, while PL+ is polynomial-time tractable through a reduction to minimum edge-weighted spanning tree.The additive PL result can also be formulated using weighted matroid intersection, which is polynomial-time solvable.
  • 5 Implications for Polytree Learning: BNSL with additive representation remains fixed-parameter tractable by the number of dependent vertices, whereas PL with additive representation is polynomial-time tractable.The latter result includes the constant-parent-set-size setting described through matroid-based methods.

6 Concluding Remarks

The results broaden tractability for BNSL and Polytree Learning across superstructure parameters and input representations. Their immediate practical impact is limited, while the newly introduced local feedback edge number may have applications beyond BNSL.

  • 6 Concluding Remarks: Feedback edge number and its localized version yield fixed-parameter tractability and data reduction for BNSL and Polytree Learning despite vertex-cover lower bounds.Together with the treecut-width lower bound, these results complete the complexity map for BNSL across virtually all commonly considered superstructure parameters.
  • 6 Concluding Remarks: With additive rather than non-zero score representation, BNSL and Polytree Learning admit dynamic programming that is fixed-parameter tractable with respect to superstructure treewidth.The paper assumes that score functions are provided explicitly.
  • 6 Concluding Remarks: The paper claims no immediate practical applications, but suggests adapting and streamlining its polynomial-time data reduction for heuristics.The proposed direction includes combining the reduction with heuristic rules that lack a theoretical benefit but perform well empirically.
  • 6 Concluding Remarks: The local feedback edge number is introduced specifically for BNSL and may have applications beyond this problem.The paper notes that graph-theoretic works have not yet considered this parameter.
Loading 2602.10253v1…