Disjunctive Temporal Problems under Structural Restrictions
Authors: Konrad K Dabrowski, Peter Jonsson, Sebastian Ordyniak, George Osipov3724-3732
AAAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | The disjunctive temporal problem (DTP) is an expressive temporal formalism that extends Dechter et al. s simple temporal problem. The DTP is well studied in the literature and has many important applications. It is known that deciding satisfiability of DTPs is NP-hard and that, in many cases, single-exponential algorithms (running in O(cn) time) do not exist under the Exponential-Time Hypothesis. The computational hardness makes it worthwhile to identify restricted problems that are efficiently solvable. One way of doing this is to restrict the interactions of variables and constraints. We show that instances of DTP of any arity with integers bounded by poly(n) can be solved in nf(w) time, where n denotes the problem size, w is the treewidth of the incidence graph and f is a computable function; in other words, this problem is in the complexity class XP and it can be solved in polynomial time whenever w is fixed. We complement this result by showing that binary DTPs that only involve the integers 0 and 1 are not fixed-parameter tractable with respect to treewidth, i.e. they do not admit a f(w) poly(n) time algorithm for any computable function f, under standard complexity assumptions. For instances with unbounded integers, we show that even binary DTPs parameterized by treewidth cannot be in XP, unless P = NP. |
| Researcher Affiliation | Academia | Konrad K. Dabrowski,1 Peter Jonsson,2 Sebastian Ordyniak,3 George Osipov2 1Durham University 2Link oping University 3University of Leeds |
| Pseudocode | No | The paper describes the dynamic programming algorithm conceptually and through lemmas, but does not include formal pseudocode blocks or algorithms labeled as such. |
| Open Source Code | No | The paper does not provide any link to source code or explicitly state that source code for their methodology is available. |
| Open Datasets | No | This paper is theoretical and does not use or reference any datasets for training or evaluation. |
| Dataset Splits | No | This paper is theoretical and does not describe empirical experiments, thus there are no training/test/validation dataset splits mentioned. |
| Hardware Specification | No | This paper is theoretical and does not describe empirical experiments, thus no hardware specifications are mentioned. |
| Software Dependencies | No | This paper is theoretical and does not describe empirical experiments. Therefore, it does not list any specific software dependencies with version numbers needed for replication. |
| Experiment Setup | No | This paper is theoretical and does not describe empirical experiments, thus no experimental setup details, hyperparameters, or training configurations are provided. |