You are here

Positive and Negative Length-Bound Reachability Constraints

Publication Type: 
Refereed Conference Meeting Proceeding
Abstract: 
In many application problems, including physical security and wildlife conservation, infrastructure must be configured to ensure or deny paths between specified locations. We model the problem as sub-graph design subject to constraints on paths and path lengths, and propose length-bound reachability constraints. Although reachability in graphs has been modelled before in constraint programming, the interaction of positive and negative reachability has not been studied in depth. We prove that deciding whether a set of positive and negative reachability constraints are satisfiable is NP complete. We show the effectiveness of our approach on decision problems, and also on optimisation problems. We compare our approach with existing constraint models, and we demonstrate significant improvements in runtime and solution costs, on a new problem set.
Conference Name: 
27th International Conference on Principles and Practice of Constraint Programming (CP 2021)
Proceedings: 
Proceedings of the 27th International Conference on Principles and Practice of Constraint Programming (CP 2021)
Digital Object Identifer (DOI): 
10.4230/LIPIcs.CP.2021.46
Publication Date: 
15/10/2021
Volume: 
210
Pages: 
46:1--46:16
Conference Location: 
France
Institution: 
National University of Ireland, Cork (UCC)
Open access repository: 
Yes
Publication document: