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.29
URN: urn:nbn:de:0030-drops-153200
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15320/
Go to the corresponding LIPIcs Volume Portal

Isoart, Nicolas ; Régin, Jean-Charles

A Linear Time Algorithm for the k-Cutset Constraint

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

Abstract

In CP, the most efficient model solving the TSP is the Weighted Circuit Constraint (WCC) combined with the k-cutset constraint. The WCC is mainly based on the edges cost of a given graph whereas the k-cutset constraint is a structural constraint. Specifically, for each cutset in a graph, the k-cutset constraint imposes that the size of the cutset is greater than or equal to two. In addition, any solution contains an even number of elements from this cutset. Isoart and Régin introduced an algorithm for this constraint. Unfortunately, their approach leads to a time complexity growing with the size of the considered cutsets, i.e. with k. Thus, they introduced an algorithm with a quadratic complexity dealing with k lower or equal to three. In this paper, we introduce a linear time algorithm for any k based on a DFS checking the consistency of this constraint and performing its filtering. Experimental results show that the size of most of the k-cutsets is lower or equal than 3. In addition, since the time complexity is improved, our algorithm also improves the solving times.

BibTeX - Entry

@InProceedings{isoart_et_al:LIPIcs.CP.2021.29,
  author =	{Isoart, Nicolas and R\'{e}gin, Jean-Charles},
  title =	{{A Linear Time Algorithm for the k-Cutset Constraint}},
  booktitle =	{27th International Conference on Principles and Practice of Constraint Programming (CP 2021)},
  pages =	{29:1--29: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/15320},
  URN =		{urn:nbn:de:0030-drops-153200},
  doi =		{10.4230/LIPIcs.CP.2021.29},
  annote =	{Keywords: k-Cutset, TSP, Linear algorithm, Constraint}
}

Keywords: k-Cutset, TSP, Linear algorithm, Constraint
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