## 5.382. subgraph_isomorphism

Origin
Constraint

$\mathrm{𝚜𝚞𝚋𝚐𝚛𝚊𝚙𝚑}_\mathrm{𝚒𝚜𝚘𝚖𝚘𝚛𝚙𝚑𝚒𝚜𝚖}\left(\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝙿𝙰𝚃𝚃𝙴𝚁𝙽},\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝚃𝙰𝚁𝙶𝙴𝚃},\mathrm{𝙵𝚄𝙽𝙲𝚃𝙸𝙾𝙽}\right)$

Arguments
 $\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝙿𝙰𝚃𝚃𝙴𝚁𝙽}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚒𝚗𝚍𝚎𝚡}-\mathrm{𝚒𝚗𝚝},\mathrm{𝚜𝚞𝚌𝚌}-\mathrm{𝚜𝚒𝚗𝚝}\right)$ $\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝚃𝙰𝚁𝙶𝙴𝚃}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚒𝚗𝚍𝚎𝚡}-\mathrm{𝚒𝚗𝚝},\mathrm{𝚜𝚞𝚌𝚌}-\mathrm{𝚜𝚟𝚊𝚛}\right)$ $\mathrm{𝙵𝚄𝙽𝙲𝚃𝙸𝙾𝙽}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚒𝚖𝚊𝚐𝚎}-\mathrm{𝚍𝚟𝚊𝚛}\right)$
Restrictions
 $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝙿𝙰𝚃𝚃𝙴𝚁𝙽},\left[\mathrm{𝚒𝚗𝚍𝚎𝚡},\mathrm{𝚜𝚞𝚌𝚌}\right]\right)$ $\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝙿𝙰𝚃𝚃𝙴𝚁𝙽}.\mathrm{𝚒𝚗𝚍𝚎𝚡}\ge 1$ $\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝙿𝙰𝚃𝚃𝙴𝚁𝙽}.\mathrm{𝚒𝚗𝚍𝚎𝚡}\le |\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝙿𝙰𝚃𝚃𝙴𝚁𝙽}|$ $\mathrm{𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝}$$\left(\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝙿𝙰𝚃𝚃𝙴𝚁𝙽},\mathrm{𝚒𝚗𝚍𝚎𝚡}\right)$ $\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝙿𝙰𝚃𝚃𝙴𝚁𝙽}.\mathrm{𝚜𝚞𝚌𝚌}\ge 1$ $\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝙿𝙰𝚃𝚃𝙴𝚁𝙽}.\mathrm{𝚜𝚞𝚌𝚌}\le |\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝙿𝙰𝚃𝚃𝙴𝚁𝙽}|$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝚃𝙰𝚁𝙶𝙴𝚃},\left[\mathrm{𝚒𝚗𝚍𝚎𝚡},\mathrm{𝚜𝚞𝚌𝚌}\right]\right)$ $\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝚃𝙰𝚁𝙶𝙴𝚃}.\mathrm{𝚒𝚗𝚍𝚎𝚡}\ge 1$ $\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝚃𝙰𝚁𝙶𝙴𝚃}.\mathrm{𝚒𝚗𝚍𝚎𝚡}\le |\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝚃𝙰𝚁𝙶𝙴𝚃}|$ $\mathrm{𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝}$$\left(\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝚃𝙰𝚁𝙶𝙴𝚃},\mathrm{𝚒𝚗𝚍𝚎𝚡}\right)$ $\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝚃𝙰𝚁𝙶𝙴𝚃}.\mathrm{𝚜𝚞𝚌𝚌}\ge 1$ $\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝚃𝙰𝚁𝙶𝙴𝚃}.\mathrm{𝚜𝚞𝚌𝚌}\le |\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝚃𝙰𝚁𝙶𝙴𝚃}|$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝙵𝚄𝙽𝙲𝚃𝙸𝙾𝙽},\left[\mathrm{𝚒𝚖𝚊𝚐𝚎}\right]\right)$ $\mathrm{𝙵𝚄𝙽𝙲𝚃𝙸𝙾𝙽}.\mathrm{𝚒𝚖𝚊𝚐𝚎}\ge 1$ $\mathrm{𝙵𝚄𝙽𝙲𝚃𝙸𝙾𝙽}.\mathrm{𝚒𝚖𝚊𝚐𝚎}\le |\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝚃𝙰𝚁𝙶𝙴𝚃}|$ $\mathrm{𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝}$$\left(\mathrm{𝙵𝚄𝙽𝙲𝚃𝙸𝙾𝙽},\mathrm{𝚒𝚖𝚊𝚐𝚎}\right)$ $|\mathrm{𝙵𝚄𝙽𝙲𝚃𝙸𝙾𝙽}|=|\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝙿𝙰𝚃𝚃𝙴𝚁𝙽}|$
Purpose

Given two directed graphs $\mathrm{𝙿𝙰𝚃𝚃𝙴𝚁𝙽}$ and $\mathrm{𝚃𝙰𝚁𝙶𝙴𝚃}$ enforce a one to one correspondence, defined by the function $\mathrm{𝙵𝚄𝙽𝙲𝚃𝙸𝙾𝙽}$, between the vertices of the graph $\mathrm{𝙿𝙰𝚃𝚃𝙴𝚁𝙽}$ and the vertices of an induced subgraph of $\mathrm{𝚃𝙰𝚁𝙶𝙴𝚃}$ so that, if there is an arc from $u$ to $v$ in the graph $\mathrm{𝙿𝙰𝚃𝚃𝙴𝚁𝙽}$, then there is also an arc from the image of $u$ to the image of $v$ in the induced subgraph of $\mathrm{𝚃𝙰𝚁𝙶𝙴𝚃}$. The vertices of both graphs are respectively defined by the two collections of vertices $\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝙿𝙰𝚃𝚃𝙴𝚁𝙽}$ and $\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝚃𝙰𝚁𝙶𝙴𝚃}$. Within collection $\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝙿𝙰𝚃𝚃𝙴𝚁𝙽}$ the set of successors of each node is fixed, while this is not the case for the collection $\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝚃𝙰𝚁𝙶𝙴𝚃}$. This stems from the fact that the $\mathrm{𝚃𝙰𝚁𝙶𝙴𝚃}$ graph is not fixed (i.e., the lower and upper bounds of the target graph are specified when we post the $\mathrm{𝚜𝚞𝚋𝚐𝚛𝚊𝚙𝚑}_\mathrm{𝚒𝚜𝚘𝚖𝚘𝚛𝚙𝚑𝚒𝚜𝚖}$ constraint, while the induced subgraph of a solution to the $\mathrm{𝚜𝚞𝚋𝚐𝚛𝚊𝚙𝚑}_\mathrm{𝚒𝚜𝚘𝚖𝚘𝚛𝚙𝚑𝚒𝚜𝚖}$ constraint corresponds to a graph for which the upper and lower bounds are identical).

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

Figure 5.382.1 gives the pattern (see Part (A)) and target graph (see Part (B)) of the Example slot as well as the one to one correspondence (see Part (C)) between the pattern graph and the induced subgraph of the target graph. The $\mathrm{𝚜𝚞𝚋𝚐𝚛𝚊𝚙𝚑}_\mathrm{𝚒𝚜𝚘𝚖𝚘𝚛𝚙𝚑𝚒𝚜𝚖}$ constraint since:

• To the arc from vertex 1 to vertex 4 in the pattern graph corresponds the arc from vertex 4 to 5 in the induced subgraph of the target graph.

• To the arc from vertex 1 to vertex 2 in the pattern graph corresponds the arc from vertex 4 to 2 in the induced subgraph of the target graph.

• To the arc from vertex 2 to vertex 1 in the pattern graph corresponds the arc from vertex 2 to 4 in the induced subgraph of the target graph.

• To the arc from vertex 2 to vertex 4 in the pattern graph corresponds the arc from vertex 2 to 5 in the induced subgraph of the target graph.

• To the arc from vertex 2 to vertex 3 in the pattern graph corresponds the arc from vertex 2 to 3 in the induced subgraph of the target graph.

##### Figure 5.382.1. Illustration of the Example slot: (A) The pattern graph, (B) a possible initial target graph – plain arcs must belong to the induced subgraph, while dotted arcs may or may not belong to the induced subgraph – and (C) the correspondence, denoted by thick dashed arcs, between the vertices of the pattern graph and the vertices of the induced subgraph of the target graph. Within a set variable a bold value (respectively a plain value) represents a value that for sure belong (respectively that may belong) to the set. Typical
 $|\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝙿𝙰𝚃𝚃𝙴𝚁𝙽}|>1$ $|\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝚃𝙰𝚁𝙶𝙴𝚃}|>1$
Symmetries
• Items of $\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝙿𝙰𝚃𝚃𝙴𝚁𝙽}$ are permutable.

• Items of $\mathrm{𝙽𝙾𝙳𝙴𝚂}_\mathrm{𝚃𝙰𝚁𝙶𝙴𝚃}$ are permutable.

Usage

Within the context of constraint programming the constraint was used for finding symmetries [Puget03], [Puget05a], [Puget05b].

Algorithm