patternModerate
Are regex crosswords NP-hard?
Viewed 0 times
areregexhardcrosswords
Problem
I was fooling around the other day on this website: http://regexcrossword.com/ and it got me wondering what the best way to solve it was.
Can you solve the following problem in polynomial time or is it NP-hard?
Given an NxM grid with N regular expressions for the columns and M for the rows, find any solution to the grid such that all the regular expressions are satisfied, or say that no solution exists.
Can you solve the following problem in polynomial time or is it NP-hard?
Given an NxM grid with N regular expressions for the columns and M for the rows, find any solution to the grid such that all the regular expressions are satisfied, or say that no solution exists.
Solution
The problem is NP-hard.
We show this by reducing vertex cover:
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.
We show this by reducing vertex cover:
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.
Context
StackExchange Computer Science Q#30143, answer score: 11
Revisions (0)
No revisions yet.