Positive and negative length-bound reachability constraints

Thumbnail Image
LIPIcs-CP-2021-46.pdf(1.3 MB)
Published Version
Quesada, Luis
Brown, Kenneth N.
Journal Title
Journal ISSN
Volume Title
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Research Projects
Organizational Units
Journal Issue
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.
Reachability constraints , Graph connectivity , Constraint programming
Quesada, L. and Brown, K. N. (2021) 'Positive and negative length-bound reachability constraints', 27th International Conference on Principles and Practice of Constraint Programming (CP 21), Montpellier, France, 25 - 29 October, 46 (16pp). doi: 10.4230/LIPIcs.CP.2021.46
Link to publisher’s version