Longest sequence of dominoes

Question

Given $k$, a $k$-domino is a non-ordered pair of integer values of $[\![0, k-1]\!]$, for example $\langle 0, 3\rangle$ or $\langle 1, 1\rangle$ are dominoes, the domino $\langle 3, 0\rangle$ being the same as $\langle 0, 3\rangle$.

A sequence of length $n$ of dominoes is a sequence $(d_0, d_1, …, d_{n-1})$ where $d_i = \langle a_i, b_i\rangle$ is a domino, and $\forall i \in [\![0, n-2]\!], b_i = a_{i+1}$. For example, $\langle 2,3\rangle\langle 3,5\rangle\langle 5,2\rangle\langle 2,1\rangle$ is a sequence of length 4.

Given $k$ and $N$, and a set $S$ of $N$ distincts $k$-dominoes, I want to find the longest sequence of dominoes constructible using each domino in the set $S$ at most once.

My ideas so far are to use some kind of backtracking algorithm: I try to complete a sequence of dominoes with a new domino – among those not used, or not eliminated – and if it is valid, I continue; if there is no valid domino, I delete and elimininate the last domino to try again. I am using hash table to keep track of the remaining dominoes.

I wondered if there is a more efficient/elegant way to do it, maybe by pre-sorting the set $S$ before trying to construct sequences of dominoes, or using dynamic programming in a way I haven't found yet.

I also thought of constructing a graph with each domino as a vertex, but I don't really know how to put edges because of the two faces of the domino: if I add an edge between two dominoes that have a common value, then I risk to find $\langle 1,2\rangle\langle 2,3\rangle\langle 2,0\rangle$ as a valid sequence…

One of the ideas proposed in the comments is to construct a graph where vertices are integers of $[\![0,k-1]\!]$ and edges are dominoes of $S$ (domino $\langle a , b\rangle$ is an edge between $a$ and $b$, possibly a loop if $a = b$). The question is now equivalent to finding a longest path in this graph. The problem is that it is not similar to longest path problem because the path are not necessarily simples (meaning a path can cross the same vertex multiple times). One would need to keep track of used edges to find the longest path, so it does not really simplify the problem.

The problem is difficult and seems even $NP$-hard, but I still want to find an efficient algorithm solving it. My current backtracking solution find the answer for $k = 20$ and $N = 30$ in 10 sec (for a randomly generated set of distinct dominoes), but it increases quickly if I lower the value of $k$ or increase the value of $N$ (even $k = 15$ and $N = 30$ is taking ~30 minutes).

Answer 1

Your problem is NP-hard. Consider an instance of Hamiltonian path graph $G=(V,E)$ in which the degree of each vertex is at most $3$ and we are given a starting vertex $s$ and ending vertex $t$ both of degree at most $2$ (the problem remains hard in this case). W.l.o.g., let $V=\{3,\dots,k-4\}$, $s=3$, and $t=k-4$.

Create the dominoes $(0,1)$, $(1,2)$, $(2,3)$, $(k-4, k-3)$, $(k-3, k-2)$, and $(k-2, k-1)$. Create one "edge" domino $(a,b)$ for each edge $(a,b) \in E$.

There exists an Hamiltonian path in $G$ if and only if there is a sequence of $k-1$ dominoes. Indeed, notice that any sequence of dominoes that only uses the dominoes from $E$ traces a (not-necessarily simple) path $P$ in $G$. But then, all vertices except the endpoints of $P$ must be traversed at most once (since their degree is at most $3$). The two endpoints can extend the path by at most $2$. Then the number of edges of $P$ can be at most $|V|+1 = k-6+1 = k-5$. This implies that a sequence of $k-1$ dominoes must use all "non-edge" dominoes, i.e., the sequence of dominoes must start with $(0,1), \dots, (2,3)$ and end with $(k-4, k-4), \dots, (k-2, k-1)$. Then, the path induced by the sub-sequence obtained by dropping the "non-edge" dominoes must be simple and traverses $k-1-6 = k-7 = |V|-1$ edges of $G$, i.e., it is an Hamiltonian path in $G$.

Conversely, we can create a sequence of $\ell+6$ dominoes from any simple path of length $\ell$ from $s$ to $t$ in $G$ (simply prepend $(0,1), \dots, (2,3)$ and append $(k-4, k-4), \dots, (k-2, k-1)$). For an Hamiltoniam path we have $\ell=|V|-1=k-7$, therefore the sequence has length $k-1$.

Answer 2

Regarding each given domino as an edge in a graph connecting the vertices labelled from $[\![0, k-1]\!]$, with "doubles" $\langle j,j\rangle$ handled separately, we need to answer:

• is the graph connected? In general this will be an easy question because most cases will have a much smaller number of vertices than edges. If the answer is "no", the problem sub-divides into the connected components of the graph.
• how many vertices of odd degree are there? This determines the existence of a Eulerian path and so whether all dominoes in the current problem can be included, or otherwise gives initial information to assess which dominoes may need to be excluded. If there are zero or two odd-degree vertices, a Eulerian path is possible and all dominoes can be used.
• for the case where a Eulerian path is not possible, we need to find short paths that link together odd-degree nodes whose removal will not disconnect the graph (but see extra note). These would constitute the dominoes that are not going to be used; the shortest paths that connect pairs of odd-degree nodes (allowing two such to remain) give the dominoes to set aside.
  Example adjustment, showing odd-degree nodes in gold and removed edges in red:

Either as given or as adjusted by removal, a Eulerian path can found using e.g. Hierholzer's algorithm

Handling doubles: These can be kept as a separate list; they are included if there is any other connection to that value (vertex). If consideration is made of which dominoes to ignore, if a double is attached to a node that otherwise has only degree one, this could change the optimum set of dominoes to exclude since the double would also then be unused.

---

Extra note: finding the paths that connect the odd-degree nodes may not permit keeping the graph connected in some cases, even limiting that to a substantial disconnection (more than just leaving an isolated node), especially if the edges (dominoes) are relatively few and the vertices (values) many. Finding bridges in the graph would allow detection of this case; these can be found in linear time. Example graph: