2
$\begingroup$

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).

$\endgroup$
13
  • 1
    $\begingroup$ Is this a question in a CS course? The problem is equivalent to a well-known graph theory problem, but telling you what it is might defeat the purpose of the exercise. $\endgroup$ Mar 26, 2021 at 22:50
  • $\begingroup$ Yes it is a question in a (future) CS course, but… I'm the teacher! (though I swallowed my pride when asking the question). I edited the question to add my thoughts about graphs. But I would like to use a solution without graph theory since my students have yet to study it. $\endgroup$
    – Nathaniel
    Mar 26, 2021 at 23:02
  • 1
    $\begingroup$ @Steven All dominoes are supposed to be distinct. $\endgroup$
    – Nathaniel
    Mar 26, 2021 at 23:37
  • 1
    $\begingroup$ @Steven Again, I don't want to necessarily use all dominoes. Also, since dominoes are edges, would it not be an Eulerian path instead of a Hamiltonian path? $\endgroup$
    – Nathaniel
    Mar 26, 2021 at 23:41
  • 1
    $\begingroup$ @Nathaniel, instead of Hamiltonian path, you're looking for the longest path. $\endgroup$
    – Steven
    Mar 26, 2021 at 23:49

2 Answers 2

3
$\begingroup$

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$.

$\endgroup$
8
  • $\begingroup$ As said in my original post, a simple path in $G$ does not induce a valide sequence, since $\langle 1,2\rangle\langle 2,3\rangle\langle 2,0\rangle$ is not valid (but is a path in $G$). $\endgroup$
    – Nathaniel
    Mar 27, 2021 at 0:55
  • $\begingroup$ Well thanks for your answer, it was already pretty clear to me that the problem was NP-hard, but I still wonder if there is an efficient way to compute a solution (obviously in exponential time). $\endgroup$
    – Nathaniel
    Mar 27, 2021 at 1:05
  • $\begingroup$ Can you clarify how finding the Hamiltonian path relates to maximizing domino use? Thanks. $\endgroup$
    – Joffan
    Mar 29, 2021 at 16:34
  • $\begingroup$ Any path in $G$ is essentially a sequence of dominoes, and all such dominoes are of the form $(a,b)$ with $a,b \in \{3,k-4\}$. Moreover, if the path starts with $s$ you can prepend $(0,1), (1,2), (2,3)$ to this sequence, and if the path ends with $t$ you can aooebd $(k-4, k-3), (k-3, k-2), (k-2, k-1)$. Since the converse is also true (any sequence of dominoes can be mapped to a path of the same length except possibly for a prefix/suffix similar to the ones above), in order to maximize the used dominoes you want to find the longest simple path from $s$ to $t$, i.e., an Hamiltonian path. $\endgroup$
    – Steven
    Mar 29, 2021 at 18:16
  • 1
    $\begingroup$ A vertex could, in theory, be visited twice but keep in mind that each vertex of the graph has degree at most $3$ (and $s$ and $t$ have degree $2$). Once you enter and exit a vertex, visiting it again would leave you no way to continue your path. So you could have non-simple paths but at most 2 vertices would be repeated (and they must those at the endpoints of the path). The prefixes and suffixes ensure that is is never convenient to do so. Since a sequence of length $k-7$ must use both the prefix and the suffix, no vertex can be repeated in the corresponding path. $\endgroup$
    – Steven
    Mar 29, 2021 at 19:04
2
$\begingroup$

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: enter image description here

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:

enter image description here

$\endgroup$
8
  • $\begingroup$ Thanks, this is a nice idea, but does it guarantee that it finds a longest sequence of dominoes? It seems to me that this algorithm is executed in polynomial time (since finding connected components, shortest paths and eulerian path are all done in polynomial time), which contradicts Steven's answer (or proves that $P = NP$, congratulations!). $\endgroup$
    – Nathaniel
    Mar 27, 2021 at 11:06
  • $\begingroup$ The Eulerian path includes all retained dominoes; the only tricky part is finding which dominoes to discard (the best paths between odd nodes) to bring the count of odd-degree nodes down to two. $\endgroup$
    – Joffan
    Mar 27, 2021 at 11:09
  • $\begingroup$ Also, if you consider a graph with a vertex connected to four other vertices (and no other edges), there are 4 odd-degree nodes, but there is no path between odd-degree nodes that lets the graph connected, so the algorithm fails. $\endgroup$
    – Nathaniel
    Mar 27, 2021 at 11:19
  • $\begingroup$ Disconnecting a degree-1 vertex is acceptable. (Although this where the potential loss of using a double should be weighted in) $\endgroup$
    – Joffan
    Mar 27, 2021 at 11:23
  • 1
    $\begingroup$ Now I've had some conversation and clarification on Steven's answer, I can see what the process is there and understand the problem case that is being exhibited. When there are many odd-degree vertices, the issue of finding which ones to pair up for optimum path becomes a jungle, many possible options, most of which are not optimum. $\endgroup$
    – Joffan
    Mar 29, 2021 at 23:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.