## 5.53. circuit

 DESCRIPTION LINKS GRAPH
Origin
Constraint

$\mathrm{𝚌𝚒𝚛𝚌𝚞𝚒𝚝}\left(\mathrm{𝙽𝙾𝙳𝙴𝚂}\right)$

Synonyms

$\mathrm{𝚊𝚝𝚘𝚞𝚛}$, $\mathrm{𝚌𝚢𝚌𝚕𝚎}$.

Argument
 $\mathrm{𝙽𝙾𝙳𝙴𝚂}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚒𝚗𝚍𝚎𝚡}-\mathrm{𝚒𝚗𝚝},\mathrm{𝚜𝚞𝚌𝚌}-\mathrm{𝚍𝚟𝚊𝚛}\right)$
Restrictions
 $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝙽𝙾𝙳𝙴𝚂},\left[\mathrm{𝚒𝚗𝚍𝚎𝚡},\mathrm{𝚜𝚞𝚌𝚌}\right]\right)$ $\mathrm{𝙽𝙾𝙳𝙴𝚂}.\mathrm{𝚒𝚗𝚍𝚎𝚡}\ge 1$ $\mathrm{𝙽𝙾𝙳𝙴𝚂}.\mathrm{𝚒𝚗𝚍𝚎𝚡}\le |\mathrm{𝙽𝙾𝙳𝙴𝚂}|$ $\mathrm{𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝}$$\left(\mathrm{𝙽𝙾𝙳𝙴𝚂},\mathrm{𝚒𝚗𝚍𝚎𝚡}\right)$ $\mathrm{𝙽𝙾𝙳𝙴𝚂}.\mathrm{𝚜𝚞𝚌𝚌}\ge 1$ $\mathrm{𝙽𝙾𝙳𝙴𝚂}.\mathrm{𝚜𝚞𝚌𝚌}\le |\mathrm{𝙽𝙾𝙳𝙴𝚂}|$
Purpose

Enforce to cover a digraph $G$ described by the $\mathrm{𝙽𝙾𝙳𝙴𝚂}$ collection with one circuit visiting once all vertices of $G$.

Example
$\left(\begin{array}{c}〈\begin{array}{cc}\mathrm{𝚒𝚗𝚍𝚎𝚡}-1\hfill & \mathrm{𝚜𝚞𝚌𝚌}-2,\hfill \\ \mathrm{𝚒𝚗𝚍𝚎𝚡}-2\hfill & \mathrm{𝚜𝚞𝚌𝚌}-3,\hfill \\ \mathrm{𝚒𝚗𝚍𝚎𝚡}-3\hfill & \mathrm{𝚜𝚞𝚌𝚌}-4,\hfill \\ \mathrm{𝚒𝚗𝚍𝚎𝚡}-4\hfill & \mathrm{𝚜𝚞𝚌𝚌}-1\hfill \end{array}〉\hfill \end{array}\right)$

The $\mathrm{𝚌𝚒𝚛𝚌𝚞𝚒𝚝}$ constraint holds since its $\mathrm{𝙽𝙾𝙳𝙴𝚂}$ argument depicts the following Hamiltonian circuit visiting successively the vertices 1, 2, 3, 4 and 1.

Typical
$|\mathrm{𝙽𝙾𝙳𝙴𝚂}|>2$
Symmetry

Items of $\mathrm{𝙽𝙾𝙳𝙴𝚂}$ are permutable.

Remark

In the original $\mathrm{𝚌𝚒𝚛𝚌𝚞𝚒𝚝}$ constraint of CHIP the $\mathrm{𝚒𝚗𝚍𝚎𝚡}$ attribute was not explicitly present. It was implicitly defined as the position of a variable in a list.

Within the context of linear programming [AlthausBockmayrElfKasperJungerMehlhorn02] this constraint was introduced under the name $\mathrm{𝚊𝚝𝚘𝚞𝚛}$. In the same context [Hooker07book] provides continuous relaxations of the $\mathrm{𝚌𝚒𝚛𝚌𝚞𝚒𝚝}$ constraint.

Within the KOALOG constraint system this constraint is called $\mathrm{𝚌𝚢𝚌𝚕𝚎}$.

Algorithm

Since all $\mathrm{𝚜𝚞𝚌𝚌}$ variables of the $\mathrm{𝙽𝙾𝙳𝙴𝚂}$ collection have to take distinct values one can reuse the algorithms associated with the $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraint. A second necessary condition is to have no more than one strongly connected component. Pruning for enforcing this condition can be done by forcing all strong bridges to belong to the final solution, since otherwise the strongly connected component would be broken apart. When the number of vertices is odd (i.e., $|\mathrm{𝙽𝙾𝙳𝙴𝚂}|$ is odd) a third necessary condition is to have a bipartite graph (see the Algorithm slot of the $\mathrm{𝚋𝚒𝚙𝚊𝚛𝚝𝚒𝚝𝚎}$ constraint).

Further necessary conditions (useful when the graph is sparse) combining the fact that we have a perfect matching and one single strongly connected component can be found in [ShufetBerliner94]. These conditions forget about the orientation of the arcs of the graph and characterise new required elementary chains. A typical pattern involving four vertices is depicted by Figure 5.53.1 where we assume that:

• There is an elementary chain between $c$ and $d$ (depicted by a dashed edge),

• $b$ has exactly 3 neighbours.

In this context the edge between $a$ and $b$ is mandatory in any covering (i.e., the arc from $a$ to $b$ or the arc from $b$ to $a$) since otherwise a small circuit involving $b$, $c$ and $d$ would be created.

##### Figure 5.53.1. Reasoning about elementary chains and degrees: if we have an elementary chain between $c$ and $d$ and if $b$ has 3 neighbours then the edge $\left(a,b\right)$ is mandatory. When the graph is planar [HopcroftTarjan74][Deo76] one can also use as a necessary condition discovered by Grinberg [Grinberg68] for pruning.

Finally, another approach based an the notion of 1 -toughness [Chvatal73] was proposed in [KayaHooker06] and evaluated for small graphs (i.e., graphs with up to 15 vertices).

Systems
See also

generalisation: $\mathrm{𝚌𝚢𝚌𝚕𝚎}$ (introduce a variable for the number of circuits).

Keywords
Arc input(s)

$\mathrm{𝙽𝙾𝙳𝙴𝚂}$

Arc generator
$\mathrm{𝐶𝐿𝐼𝑄𝑈𝐸}$$↦\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚗𝚘𝚍𝚎𝚜}\mathtt{1},\mathrm{𝚗𝚘𝚍𝚎𝚜}\mathtt{2}\right)$

Arc arity
Arc constraint(s)
$\mathrm{𝚗𝚘𝚍𝚎𝚜}\mathtt{1}.\mathrm{𝚜𝚞𝚌𝚌}=\mathrm{𝚗𝚘𝚍𝚎𝚜}\mathtt{2}.\mathrm{𝚒𝚗𝚍𝚎𝚡}$
Graph property(ies)
 $•$$\mathrm{𝐌𝐈𝐍}_\mathrm{𝐍𝐒𝐂𝐂}$$=|\mathrm{𝙽𝙾𝙳𝙴𝚂}|$ $•$$\mathrm{𝐌𝐀𝐗}_\mathrm{𝐈𝐃}$$=1$

Graph class
$\mathrm{𝙾𝙽𝙴}_\mathrm{𝚂𝚄𝙲𝙲}$

Graph model

The first graph property enforces to have one single strongly connected component containing $|\mathrm{𝙽𝙾𝙳𝙴𝚂}|$ vertices. The second graph property imposes to only have circuits. Since each vertex of the final graph has only one successor we do not need to use set variables for representing the successors of a vertex.

Parts (A) and (B) of Figure 5.53.2 respectively show the initial and final graph associated with the Example slot. The $\mathrm{𝚌𝚒𝚛𝚌𝚞𝚒𝚝}$ constraint holds since the final graph consists of one circuit mentioning once every vertex of the initial graph.

##### Figure 5.53.2. Initial and final graph of the $\mathrm{𝚌𝚒𝚛𝚌𝚞𝚒𝚝}$ constraint  (a) (b)
Signature

Since the initial graph contains $|\mathrm{𝙽𝙾𝙳𝙴𝚂}|$ vertices the final graph contains at most $|\mathrm{𝙽𝙾𝙳𝙴𝚂}|$ vertices. Therefore we can rewrite the graph property $\mathrm{𝐌𝐈𝐍}_\mathrm{𝐍𝐒𝐂𝐂}=|\mathrm{𝙽𝙾𝙳𝙴𝚂}|$ to $\mathrm{𝐌𝐈𝐍}_\mathrm{𝐍𝐒𝐂𝐂}\ge |\mathrm{𝙽𝙾𝙳𝙴𝚂}|$. This leads to simplify $\underline{\overline{\mathrm{𝐌𝐈𝐍}_\mathrm{𝐍𝐒𝐂𝐂}}}$ to $\overline{\mathrm{𝐌𝐈𝐍}_\mathrm{𝐍𝐒𝐂𝐂}}$.

Because of the graph property $\mathrm{𝐌𝐈𝐍}_\mathrm{𝐍𝐒𝐂𝐂}=|\mathrm{𝙽𝙾𝙳𝙴𝚂}|$ the final graph contains at least one vertex. Since a vertex $v$ belongs to the final graph only if there is an arc that has $v$ as one of its extremities the final graph contains at least one arc. Therefore $\mathrm{𝐌𝐀𝐗}_\mathrm{𝐈𝐃}$ is greater than or equal to 1. So we can rewrite the graph property $\mathrm{𝐌𝐀𝐗}_\mathrm{𝐈𝐃}=1$ to $\mathrm{𝐌𝐀𝐗}_\mathrm{𝐈𝐃}\le 1$. This leads to simplify $\underline{\overline{\mathrm{𝐌𝐀𝐗}_\mathrm{𝐈𝐃}}}$ to $\underline{\mathrm{𝐌𝐀𝐗}_\mathrm{𝐈𝐃}}$.