[Lauriere78]

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

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

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

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

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{𝚌𝚢𝚌𝚕𝚎}$.

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., $\left|\mathrm{𝙽𝙾𝙳𝙴𝚂}\right|$ 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 $(a,b)$ 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).

circuit in Gecode, circuit in JaCoP, circuit in SICStus.

common keyword: $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ (permutation), $\mathrm{𝚌𝚒𝚛𝚌𝚞𝚒𝚝}\_\mathrm{𝚌𝚕𝚞𝚜𝚝𝚎𝚛}$ (graph constraint, one_succ), $\mathrm{𝚙𝚊𝚝𝚑}$ (graph partitioning constraint, one_succ), $\mathrm{𝚝𝚘𝚞𝚛}$ (graph partitioning constraint, Hamiltonian).

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

implies: $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$.

related: $\mathrm{𝚜𝚝𝚛𝚘𝚗𝚐𝚕𝚢}\_\mathrm{𝚌𝚘𝚗𝚗𝚎𝚌𝚝𝚎𝚍}$.

combinatorial object: permutation.

constraint type: graph constraint, graph partitioning constraint.

filtering: linear programming, planarity test, strong bridge, DFS-bottleneck.

final graph structure: circuit, one_succ.

problems: Hamiltonian.

$\mathrm{𝙽𝙾𝙳𝙴𝚂}$

The first graph property enforces to have one single strongly connected component containing $\left|\mathrm{𝙽𝙾𝙳𝙴𝚂}\right|$ 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)

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

Because of the graph property $\mathrm{𝐌𝐈𝐍}\_\mathrm{𝐍𝐒𝐂𝐂}=\left|\mathrm{𝙽𝙾𝙳𝙴𝚂}\right|$ 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{𝐈𝐃}}$.