Resolving Inconsistencies in Simple Temporal Problems: A Parameterized Approach
Authors: Konrad K. Dabrowski, Peter Jonsson, Sebastian Ordyniak, George Osipov3724-3732
AAAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We prove that the problem of identifying a maximally large consistent subset of data is NP-hard. In practical instances, it is reasonable to assume that the amount of erroneous data is small. We therefore parameterize by the number of constraints that need to be removed to achieve consistency. Using tools from parameterized complexity we design fixed-parameter tractable algorithms for two large fragments of the STP. Our main algorithmic results employ reductions to the Directed Subset Feedback Arc Set problem and iterative compression combined with an efficient algorithm for the Edge Multicut problem. We complement our algorithmic results with hardness results that rule out fixed-parameter tractable algorithms for all remaining non-trivial fragments of the STP (under standard complexity-theoretic assumptions). |
| Researcher Affiliation | Academia | 1Newcastle University, UK 2Link oping University, Sweden 3University of Leeds, UK |
| Pseudocode | Yes | Algorithm 1: Solving ALMOSTCSP(S=). |
| Open Source Code | No | The paper does not provide concrete access to source code for the methodology described. |
| Open Datasets | No | The paper is theoretical and does not use datasets for training or evaluation. |
| Dataset Splits | No | The paper is theoretical and does not describe dataset splits for validation. |
| Hardware Specification | No | The paper is theoretical and does not report on experimental hardware specifications. |
| Software Dependencies | No | The paper describes theoretical algorithms and does not list specific software dependencies with version numbers for experimental replication. |
| Experiment Setup | No | The paper is theoretical and does not detail an experimental setup or hyperparameters. |