Como encontro a representação mais curta para um subconjunto de um conjunto de energia?

Estou procurando um algoritmo eficiente para o seguinte problema ou uma prova de dureza NP.

Deixe $\Sigma$ ser um conjunto e $A\subseteq\mathcal{P}(\Sigma)$ um conjunto de subconjuntos de $\Sigma$ . Encontrar uma sequência $w\in \Sigma^*$ de menos comprimento tal que, para cada $L\in A$ , há um $k\in\mathbb{N}$ tal que $\{ w_{k+i} \mid 0\leq i < |L| \} = L$ .

Por exemplo, para $A = \{\{a,b\},\{a,c\}\}$ , a palavra $w = bac$ é uma solução para o problema, pois para $\{a,b\}$ há $k=0$ , para $\{a,c\}$ existe $k=1$ .

Quanto à minha motivação, estou tentando representar o conjunto de arestas de um autômato finito, onde cada aresta pode ser rotulada por um conjunto de letras do alfabeto de entrada. Gostaria de armazenar uma única string e, em seguida, manter um par de ponteiros para essa string em cada borda. Meu objetivo é minimizar o comprimento dessa string.

Acredito que encontrei uma redução no caminho Hamiltoniano , provando o problema NP-difícil.

Chame a palavra w ∈ Σ * uma testemunha de A , se satisfizer a condição da questão (para cada L ∈ A , há m ≥ 1 tal 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$

Considere a versão de decisão do problema original, ou seja, decida se para alguns A e k ≥ 0 , há uma testemunha de A no máximo k . Esse problema pode ser resolvido usando o problema original como um oráculo no tempo polinomial (encontre a menor testemunha e compare seu comprimento com k ).$A$$k\geq 0$$A$$k$$k$

Agora, o núcleo da redução. Seja G = ( V , E ) um gráfico simples, não direcionado e conectado. Para cada v ∈ V , deixar L v = { v } ∪ { e ∈ E | v ∈ e } o conjunto contendo o vértice v e todos os seus bordos adjacentes. Defina Σ = E e A = { L v ∣ v ∈ V } . Então $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$possui um caminho hamiltoniano se, e somente se, houver uma testemunha de A no máximo 2 | E | + 1 .$A$$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.