Filling crosswords is very hard

We revisit a classical crossword filling puzzle which already appeared in Garey& Jonhson's book. We are given a grid with ������ vertical and horizontal slots and a dictionary with ������ words. We are asked to place words from the dictionary in the slots so that shared cells are consistent. We attempt to pinpoint the source of intractability of this problem by carefully taking into account the structure of the grid graph, which contains a vertex for each slot and an edge if two slots intersect. Our main approach is to consider the case where this graph has a tree-like structure. Unfortunately, if we impose the common rule that words cannot be reused, we discover that the problem remains NP-hard under very severe structural restrictions, namely, if the grid graph is a union of stars and the alphabet has size 2, or the grid graph is a matching (so the crossword is a collection of disjoint crosses) and the alphabet has size 3. The problem does become slightly more tractable if word reuse is allowed, as we obtain an ������tw algorithm in this case, where tw is the treewidth of the grid graph. However, even in this case, we show that our algorithm cannot be improved to obtain fixed-parameter tractability. More strongly, we show that under the ETH the problem cannot be solved in time ������������(������), where ������ is the number of horizontal slots of the instance (which trivially bounds tw). Motivated by these mostly negative results, we also consider the much more restricted case where the problem is parameterized by the number of slots ������. Here, we show that the problem does become FPT (if the alphabet has constant size), but the parameter dependence is exponential in ������2. We show that this dependence is also justified: the existence of an algorithm with running time 2 ������(������2), even for binary alphabet, would contradict the randomized ETH. After that, we consider an optimization version of the problem, where we seek to place as many words on the grid as possible. Here it is easy to obtain a 21-approximation, even on weighted instances, simply by considering only horizontal or only vertical slots. We show that this trivial algorithm is also likely to be optimal, as obtaining a better approximation ratio in polynomial time would contradict the Unique Games Conjecture. The latter two results apply whether word reuse is allowed or not. Finally, we present some special cases where the problem is decidable in polynomial time. In particular, we present three reductions, one to 2 -SAT, the second to MAXIMUM MATCHING and the third to EXACT MATCHING.