On restricted disjunctive temporal problems: faster algorithms and tractability frontier

DOI10.4230/LIPICS.TIME.2018.10MaRDI QIDQ5079776zbMATH OpenOpenAlexFDO

Authors Carlo Comin, Romeo Rizzi

Publication date 28 May 2022

Full work available at URL https://arxiv.org/abs/1805.02183

zbMATH Keywords

2-SATconsistency checkinghyper-temporal networksrestricted disjuctive temporal problemssimple temporal networkssingle-source shortest-paths

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Abstract: In 2005 Kumar studied the Restricted Disjunctive Temporal Problem (RDTP), a restricted but very expressive class of disjunctive temporal problems (DTPs). It was shown that that RDTPs are solvable in deterministic strongly-polynomial time by reducing them to the Connected Row-Convex (CRC) constraints problem; plus, Kumar devised a randomized algorithm whose expected running time is less than that of the deterministic one. 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 both the deterministic and randomized algorithms of Kumar. 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 Type-1 and Type-2 constraints (and no Type-3 constraint). As a second main contribution, we study the tractability frontier of solving RDTPs by considering Hyper Temporal Networks (HTNs), a strict generalization of STNs grounded on hypergraphs: on one side, we prove that solving temporal problems having only Type-2 constraints and either only multi-tail or only multi-head hyperarc constraints lies in both NP and co-NP and it admits deterministic pseudo-polynomial time algorithms; on the other side, solving problems with Type-3 constraints and either only multi-tail or only multi-head hyperarc constraints turns strongly NP-complete.

Recommendations

• Efficient solution techniques for disjunctive temporal reasoning problems
• Backtracking algorithms for disjunctions of temporal constraints
• Hyper temporal networks. A tractable generalization of simple temporal networks and its relation to mean payoff games
• Translation-based approaches for solving disjunctive temporal problems with preferences
• Solving disjunctive temporal problems with preferences using maximum satisfiability

Cites work

• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A note on two problems in connexion with graphs
• Boosting search with variable elimination in constraint optimization and constraint satisfaction problems
• Constraint satisfaction over connected row-convex constraints
• scientific article; zbMATH DE number 2201583 (Why is no real title available?)
• Hyper temporal networks. A tractable generalization of simple temporal networks and its relation to mean payoff games
• On a routing problem
• Temporal constraint networks

Cited in

(3)

• The complexity of finding temporal separators under waiting time constraints
• Translation-based approaches for solving disjunctive temporal problems with preferences
• An interdisciplinary experimental evaluation on the disjunctive temporal problem

This page was built for publication: On restricted disjunctive temporal problems: faster algorithms and tractability frontier

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5079776)