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.

  • $\begingroup$ 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$? $\endgroup$
    – zdm
    Sep 4 '18 at 0:55
  • $\begingroup$ @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$. $\endgroup$
    – J. Schmidt
    Sep 4 '18 at 8:58
  • $\begingroup$ Anyway, I see that the authors use the inequality $q<3nt$ in the proof of Claim 2.3. $\endgroup$
    – zdm
    Sep 4 '18 at 21:08
  • $\begingroup$ @zdm They do. It would make the proof for Claim 2.3 incorrect if it's actually $q<3(3nt)$. $\endgroup$
    – J. Schmidt
    Sep 5 '18 at 13:46

Your Answer

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

Browse other questions tagged or ask your own question.