Disentangling the Computational Complexity of Network Untangling
Authors: Vincent Froese, Pascal Kunz, Philipp Zschoche
IJCAI 2022 | Conference PDF | Archive PDF | Plain Text | 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 {vincent.froese, p.kunz.1, zschoche}@tu-berlin.de |
| 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. |