Positive and negative length-bound reachability constraints
Loading...
Files
Published Version
Date
2021-10-15
Authors
Quesada, Luis
Brown, Kenneth N.
Journal Title
Journal ISSN
Volume Title
Publisher
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Published Version
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.
Description
Keywords
Reachability constraints , Graph connectivity , Constraint programming
Citation
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