KR2026Proceedings of the 23rd International Conference on Principles of Knowledge Representation and ReasoningProceedings of the 23rd International Conference on Principles of Knowledge Representation and Reasoning

Lisbon, Portugal. July 20-23, 2026.

Edited by
  1. Renata Wassermann
  2. Marie-Laure Mugnier
  3. Franz Baader

ISSN: 2334-1033
ISBN: 978-1-956792-18-8

Sponsored by
Published by

Copyright © 2026 International Joint Conferences on Artificial Intelligence Organization

Resolving Inconsistencies in Disjunctive Temporal Constraints: a Parameterized Complexity Classification

  1. Konrad K. Dabrowski(Newcastle University)
  2. Peter Jonsson(Linköping University)
  3. Sebastian Ordyniak(University of Leeds)
  4. George Osipov(Linköping University, Royal Holloway, University of London)
  5. Jorke M. de Vlas(Linköping University)
PDF
BibTeX
https://doi.org/10.24963/kr.2026/24

Keywords

  1. null-constraint satisfaction problem
  2. null-MinCSP
  3. null-temporal constraints

Abstract

The simple temporal problem (STP) and its generalization allowing disjunctive constraints (DTP) are some of the most influential reasoning formalisms for temporal information in AI. We study the problem of resolving inconsistency of data encoded in the DTP, i.e. given a DTP instance, find the minimum number of constraints to remove to make it satisfiable. While this problem is NP-hard in general, it is reasonable to assume that the amount of erroneous data will be small in practical instances. We therefore study the parameterized complexity of this problem parameterized by the number of constraints to be removed to achieve satisfiability, and obtain full P/NP-hard and FPT/W[1]-hard dichotomies for all binary DTP languages.