1
$\begingroup$

I have an assignment where I have to prove that solving a crossword puzzle is an $NP$-complete problem by reducing from EXACT 3-SET COVER. I have more or less given up at this point. If anyone could give me a hint or know where to find the proof, it would be much appreciated.

Problem: [${\bf CrossWordPuzzleConstruction}$]

Input: Given are an alphabet $\Sigma$ not containing the symbols "blank" or "#", a non-empty set of strings $S=\{s_1,\dots,s_m\}$ over $\Sigma$, and an $n\times n$ matrix $A$ for a non-negative integer $n$. The entries in $A$ are either "blank" or "#".

Output: YES if the blank entries in $A$ can be filled with letters from $\Sigma$ in such a way that the result is a crossword puzzle with strings from $S$. That is, every maximal horizontal or vertical sequence in $A$ consisting of letters from $\Sigma$ is a string from $S$ when read left-to-right respectively downwards. The same string may occur more than once.

We call the problem ${\bf CPC}$ for short.

Example: $\Sigma=\{a,b,c\}$, $S=\{aa,bb,cac,ab,cab,ca,a,ac,bba,aab,bab\}$,

enter image description here

The answer to this input is YES as the following solution shows:

enter image description here

Problem: [${\bf ExactThreeCover}$]

Input: The set $X=\{1,2,\dots,n\}$ where $n=3q$, $q\geq1$, and a collection $\mathcal{C}=\{C_1,C_2,\dots,C_m\}$ of subsets of $X$ of sixe $3$. That is, for $i\in\{1,\dots,m\}$, we have $C_i\subseteq X$ and $|C_i|=3$.

Output: YES if there exists a set $\mathcal{A}\subseteq\mathcal{C}$ such that the elements of $\mathcal{A}$ are a partition of $X$, i.e., $\cup_{C_i\in \mathcal{A}}=X$ and $C_i\cap C_j=\emptyset$ for $C_i,C_j\in\mathcal{A}$ and $i\neq j$.

$\endgroup$
  • 1
    $\begingroup$ Welcome to Computer Science! We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and what you could not figure out. It will definitely draw more answers to your post. Until then, the question will be voted to be closed / downvoted. You may also want to check out these hints, or use the search engine of this site to find similar questions that were already answered. $\endgroup$ – Raphael Nov 2 '18 at 13:46
  • $\begingroup$ Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics (note that you can use LaTeX) and don't forget to give proper attribution to your sources! $\endgroup$ – Raphael Nov 2 '18 at 13:46
0
$\begingroup$

Since you are so interested in solving this assignment to hand in and be applaused by the whole class.

I give you another answer.

Reduce from X3C (Exact 3-Set Cover) as required.

We will construct a table as follows:

The leftmost column will be forced to be (solely by its maximum length)

$\star\\ \star\\ \star\\ 1_{row}\\ \star\\ \star\\ \star\\ \star\\ \star\\ 2_{row}\\ \star\\ \star\\ \star\\ \star\\ \star\\ 3_{row}\\ \dots $

The uppermost row will contain the solution (a subcollection of $3$-sets).

$\#\#\#1_{col}\star\star\star\star2_{col}\star\star\star\star3_{col}\#\#\dots\#\#\#$ to denote that we choose a $3$-set that contains $1$, $2$ and $3$.

Now, all that we need is to make sure that our solution which appear in the uppermost row is feasible. It means that for each $i_{row}$, if we "beam" from its position (in the first column) to the right, we will meet $i_{col}$ exactly once (in fact, we only need to assure at most once).

To guarantee this, we create zig-zag tunnel like this:

- ---
| | |
| | |
---- --- ...

To be able to cross a different column item, we add these words $i_{row}<i_{row}j_{col}>i_{row}$ where $<i_{row}j_{col}>$ is a single symbol, for every $i\neq j$. And, similarly, for the column item, these words $j_{col}<i_{row}j_{col}>j_{col}$

To be able to meet the same column item (and never again), we add these words $i_{row}<i_{row}i_{met}>i_{met}$, for all $i$. Similarly, for the column item, these words $i_{col}<i_{row}i_{met}>i_{col}$.

Note that, $i_{met}$ are deemed to belong to the rows only.

To be able, to continue after crossing the same column item, and never meets same column item again, we add these words $i_{met}<i_{met}j_{col}>i_{met}$, for every $i\neq j$. And, similarly, for the column item, $j_{col}<i_{met}j_{col}>j_{col}$.

Lastly, to be able to go through the tunnel, add all these word $x\star x$ for all symbol $x$ that appears so far.

$\endgroup$
  • $\begingroup$ Thanks, I greatly appreciate your answer and quick response. Thank you very much for the time and effort you have put into my question. $\endgroup$ – Skulldj skull Nov 2 '18 at 21:07
0
$\begingroup$

A reduction from PLANAR 3-SAT with bounded occurrences is more viable.

The upper bound of occurrences should be $3$ for each variables $x_i$ (two positive and one negative OR two negative and one negative).

$\endgroup$
  • $\begingroup$ I am aware that there might be easier reductions, but the assignment states that I have to use EXACT 3-SET COVER. But thanks for the tip anyway. $\endgroup$ – Skulldj skull Nov 1 '18 at 14:18
  • $\begingroup$ Which book is this assignment contained in? $\endgroup$ – Thinh D. Nguyen Nov 2 '18 at 9:10
  • $\begingroup$ It is not from a book it's for a school project. $\endgroup$ – Skulldj skull Nov 2 '18 at 11:47
  • $\begingroup$ If so, then a link to your professor's class webpage would give more materials on solving this problem. Since, the taught-in-class techniques could hint a quick solution to homework assignment. $\endgroup$ – Thinh D. Nguyen Nov 2 '18 at 11:50
  • $\begingroup$ All the information can be found in a note called "Lecture Notes Computationally Hard Problems Paul Fischer, Carsten Witt DTU Compute, Danmarks Tekniske Universitet", but I think it is only available on my school's intranet, and I am not allowed to hand it out to you. $\endgroup$ – Skulldj skull Nov 2 '18 at 11:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.