Comment trouver la représentation la plus courte pour un sous-ensemble d'un jeu de puissances?

Je recherche un algorithme efficace pour le problème suivant ou une preuve de dureté NP.

Soit $\Sigma$ un ensemble et $A\subseteq\mathcal{P}(\Sigma)$ un ensemble de sous-ensembles de $\Sigma$ . Trouver une séquence $w\in \Sigma^*$ de moindre longueur telle que pour chaque $L\in A$ , il existe un $k\in\mathbb{N}$ tel que $\{ w_{k+i} \mid 0\leq i < |L| \} = L$ .

Par exemple, pour $A = \{\{a,b\},\{a,c\}\}$ , le mot $w = bac$ est une solution au problème, car pour $\{a,b\}$ il y a $k=0$ , pour $\{a,c\}$ il y a $k=1$ .

Quant à ma motivation, j'essaie de représenter l'ensemble des bords d'un automate fini, où chaque bord peut être étiqueté par un ensemble de lettres de l'alphabet d'entrée. Je voudrais stocker une seule chaîne, puis conserver une paire de pointeurs vers cette chaîne à chaque bord. Mon objectif est de minimiser la longueur de cette chaîne.

Je crois avoir trouvé une réduction du chemin hamiltonien , prouvant ainsi le problème NP-difficile.

Appelons le mot w ∈ Σ ∗ un témoin pour A , s'il satisfait la condition de la question (pour chaque L ∈ A , il y a m ≥ 1 tel que { w m + i ∣ 0 ≤ i < | L | } = L ) .$w\in\Sigma^*$$A$$L\in A$$m\geq 1$$\{w_{m+i}\mid 0\leq i<|L|\} = L$

Considérons la version de décision du problème d'origine, c'est-à-dire décider si pour certains A et k ≥ 0 , il y a un témoin pour A de longueur au plus k . Ce problème peut être résolu en utilisant le problème d'origine comme un oracle en temps polynomial (trouver le témoin le plus court, puis comparer sa longueur à k ).$A$$k\geq 0$$A$$k$$k$

Maintenant, au cœur de la réduction. Soit G = ( V , E ) un graphe simple, non orienté et connecté. Pour chaque v ∈ V , soit L v = { v } ∪ { e ∈ E ∣ v ∈ e } l'ensemble contenant le sommet v et toutes ses arêtes adjacentes. Réglez Σ = E et A = { L v ∣ v ∈ V } . Alors $G=(V,E)$$v\in V$$L_v=\{v\}\cup\{e\in E\mid v\in e\}$$v$$\Sigma=E$$A=\{L_v\mid v\in V\}$$G$ has a Hamiltonian path if and only if there is a witness for $A$ of length at most $2|E|+1$.

Proof. Let $v_1e_1v_2\ldots e_{n-1}v_n$ be a Hamiltonian path in $G$ and $H=\{e_1, e_2, \ldots, e_{n-1}\}$ the set of all edges on the path. For each vertex $v$, define the set $U_v=L_v\setminus H$. Choose an arbitrary ordering $\alpha_v$ for each $U_v$. The word $w=\alpha_{v_1}e_1\alpha_{v_2}e_2\ldots e_{n-1}\alpha_{v_n}$ is a witness for $A$, since $L_{v_1}$ is represented by the substring $\alpha_1e_1$, $L_{v_n}$ by $e_{n-1}\alpha_n$, and for each $v_i$, $i\notin\{1, n\}$, $L_{v_i}$ is represented by $e_{i-1}u_{v_i}e_i$. Furthermore, each edge in $E$ occurs twice in $w$ with the exception of $|V|-1$ edges in $H$, which occur once, and each vertex in $V$ occurs once, giving $|w|=2|E|+1$.

For the other direction, let $w$ be an arbitrary witness for $A$ of length at most $2|E|+1$. Clearly, each $e\in E$ and $v\in V$ occurs in $w$ at least once. Without loss of generality, assume that each $e\in E$ occurs in $w$ at most twice and each $v\in V$ occurs exactly once; otherwise a shorter witness can be found by removing elements from $w$. Let $H\subseteq E$ be the set of all edges occurring in $w$ exactly once. Given the assumptions above, it holds that $|w|=2|E|-|H|+|V|$.

Consider a contiguous substring of $w$ of the form $ue_1e_2\ldots e_kv$, where $u,v\in V$, $e_i\in E$. We say that $u,v$ are adjacent. Notice that if $e_i\in H$, then $e_i=\{u,v\}$, because $e_i$ occurs only once, yet it is adjacent to two vertices in $G$. Therefore, at most one of $e_i$ can be in $H$. Similarly, no edge in $H$ can occur in $w$ before the first vertex or after the last vertex.

Now, there are $|V|$ vertices, therefore $|H|\leq |V|-1$. From there, it follows that $|w|\geq 2|E|+1$. Since we assume $|w|\leq 2|E|+1$, we get equality. From there we get $|H|=|V|-1$. By pigeonhole principle, there is an edge from $H$ between each pair of vertices adjacent in $w$. Denote $h_1h_2\ldots h_{n-1}$ all elements from $H$ in the order they appear in $w$. It follows that $v_1h_1v_2h_2\ldots h_{n-1}v_n$ is a Hamiltonian path in $G$. $\square$

Since the problem of deciding the existence of Hamiltonian path is NP-hard and the above reduction is polynomial, the original problem is NP-hard too.