The Complexity of Temporal Vertex Cover in Small-Degree Graphs
Authors: Thekla Hamm, Nina Klobas, George B. Mertzios, Paul G. Spirakis10193-10201
AAAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our main result shows that for every ε 2, ε-TVC is NP-hard even when the underlying topology is described by a path or a cycle. This resolves an open problem from literature and shows a surprising contrast between ε-TVC and TVC for which we provide a polynomial-time algorithm in the same setting. To circumvent this hardness, we present a number of exact and approximation algorithms for temporal graphs whose underlying topologies are given by a path, that have bounded vertex degree in every time step, or that admit a small-sized temporal vertex cover. |
| Researcher Affiliation | Academia | 1 Algorithms and Complexity Group, TU Wien, Austria 2 Department of Computer Science, Durham University, UK 3 Department of Computer Science, University of Liverpool, UK 4 Computer Engineering & Informatics Department, University of Patras, Greece |
| Pseudocode | No | The paper describes algorithms conceptually and presents their theoretical properties, but it does not include any formal pseudocode blocks or clearly labeled algorithm figures. |
| Open Source Code | No | The paper does not provide any statements or links indicating that source code for the described methodology is publicly available. |
| Open Datasets | No | The paper is theoretical and focuses on complexity and algorithm design for temporal graphs. It does not involve empirical experiments, datasets, or the concept of training splits. |
| Dataset Splits | No | The paper is theoretical and focuses on complexity and algorithm design for temporal graphs. It does not involve empirical experiments, datasets, or the concept of validation splits. |
| Hardware Specification | No | The paper is theoretical and focuses on complexity and algorithm design. It does not describe any empirical experiments that would require specifying hardware used. |
| Software Dependencies | No | The paper is theoretical and focuses on complexity and algorithm design. It does not mention any specific software components or their version numbers that would be required to reproduce the work. |
| Experiment Setup | No | The paper is theoretical, presenting complexity results and algorithms. It does not describe any empirical experimental setup, hyperparameters, or training configurations. |