Document Open Access Logo

On Restricted Disjunctive Temporal Problems: Faster Algorithms and Tractability Frontier

Authors Carlo Comin , Romeo Rizzi

PDF
Thumbnail PDF

File

LIPIcs.TIME.2018.10.pdf
  • Filesize: 0.65 MB
  • 20 pages

Document Identifiers

Author Details

Carlo Comin
  • Department of Computer Science, University of Verona, Italy
Romeo Rizzi
  • Department of Computer Science, University of Verona, Italy

Cite AsGet BibTex

Carlo Comin and Romeo Rizzi. On Restricted Disjunctive Temporal Problems: Faster Algorithms and Tractability Frontier. In 25th International Symposium on Temporal Representation and Reasoning (TIME 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 120, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.TIME.2018.10

Abstract

In 2005 T.K.S. Kumar studied the Restricted Disjunctive Temporal Problem (RDTP), a restricted but very expressive class of Disjunctive Temporal Problems (DTPs). An RDTP comes with a finite set of temporal variables, and a finite set of temporal constraints each of which can be either one of the following three types: (t_1) two-variable linear-difference simple constraint; (t_2) single-variable disjunction of many interval constraints; (t_3) two-variable disjunction of two interval constraints only. Kumar showed that RDTPs are solvable in deterministic strongly polynomial time by reducing them to the Connected Row-Convex (CRC) constraints satisfaction problem, also devising a faster randomized algorithm. Instead, the most general form of DTPs allows for multi-variable disjunctions of many interval constraints and it is NP-complete. This work offers a deeper comprehension on the tractability of RDTPs, leading to an elementary deterministic strongly polynomial time algorithm for them, significantly improving the asymptotic running times of all the previous deterministic and randomized solutions. The result is obtained by reducing RDTPs to the Single-Source Shortest Paths (SSSP) and the 2-SAT problem (jointly), instead of reducing to CRCs. In passing, we obtain a faster (quadratic time) algorithm for RDTPs having only {t_1, t_2}-constraints and no t_3-constraint. As a second main contribution, we study the tractability frontier of solving RDTPs blended with Hyper Temporal Networks (HyTNs), a disjunctive strict generalization of Simple Temporal Networks (STNs) based on hypergraphs: we prove that solving temporal problems having only t_2-constraints and either only multi-tail or only multi-head hyperarc-constraints lies in NP cap co-NP and admits deterministic pseudo-polynomial time algorithms; on the other hand, problems having only t_3-constraints and either only multi-tail or only multi-head hyperarc-constraints turns out strongly NP-complete.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Computing methodologies → Temporal reasoning
  • Computing methodologies → Planning and scheduling
Keywords
  • Restricted Disjuctive Temporal Problems
  • Simple Temporal Networks
  • Hyper Temporal Networks
  • Consistency Checking
  • Single-Source Shortest-Paths
  • 2-SAT

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Bengt Aspvall, Michael F. Plass, and Robert Endre Tarjan. A linear-time algorithm for testing the truth of certain quantified boolean formulas. Information Processing Letters, 8(3):121-123, 1979. URL: http://dx.doi.org/10.1016/0020-0190(79)90002-4.
  2. Richard Bellman. On a routing problem. Quarterly of Applied Maths, 16(1):87-90, 1958. Google Scholar
  3. Carlo Comin, Roberto Posenato, and Romeo Rizzi. Hyper temporal networks - A tractable generalization of simple temporal networks and its relation to mean payoff games. Constraints, 22(2):152-190, 2017. URL: http://dx.doi.org/10.1007/s10601-016-9243-0.
  4. Rina Dechter. Constraint Processing. Morgan Kaufmann, San Francisco, CA, US, 2003. Google Scholar
  5. Rina Dechter, Itay Meiri, and Judea Pearl. Temporal constraint networks. Artificial Intelligence, 49(1-3):61-95, 1991. URL: http://dx.doi.org/10.1016/0004-3702(91)90006-6.
  6. Yves Deville, Olivier Barette, and Pascal Van Hentenryck. Constraint satisfaction over connected row-convex constraints. Artificial Intelligence, 109(1):243-271, 1999. URL: http://dx.doi.org/10.1016/S0004-3702(99)00012-0.
  7. E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1(1):269-271, Dec 1959. URL: http://dx.doi.org/10.1007/BF01386390.
  8. Manolis Koubarakis. Chapter 19 - temporal csps. In Francesca Rossi, Peter van Beek, and Toby Walsh, editors, Handbook of Constraint Programming, volume 2 of Foundations of AI, pages 665-697. Elsevier, 2006. URL: http://dx.doi.org/10.1016/S1574-6526(06)80023-4.
  9. T. K. Sathish Kumar. Tractable classes of metric temporal problems with domain rules. In Proceedings of the 21st National Conference on Artificial Intelligence - Volume 1, AAAI'06, pages 847-852. AAAI Press, 2006. Google Scholar
  10. T. K. Satish Kumar. On the tractability of restricted disjunctive temporal problems. In Proceedings of the Fifteenth International Conference on Automated Planning and Scheduling (ICAPS 2005), June 5-10 2005, Monterey, California, USA, pages 110-119, 2005. Google Scholar
  11. T. K. Satish Kumar, Marcello Cirillo, and Sven Koenig. Simple temporal problems with taboo regions. In Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence, AAAI'13, pages 548-554. AAAI Press, 2013. Google Scholar
  12. Dana Nau, Malik Ghallab, and Paolo Traverso. Automated Planning: Theory &Practice. Morgan Kaufmann, San Francisco, CA, USA, 2004. Google Scholar
  13. Angelo Oddi and Amedeo Cesta. Incremental forward checking for the disjunctive temporal problem. In Proceedings of the 14th European Conference on Artificial Intelligence, ECAI'00, pages 108-112, Amsterdam, The Netherlands, The Netherlands, 2000. IOS Press. Google Scholar
  14. A.K. Pani and G.P. Bhattacharjee. Temporal representation and reasoning in artificial intelligence: A review. Mathematical and Computer Modelling, 34(1):55-80, 2001. Google Scholar
  15. E. Schwalb and L. Vila. Temporal constraints: A survey. Constraints, 3(2):129-149, 1998. Google Scholar
  16. Kostas Stergiou and Manolis Koubarakis. Backtracking algorithms for disjunctions of temporal constraints. Artificial Intelligence, 120(1):81-117, 2000. Google Scholar
  17. Ioannis Tsamardinos and Martha E Pollack. Efficient solution techniques for disjunctive temporal reasoning problems. Artificial Intelligence, 151(1):43-89, 2003. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact