License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CP.2021.46
URN: urn:nbn:de:0030-drops-153372
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15337/
Go to the corresponding LIPIcs Volume Portal

Quesada, Luis ; Brown, Kenneth N.

Positive and Negative Length-Bound Reachability Constraints

pdf-format:
LIPIcs-CP-2021-46.pdf (1 MB)

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.

BibTeX - Entry

@InProceedings{quesada_et_al:LIPIcs.CP.2021.46,
  author =	{Quesada, Luis and Brown, Kenneth N.},
  title =	{{Positive and Negative Length-Bound Reachability Constraints}},
  booktitle =	{27th International Conference on Principles and Practice of Constraint Programming (CP 2021)},
  pages =	{46:1--46:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-211-2},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{210},
  editor =	{Michel, Laurent D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/15337},
  URN =		{urn:nbn:de:0030-drops-153372},
  doi =		{10.4230/LIPIcs.CP.2021.46},
  annote =	{Keywords: Reachability Constraints, Graph Connectivity, Constraint Programming}
}

Keywords: Reachability Constraints, Graph Connectivity, Constraint Programming
Collection: 27th International Conference on Principles and Practice of Constraint Programming (CP 2021)
Issue Date: 2021
Date of publication: 15.10.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI