[Solved]: Are regex crosswords NP-hard?

Given a graph $G=(V,E)$ and a threshold $k$, is there a subset $V’ subseteq V$ of cardinality at most $k$, so that each edge in $E$ is incident to at least one node in $V’$?

We translate this into a regex crossword with $|E|+1$ columns and $|V|$ rows as follows: All columns, except for the first, correspond to an edge. They get a regex $0^*1(0|1)^*$. All rows correspond to a vertex. They get a regex that allows to write either

• a $1$ in the first column and each column corresponding to an edge incident to that node and zeroes in all other columns, or
• $0^*$

Finally, the first column counts the size of the vertex cover. It gets a regex, that allows for at most $k$ ones. The correspondence between solutions to the regex crossword and vertex covers should be obvious. Example: Find a vertex cover of size 2 for the following graph: $V_A = 0^* big| 10110$ $V_B = 0^* big| 11101$ $V_C = 0^* big| 10011$ $V_D = 0^* big| 11000$ $Counter = 0^* big| 0^*10^* big| 0^*10^*10^*$ $E_1 = 0^*1(0|1)^*$ $E_2 = 0^*1(0|1)^*$ $E_3 = 0^*1(0|1)^*$ $E_4 = 0^*1(0|1)^*$ Lastly, you can set up the “crossword” so that $V_A$ through $V_D$ are the top regexes and $Counter$ and $E_1$ through $E_4$ are the left side regexes. Solving this regex crossword give you a vertex cover of size 2 for nodes $V_A,V_B$ or $V_C,V_B$. If we change k to be 1 and $Counter$ to be $0^* big| 0^*10^*$ as another example, the regex crossword is impossible to solve because there is no vertex cover of size 1.