Learning Bayesian Networks Under Sparsity Constraints: A Parameterized Complexity Analysis
Authors: Niels Grüttemeier, Christian Komusiewicz
IJCAI 2020 | Conference 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 structural constraints are posed on the network or on its moralized graph. More precisely, we consider the constraint that the moralized graph can be transformed to a graph from a sparse graph class Π by at most k vertex deletions. We show that for Π being the graphs with maximum degree 1, an optimal network can be computed in polynomial time when k is constant, extending previous work that gave an algorithm with such a running time for Π being the class of edgeless graphs [Korhonen & Parviainen, NIPS 2015]. We then show that further extensions or improvements are presumably impossible. |
| Researcher Affiliation | Academia | Niels Gr uttemeier and Christian Komusiewicz Fachbereich Mathematik und Informatik, Philipps-Universit at Marburg, Marburg, Germany {niegru, komusiewicz}@informatik.uni-marburg.de |
| Pseudocode | No | The paper describes algorithms in prose and mathematical notation (e.g., recurrences for dynamic programming) but does not include structured pseudocode or clearly labeled algorithm blocks. |
| Open Source Code | No | The paper does not provide any statement or link regarding the availability of open-source code for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not conduct experiments with specific datasets, therefore no concrete access information for a publicly available or open dataset is provided. |
| Dataset Splits | No | The paper is theoretical and does not describe experimental results, thus no specific dataset split information for training, validation, or testing is provided. |
| Hardware Specification | No | The paper is theoretical and does not describe empirical experiments, therefore no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not describe empirical experiments or provide implementation details, therefore no specific software dependencies with version numbers are mentioned. |
| Experiment Setup | No | The paper is theoretical and does not describe empirical experiments, therefore no specific experimental setup details like hyperparameters or training configurations are provided. |