[Solved]: How do I find the shortest representation for a subset of a powerset?

I believe I found a reduction from Hamiltonian path, thus proving the problem NP-hard. Call the word $winSigma^*$ a witness for $A$, if it satisfies the condition from the question (for each $Lin A$, there’s $mgeq 1$ such that ${w_{m+i}mid 0leq i<|L|} = L$). Consider the decision version of the original problem, i.e. decide whether for some $A$ and $kgeq 0$, there’s a witness for $A$ of length at most $k$. This problem can be solved using the original problem as an oracle in polynomial time (find the shortest witness, then compare its length to $k$). Now for the core of the reduction. Let $G=(V,E)$ be a simple, undirected, connected graph. For each $vin V$, let $L_v={v}cup{ein Emid vin e}$ be the set containing the vertex $v$ and all of its adjacent edges. Set $Sigma=E$ and $A={L_vmid vin V}$. Then $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_2ldots 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_vsetminus H$. Choose an arbitrary ordering $alpha_v$ for each $U_v$. The word $w=alpha_{v_1}e_1alpha_{v_2}e_2ldots 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$, $inotin{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 $ein E$ and $vin V$ occurs in $w$ at least once. Without loss of generality, assume that each $ein E$ occurs in $w$ at most twice and each $vin V$ occurs exactly once; otherwise a shorter witness can be found by removing elements from $w$. Let $Hsubseteq 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_2ldots e_kv$, where $u,vin V$, $e_iin E$. We say that $u,v$ are adjacent. Notice that if $e_iin 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_2ldots h_{n-1}$ all elements from $H$ in the order they appear in $w$. It follows that $v_1h_1v_2h_2ldots 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.