Learning Bayesian Networks Under Sparsity Constraints: A Parameterized Complexity Analysis
Authors: Niels Grüttemeier, Christian Komusiewicz
JAIR 2022 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the problem of learning the structure of an optimal Bayesian network when additional constraints are posed on the network or on its moralized graph. More precisely, we consider the constraint that the network or its moralized graph are close, in terms of vertex or edge deletions, to a sparse graph class Π. For example, we show that learning an optimal network whose moralized graph has vertex deletion distance at most k from a graph with maximum degree 1 can be computed in polynomial time when k is constant. This extends previous work that gave an algorithm with such a running time for the vertex deletion distance to edgeless graphs. We then show that further extensions or improvements are presumably impossible. For example, we show that learning optimal networks where the network or its moralized graph have maximum degree 2 or connected components of size at most c, c 3, is NP-hard. Finally, we show that learning an optimal network with at most k edges in the moralized graph presumably has no f(k) |I|O(1)-time algorithm and that, in contrast, an optimal network with at most k arcs can be computed in 2O(k) |I|O(1) time where |I| is the total input size. In parameterized complexity (Cygan et al., 2015) one measures the running time of algorithms depending on the total input size and a problem parameter. A parameterized problem is a language L Σ N0 over a finite alphapet Σ. For an instance (I, k) of L we call k the parameter. A parameterized problem L has an XP-time algorithm if for every instance (I, k) it can be decided in O(|I|f(k)) time for a computable function f whether (I, k) L. That is, the problem is solvable in polynomial time when the parameter is constant. A parameterized problem L is called fixed-parameter tractable (FPT) if for every instance (I, k) it can be decided in f(k) |I|O(1) time for a computable function f whether (I, k) L. A problem kernelization for a parameterized problem L is a polynomial-time preprocessing. |
| Researcher Affiliation | Academia | Niels Gr uttemeier EMAIL Christian Komusiewicz EMAIL Hans-Meerwein-Straße 6 35032 Marburg, Germany |
| Pseudocode | No | The paper describes algorithms and dynamic programming recurrences in prose and mathematical notation but does not include clearly labeled pseudocode or algorithm blocks with structured code-like formatting. For example, Proposition 5 describes an 'Algorithm. To describe the algorithm, we introduce some notation.' and provides a recurrence relation, but not a formally structured pseudocode block. |
| Open Source Code | No | No explicit statement about the release of source code or a link to a code repository is provided in the paper. |
| Open Datasets | No | The paper primarily focuses on theoretical complexity analysis and does not describe experiments that would utilize specific datasets. |
| Dataset Splits | No | The paper is a theoretical work on parameterized complexity analysis and does not involve empirical experiments with datasets, therefore no dataset split information is provided. |
| Hardware Specification | No | The paper is a theoretical study of parameterized complexity and does not report on experimental results requiring specific hardware specifications. |
| Software Dependencies | No | The paper does not mention any specific software dependencies with version numbers used for implementing or running the described algorithms, as it is a theoretical work. |
| Experiment Setup | No | The paper is theoretical and focuses on complexity analysis; therefore, it does not describe any experimental setup details such as hyperparameters or training configurations. |