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.
Asked By : Glen Takahashi
Answered By : FrankW
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/30143
0 comments:
Post a Comment
Let us know your responses and feedback