# Error in paper “Some NP-complete geometric problems”?

The paper in question: M.R. Garey, R.L. Graham and D.S. Johnson. Some NP-complete geometric problems .

This paper proofs the NP-completeness of some well-known problems, such as the Steiner Tree Problem, by reducing Exact Set Cover by 3-sets to these problems.

On page 3 (labeled page 12), right above Equation (2.2), it is stated that the number of crossovers is $$q < 3nt$$. In the example figure (Fig. 6) on page 4 however, this is clearly not true, as the number of crossovers $$q=26$$, whereas $$3nt=18$$ (as the number of subsets $$t=3$$, and the size of the set to cover $$3n=6$$).
I would understand if $$q<3(3nt)$$, is this an error?

PS: even if it's an error, it would likely not change the NP-completeness proof(s). I only ask to better understand the reasoning behind them.

• Why do you think that "the size of the set to cover $3n=6$"? Is it by definition of X3C that the union of the $3$-element sets of the collection equal to the set $U$? – zdm Sep 4 '18 at 0:55
• @zdm on the second page of the paper, when defining X3C, it is stated that $U = \{1,2,3,...,3n\}$. On the third page, directly below the section 2 title, it is stated $\cup_{i=1}^t F_i = \{1,2,...,3n\}$. To answer your question, yes, by these arguments the union of the 3-element sets of the collection equals the set $U$. – J. Schmidt Sep 4 '18 at 8:58
• Anyway, I see that the authors use the inequality $q<3nt$ in the proof of Claim 2.3. – zdm Sep 4 '18 at 21:08
• @zdm They do. It would make the proof for Claim 2.3 incorrect if it's actually $q<3(3nt)$. – J. Schmidt Sep 5 '18 at 13:46