Complexity and Algorithms for Reasoning About Time: A Graph-Theoretic Approach

Abstract

Temporal events are regarded here as intervals on a time line, This paper deals with problems m reasoning about such intervals when the prccisc topological relationship between them is unknown or only partially specified, This work unifies notions of interval algebras in artificial intelligence with those of interval orders and mterwd gr~phs m combmatorlcs. The satqfahihty, znuumal Iabeltng, all solutLons. and all rcakatlons problems we considered for temporal (internal ) datti. Several versions are investigated by restricting the possible interval relationships yielding different complexity results, We show that even when the temporal data comprises of subsets of relatlons based on mtersectlon and precedence only, the satisfiabdlty question IS NP-complete. On the positive side, we give efficient algorithms for several restrictions of the problem. In the process, the irzterLa/,qrap/z satzdwzc/z problem is introduced, and is shown to be NP-complete This problem IS also important in molecular hlology, where it arlscs In physical mapping of DNA material. © 1993, ACM. All rights reserved.