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; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1]
Disentangling the Computational Complexity of Network Untangling
Authors: Vincent Froese, Pascal Kunz, Philipp Zschoche
IJCAI 2022 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we initiate a multivariate complexity analysis involving the following parameters: number of vertices, lifetime of the temporal graph, number of intervals per vertex, and the interval length bound. For both problem versions, we (almost) completely settle the parameterized complexity for all combinations of those four parameters, thereby delineating the border of fixed-parameter tractability. |
| Researcher Affiliation | Academia | Vincent Froese , Pascal Kunz and Philipp Zschoche Technische Universit at Berlin, Faculty IV, Institute of Software Engineering and Theoretical Computer Science, Algorithmics and Computational Complexity EMAIL |
| Pseudocode | No | The paper describes algorithms in prose (e.g., in the proofs of Theorem 7 and Theorem 8), but it does not present them in a formally structured pseudocode block or an algorithm environment. |
| Open Source Code | No | The paper does not include any statement about releasing source code or provide links to a code repository for the methodology described. |
| Open Datasets | No | This is a theoretical paper focused on complexity analysis. It does not involve empirical studies with datasets or training. |
| Dataset Splits | No | This is a theoretical paper focused on complexity analysis. It does not involve empirical studies with datasets or validation splits. |
| Hardware Specification | No | This is a theoretical paper focused on complexity analysis. It does not describe any experiments that would require specific hardware specifications. |
| Software Dependencies | No | This is a theoretical paper focused on complexity analysis. It does not describe any experiments that would require specific software dependencies or their versions. |
| Experiment Setup | No | This is a theoretical paper focused on complexity analysis. It does not involve empirical experiments with a setup or hyperparameters. |