Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
On the Parameterized Complexity of Polytree Learning
Authors: Niels Grüttemeier, Christian Komusiewicz, Nils Morawietz
IJCAI 2021 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this work, we revisit the complexity of POLYTREE LEARNING. We show that POLYTREE LEARNING can be solved in single-exponential FPT time for the number of variables. Moreover, we consider the influence of d, the number of variables that might receive a nonempty parent set in the final DAG on the complexity of POLYTREE LEARNING. We show that POLYTREE LEARNING is presumably not fixed-parameter tractable for d, unlike Bayesian network learning which is fixed-parameter tractable for d. Finally, we show that if d and the maximum parent set size are bounded, then we can obtain efficient algorithms. |
| Researcher Affiliation | Academia | Niels Gr uttemeier , Christian Komusiewicz and Nils Morawietz Philipps-Universit at Marburg, Marburg, Germany EMAIL |
| Pseudocode | Yes | Algorithm 1 FPT-algorithm for parameter d + p 1: Input: (N, F, t) and dependent vertices v1, . . . , vd 2: b A0 := { } 3: for i = 1 . . . d do 4: e Ai = S P PF(vi)\{ } b Ai 1 vi P 5: b Ai := Compute Representation( e Ai, (d i) p) 6: return b A b Ad such that (N, b A) is a polytree and score( b A) is maximal |
| Open Source Code | No | The paper describes theoretical algorithms and complexity results, but does not provide any information about open-source code for the described methodologies. |
| Open Datasets | No | The paper describes theoretical algorithms and complexity results and does not report on experiments using datasets. |
| Dataset Splits | No | The paper describes theoretical algorithms and complexity results and does not report on experiments or dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not report on computational experiments that would require specific hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not report on computational experiments that would require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not report on computational experiments or their setup, including hyperparameters or system-level training settings. |